백준 1138 자바 - 한 줄로 서기 (BOJ 1138 JAVA)

[ 문제보기 ]

[ 코드보기(깃헙) ]

 

 

  N이 최대 10이다. 따라서 모든 경우를 보려면 10! 번을 봐야한다. 이 경우 362880번으로, 사실 모든 경우를 봐도 가능하긴 하다! 다해봐야 O(N! * N) 정도이다.  

 

  사실 시간복잡도, 메모리복잡도 면에서 모두 이득인 방법이 더 있다. 어차피 입력이 키가 1인 사람부터 차례대로 들어오기 때문에, 키가 큰 사람부터 순서대로 입력을 만족하는 위치에 넣어버리면 된다. (따라서 그리디 알고리즘 분류다.)

 

4

2 1 1 0

 

의 입력을 확인해보자.

이 경우 키가 1인 사람은 좌측에 2명, 2인 사람은 좌측에 1명, 3인 사람은 좌측에 1명, 4인 사람은 좌측에 아무도 없다는 입력이다. 키가 작은 사람부터 보자면 어려운 문제가 확실하지만, 키가 큰 사람부터 보면 엄청 간단하다. 그냥 LinkedList 하나 만든 후에 큰 사람부터 그리디하게 넣어보자. 이 때 이 문제에서 제시된 조건은 '자신보다 큰 사람이 몇명이 있는지'만을 판단하면 되므로, 키가 큰 사람부터 자리를 고정시켜버리면 이후 그보다 작은 사람들이 어디에 들어가던지 그보다 큰 사람들의 조건에 영향을 끼치지 않는다는게 핵심이다.

 

A. 일단 키가 가장 큰 사람의 입력으로 뭐가 들어올 수 있을까? 0만 가능하다. 가장 크므로, 0 이외의 값은 잘못된 입력이라 볼 수 있다. 아래 그림은 LinkedList를 나타내며, 각 칸의 숫자는 키를 의미한다. 가장 큰 사람은 뭐 생각할 것도 없이 바로 넣어버리면 된다.

 

 

B. 다음으로 키가 3인 사람은 입력으로 뭐가 들어올 수 있을까? 3보다 큰 사람은 이 경우 1명 뿐이므로, 0 또는 1만 입력으로 들어올 수 있다. 이 때, 0이었다면 좌측에 자신보다 큰 사람이 있으면 안되므로 다음과 같이 '4'인 사람의 좌측에 들어가야 한다.

하지만 위 입력에서 키가 3인사람 좌측에 1명이 있다고 했으므로 자신보다 큰 4의 우측에 들어가야 한다.

 

 

C. 다음으로 키가 2인 사람을 보자. 마찬가지로 자신보다 큰 사람이 최대 2명이므로 입력은 0,1,2 중 하나일 것이다. 이 예시에서는 '1'이 입력으로 들어왔지만, 이하 0,1,2 모든 경우를 살펴보겠다.

 

C.1 키가 2인 사람의 좌측에 더 큰 사람이 0명인 경우

C.2 키가 2인 사람의 좌측에 더 큰 사람이 1명인 경우

C.3 키가 2인 사람의 좌측에 더 큰 사람이 2명인 경우

위와 같다. 즉, 현재 키가 A인 사람까지 확인했고, 그 때 리스트의 크기가 S였다면, 다음으로 A-1인 사람을 확인할 때 입력값은 0~S 까지만 들어올 수 있고, 리스트의 '입력값'을 인덱스로 삼아 해당위치에 들어가면 됨을 확인할 수 있다. 그리고 그 이후 [A-2]...[0] 까지 모든 입력도 마찬가지다.

 

 

D. 마지막으로 키가 1인 사람을 보자. 입력은 2였으므로, 인덱스 2의 위치에 들어가면 된다! 그럼 다음과 같다.

 

따라서 애초에 LinkedList를 사용해 구현한 것도, 이렇게 좌측과 우측에 넣는게 자유롭고 또 원하는 인덱스 위치에 값을 넣는게 자유로운 자료구조를 선택한 것이다. 사실 애초에 N의 최대치가 그리 크지 않아 ArrayList(일반적으로 말하는 Vector 자료구조. 자바에서는 Vector도 있지만 ArrayList가 더 효율적이다. 동작방식은 동일하다.)를 써도 상관없다.