백준 3015번 오아시스 재결합 - 스위프트(Swift) 풀이 + 그림 설명

 어디서 많이 본 것 같은 느낌이 나면서도 중복 처리가 힘들었던 문제. 일단 기본 아이디어는, X보다 더 큰 사람 Y가 나오는 순간, 이제 Y보다 뒤에 있는 사람들은 X를 볼 수 없으므로 X를 더 이상 고려하지 않아도 된다는 것이다. 배열을 순차 탐색하면서 증가 때마다 무슨 일이 일어나고.. 왠지 스택을 쓰면 뭔가 될 것 같은 느낌이다.

 아래와 같이 [3, 2, 2, 1, 2]로 주어진 상황이라고 하자. 손으로 풀어보면 그림과 같이 8쌍이 서로 볼 수 있다. 왼쪽부터 순차 탐색할 것이므로 A와 B가 서로 볼 수 있다면, 더 우측에 있는 B차례에서 카운트+1을 해줄 것이다.

 

 아까 말했던 기본 아이디어, 더 큰 사람이 올 때까지 이제 스택에 일단 한 명씩 담자. 계속 더 작은 사람만 담다보면 스택 내부는 항상 감소하는 상태로 유지될 것이다. 3X1은 3이 한 개 들어있다는 의미이다. 그냥 3을 담지 않고 개수를 같이 적어 담은 이유는, 키가 같은 사람이 있을 수 있는데, 키가 같은 사람들도 서로 볼 수 있기 때문이다. 이것을 고려해주려면 개수까지 담아두어야 한다. 뒤에 과정에서 더 자세하게 설명하겠다. 

 

 이제 하늘색 2차례이다. top보다 작으므로 스택에 push하면 된다. 이때 top인 3과 서로 볼 수 있음을 카운트해주자! 어떤 사람 A를 push하기 직전의 스택 top의 의미는, A가 왼쪽을 바라볼 때 처음으로 등장하는 A보다 큰 사람이다. 이렇게 앞으로 push 할 때는 왼쪽을 바라볼 때 처음으로 등장하는 자기보다 큰 사람과의 쌍을 카운트해줄 것이다.

 

 이제 문제 상황이 왔다. top과 현재 고려중인 사람의 키가 같다. 키가 같은 사람은 서로 볼 수 있으므로 앞에 있는 하늘색 2를 카운트해줘야 한다. 또 맨 앞에 있는 3도 볼 수 있다. 따라서 먼저 top의 2X1을 보고 앞에 키가 2인 사람 한 명을 볼 수 있다는 것을 카운트 한 뒤, pop을 해주고, 이제 새로운 top인 3X1을 보고 앞에 3도 볼 수 있다는 것을 카운트해준다.

 

 개수를 같이 기록해주는 이유가 이제 등장한다. 다음에 2보다 크거나 같은 사람이 온다면, 그 사람은 초록색 2와도 서로 볼 수 있고, 하늘색 2와도 서로 볼 수 있다. 이 둘을 다 카운트해주려면 개수를 알아야 한다. 따라서 2X2를 push해서 키가 2인 사람이 앞에 2명이 있었다는 것을 표시해둔다.

 

 다음은 노란색 1차례이다. top보다 작으므로 push 해주면 된다. 초록색 2를 볼 수 있다는 것을 카운트해주는 것을 잊지 말자.

 

 드디어 top보다 더 큰 사람이 나왔다. 뒤에 사람은 더 없지만 있다고 치면 이제 노란색 1은 현재 빨간색 2 말고는 볼 수 있는 사람이 없다. 따라서 스택에 둘 필요가 없으므로 pop 해주고 빨간색 2가 볼 수 있었음을 카운트해주자. 이렇게 top보다 더 큰 사람이 나오면 top을 pop 해주고, 현재 사람과 서로 볼 수 있기 때문에 top에 기록된 개수만큼 카운트를 늘려주면 된다. 1이 1개 있었다고 기록되어 있으므로 지금은 카운트 1을 해주면 된다. 만약 1X3이었다면, 빨간색 2 앞에 볼 수 있는 키가 1인 사람이 3명 있었다는 것이므로 +3을 해주면 된다.

 

 이제 또 top과 키가 같아졌다. 아까 했던 것처럼 앞에 있는 키 2인 사람 2명과 서로 볼 수 있다는 것을 카운트해주자. top에 기록된 개수만큼 카운트하고 top을 pop 해준다. 그러고 나서 2 개수를 하나 늘려 2X3을 다시 push 해준다. push 해줄 때 top인 회색 3을 볼 수 있다는 것 카운트해줘야 한다.

반응형