백준 22866 자바 - 탑 보기 (BOJ 22866 JAVA)

https://www.acmicpc.net/problem/22866

 

  풀이방법을 생각하기보다는 구현이 복잡한(==귀찮은) 문제였다.

일단 3가지로 나눠서 생각해봐야 하는데,

 

1. 각 건물에서 좌측으로 보이는 건물의 개수

2. 각 건물에서 우측으로 보이는 건물의 개수

3. 각 건물에서 가장 가까운 건물 번호 중 작은 번호

 

위와 같다.

 

 

  일단 '각 건물에서 좌측으로 보이는 건물의 개수' 어떻게 구할지 생각해보자. 문제에서 제시된 예시를 예시로 들겠다.

3 7 1 6 3 5 1 7 에서 좌측부터 차례로 봐보자.

 

1번째 건물 : 3 이다. 현재 좌측으로 보이는건 없다. 뭐 일단 어딘가에 넣어둬보자.

2번째 건물 : 7 이다. 현재 좌측으로 보이는건 없다. (7보다 높아야 보임). 그 이후로는 모두 7에 막힐것이므로 3은 필요가 없다. 3은 필요없으니 빼버리고, 7을 넣어보자.

3번째 건물 : 1 이다. 좌측으로 7이 1개 보인다. 현재까지 3번째 건물에서 가장 가까운 건물은 2번째 건물이다. 사실 1은 가장 작은 건물이므로 앞으로 1이 다시 나와도 볼 수 없는 건물이긴하지만, 일단 넣어보자.

4번째 건물 : 6이다. 1은 이제 6에 가려서 안보일 것이므로 필요가 없으니 빼버린다. 7을 하나 볼 수 있다. 마찬가지로 현재까지 가장 가까운건 2번째에 넣었던 건물이다. 그리고 6을 넣어준다. 7은 6이 있어도 그 이후의 건물들도 볼 수 있으므로 냅둔다.

5번째 건물 : 3이다. 빼줄건 없고, 들어있던 2개를 모두 볼 수 있다. 3도 그대로 넣어준다. 그 다음에 1이나 2인 건물이 나온다면 3도 볼 수 있을 것이다. 가장 가까운 건물은 6과 7 중에 4번째 건물인 6이다.

6번째 건물 : 5이다. 3은 이제 볼 수 없으므로 빼버리고, 5에서는 6과 7을 볼 수 있다. 가장 가까운건 역시 4번째에 넣었던 6이다. 그리고 다시 5를 넣어주자.

7번째 건물 : 1이다. 5,6,7을 모두 볼 수 있다. 이 때 가장 가까운건 6번째에 넣었던 5이다. 1도 넣어주자.

8번째 건물 : 7이다. 가장 높은 건물이므로 모두 볼 수 없다. 모두 필요없으니 다 빼버리고 7을 넣는다.

9번째 건물 : 없다. 끝났다!

 

---

 

  위에서 어떤 자료구조를 썼는지도 말 안했지만, 당연히 스택을 썼음을 예상할 수 있을 것이다. 위의 과정과 같이, i번 건물을 확인할 때 스택에 현재 높이보다 낮거나 같은걸 전부 빼버린다. 그리고 남은것(스택의 사이즈)이 현재 건물에서 좌측으로 볼 수 있는 건물의 개수이다. 그리고 스택의 가장 맨 위에 있는 것이 현재 건물과 가장 가까운 건물이다. 이 과정으로 모든 건물에서 좌측으로 보이는 건물의 개수와, 좌측으로 가장 가까운 건물의 번호를 알 수 있다.

 

  그럼 우측으로 보이는 건물은 어떻게 알 수 있을까? 위 과정을 반대로 하면 된다. 즉 스택에 반대순서로 넣었다 빼면 된다. 그럼 각 건물에서 우측으로 보이는 건물의 개수와, 우측으로 가장 가까운 건물의 번호를 알 수 있다. (단, 가까운 건물의 거리가 동일하다면 작은 건물번호를 출력해야 함)

 

  위 그림에서는 건물의 높이만을 스택에 넣었지만, 사실 가까운 건물 번호를 알기 위해서는 스택에 건물 번호도 넣을 필요가 있다. 작성한 코드에서는 따라서 Building 클래스가 이 두가지를 모두 가진다. cnt[a]는 a번 건물에서 보이는 좌측 건물 + 우측 건물의 개수의 합이다. near[a][b]에서 near[a][0]은 가까운 건물의 번호, near[a][1]은 그 거리의 차이이다. 가까운 건물의 번호는 출력을 위해 필요하고, 거리의 차이는 이후 더 가까운 건물이 존재하는 경우를 찾기 위해서이다. 이후 27~43 line에서 '각 건물에서 좌측으로 보이는 건물의 개수'을 계산하고 / 45~61line에서 '각 건물에서 우측으로 보이는 건물의 개수'를 계산한다.

 

https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/22800/BOJ_22866.java