[백준 / BOJ] 22866 탑 보기

문제

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

22866번: 탑 보기

일직선으로 다양한 높이의 건물이 존재한다.

한 건물 i의 옥상에서 다른 건물들을 볼때 높이가 건물 i보다 큰 건물만 볼 수 있으며, 높이가 L인 건물 뒤에 L이하인 건물은 볼 수 없다고 할때, 각 건물에서 볼 수 있는 건물의 최대 수와 가장 가까운 건물의 idx를 구하는 문제다.

---

풀이

N이 최대 100,000으로 완전탐색으로 구현할 경우 O(N*N)번 반복해서 TLE를 맞게된다.

문제를 풀기 위해 "바라보는 방향으로 높이가 L인 건물 뒤에 높이가 L이하인 건물이 있다면 가려져서 보이지 않는다. 와 자신보다 큰 건물만 볼 수 있다." 조건을 이해하는게 중요했다. 

 

우선 조건을 하나하나 풀어보자.

1) 자신보다 큰 건물만 볼 수 있다 : (건물A) 에서 (건물B) 을 볼 수 있다면, (건물B)은 (건물A)보다 크다

2) 바라보는 방향으로 높이가 L인 건물 뒤에 높이가 L이하인 건물이 있다면 가려져서 보이지 않는다 : (건물A)에서 (건물B)을 볼 수 있을때, 1번 조건에 의해서 (건물B)이 볼 수 있는 건물은 (건물A)도 모두 볼 수 있다. 

3) 바라보는 방향으로 높이가 L인 건물 뒤에 높이가 L이하인 건물이 있다면 가려져서 보이지 않는다 : (건물A)에서 (건물B)를 볼 수 있을때, (건물B)뒤에 있는 건물중 (건물B)보다 작은 건물은 (건물A)가 볼 수 없다.

 

2번 조건에 의해서, 순차적으로 탐색하며, 이전 건물들이 볼 수 있는 건물을 저장해준다면, 현재 건물이 볼 수 있는 건물을 O(1)만에 구할 수 있다.

또한, 3번 조건에 의해서, 저장되어있는 이전 건물이 볼 수 있는 건물들중, 현재 건물 보다 작은 건물들은 다음에 나올 건물이 볼 수 없음을 알 수 있다.

위 과정을 왼쪽에서 오른쪽으로 한번 오른쪽에서 왼쪽으로 한번 진행해주면 된다.

 

따라서, 자료구조의 형태는 감소하는 순열꼴로 나오며, 가장 최근에 저장한 건물 순서로 제거해주면 되므로 Stack이나 Deque를 사용해주면된다.

 

잘 이해가 안된다면, 다음 예시를 보자.

문제의 예제 

(자신보다 왼쪽에 있는 건물들 중 자신이 볼 수 있는 건물들을 구하는 예시다. 오른쪽 또한 똑같이 구해준다.)

8
3 7 1 6 3 5 1 7

건물의 높이 = h 저장된 건물들 : [] 과 같이 표현하겠다. idx는 문제의 지문과 일치하도록 0이 아닌 1번부터 시작한다.

 

idx = 1

h = 3

[] = empty

idx = 1인 건물에서 볼 수있는 자신보다 왼쪽에 위치한 건물은 없다.

 

idx = 2

h = 7

[] = 3

이때, []에 저장된 건물중 자신보다 작거나 같은 건물을 모두 제거한다. 따라서, [] = 7 로 변하게 된다.

idx = 2인 건물에서 볼 수 있는 자신보다 왼쪽에 위치한 건물은 없다. (이하 왼쪽 생략)

 

idx = 3

h = 1

[] = 7

[]에 저장된 건물이 자신 보다 크다. 따라서, [] = 7, 1이 된다.

idx = 3 인 건물에서는 2개의 건물을 볼 수 있다.

 

idx = 4

h = 6

[] = 7, 1

[]에 저장된 건물중 1은 자신보다 작으므로 볼 수 없다. 또한 idx = 5... 에 위치한 건물들도 볼 수 없다. (자신이 막아버리므로) 따라서 자신보다 작은 건물들을 모두 제거하고... [] = 7, 6으로 변하게 된다.

idx = 4 인 건물에서는 1개의 건물을 볼 수 있다.

 

idx = 5

h = 3

[] = 7, 6

[] 에 저장된 건물이 자신 보다 크다. 따라서, [] = 7, 6, 3 이 된다.

idx = 5 인 건물에서는 2개의 건물을 볼 수 있다.

.

.

.

이런식으로 반복하면된다.

---

전체 소스 코드

https://github.com/devxb/JJUNalgo/blob/master/22866%20%ED%83%91%20%EB%B3%B4%EA%B8%B0/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃