백준 3015 자바 - 오아시스 재결합 (BOJ 3015 JAVA)

문제 : https://www.acmicpc.net/problem/3015

코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/03000/BOJ_3015.java 

 

  우선 체크를 어느 방향으로 할 지 정해보자. 전 왠지 입력 다 받고 풀기보단 입력 받으면서 바로바로 풀고 싶었기에 N번째 사람을 입력받을 때 그 이전사람들을 체크해보기로 했다(입력 받으면서 바로바로 하려면 그 이후 사람에 대한 정보는 없으므로 그 이전 사람들만 가지고 생각해야한다!).

 

  방향을 저와 같이 정했다면, 이번에 입력된 사람보다 키가 작은 이전사람은 의미가 없다는 것을 알 수 있다.

(위와 같이 4명까지 확인했다. 그리고 5명째를 확인하려고 하는데, 사실 이 때 N=2와 N=3은 N=4에 가려져서 N=5부터 어떠한 사람이 오더라도 볼 수 없게된 상태이다.)

따라서 i번째 사람을 확일할 때, i번째 사람의 키보다 작은 이전 사람은 모두 없애버려도 전혀 상관이 없다.

즉, 데이터 유지는 가장 최근에 본 사람보다 크거나 같은 사람까지만 유지하면 된다.

즉, N=5가 올 때 이전 사람 중 N=2와 N=3은 더이상 필요없으므로 위와 같은 상태면 N=5가 판단하기에 충분한 상태가 된다.

 그리고 N=5가 오면서, N=4도 필요없어진다. (N=1과 N=5의 키는 같다.)

 

 

그럼 1차 로직이 나왔다! 위 과정을 표현하기 가장 좋은 Stack 자료구조를 사용해서 로직을 짜보면 아래와 같다. cnt는 서로 볼 수 있는 쌍의 개수이다.

 

1. N명에 대해 i번째 사람의 키를 입력받으면서, 현재 스택에 들어있는걸 위(스택의 top)에서부터 확인하면서 자신보다 키가 작은 녀석들은 빼버리고 아무튼 볼 수 있는 녀석들이니 cnt를 1씩 증가시킨다.

 

2. 자신보다 키가 크거나 같더라도 바로 옆 사람은 사이에 아무도 없으므로 볼 수 있다. 따라서 '1' 로직 후에도 스택이 비지 않았다면 자신보다 크거나 같은 녀석이 있는 것이므로 cnt를 1 증가시킨다.

 

 

  간단해보이는데, 사실 틀렸다.

만약 문제가 '두 사람 사이에 A 또는 B보다 키가 크거나 같은 사람이 없어야 한다.' 이랬다면 위 로직으로 간단하게 끝난다. 하지만 이 문제는 키가 큰 사람만 없어야 한다고 했다. 그러므로 같은 사람에 대한 처리가 따로 필요하다!

위 로직 정도면 골드 하위~중위 티어 정도면 충분한 문제인데, 골드 상위티어로 책정된 이유가 이 부분 때문이다.

 

  단순히 위 로직의 '1'을 '자신보다 작거나 같은 녀석들을 빼버리고'로 교체하면 안된다. 왜냐면 그 이후에 키가 같거나 큰 녀석들이 왔을때도 볼 수 있으므로 데이터를 유지해야만 한다. 그렇다고 무작정 유지하게되면, 스택의 개념상 그 밑을 볼 수 없게 된다. 그렇다고 리스트나 배열로 처리한다면 시간초과가 나게된다. (N=500,000, 키 전부 동일한 입력을 생각해보면 된다. O(N^2)이 되므로 절대 통과불가하다.)

 

 

  전 이 부분을 스택에 단순히 키만 넣는게 아니고, 키와 동일 키가 몇 명이 있는지도 넣을 수 있게 함으로써 처리했다.(코드의 People 클래스) 2차 로직(solution)은 아래와 같다.

 

1. N명에 대해 i번째 사람의 키를 입력받으면서, 현재 스택에 들어있는걸 위(스택의 top)에서부터 확인하면서 자신보다 키가 작은 녀석들은 빼버리고 아무튼 볼 수 있는 녀석들이니 cnt를 해당 위치의 People의 cnt씩 증가시킨다.

 

2. 스택의 top이 자신과 동일한 키라면, 해당 위치의 People의 cnt만 1 증가시킨다.

 

3. 자신보다 키가 크거나 같더라도 바로 옆 사람은 사이에 아무도 없으므로 볼 수 있다. 따라서 '1' 로직 후에도 스택이 비지 않았다면 자신보다 큰 녀석이 있는 것이므로 cnt를 1 증가시킨다.

 

 

위에서 그렸던 그림을 로직2로 변경해서 그려보면 다음과 같다.