[Kickstart][2020][Round E] 2. High Buildings

문제 : https://codingcompetitions.withgoogle.com/kickstart/round/000000000019ff47/00000000003bef73

---

N개의 1~N 높이를 가진 빌딩들이 있다.

Andre와 Sule이 각각 최좌측(leftmost)과 최우측(rightmost)에서 빌딩들을 바라볼 때 관측할 수 있는 빌딩 수를 각각 A, B라 한다.

빌딩을 관측할 수 있는 조건은 i번째 빌딩의 높이가 바라보는 방향의 앞쪽에 있는 빌딩들의 높이보다 같거나 클때 i 빌딩을 관측할 수 있다. 예를 들어, 빌딩들의 높이가 3 2 5 4 1. 라고 했을 때, 2 높이의 빌딩은 왼쪽에서 봤을 때, 3 높이의 빌딩에 가려보이지 않고 오른쪽에서 봤을 때는 5, 4 높이의 빌딩에 가려 보이지 않는다. 이 경우 A는 2(3, 5). B는 3(5, 4, 1)이 된다.

N, A, B 그리고 Andre, Sule이 동시에 관측할 수 있는 빌딩의 수인 C가 주어질 때, 가능한 빌딩 높이 배열을 구해라.

---

C = 왼쪽에서 볼 때와 오른쪽에서 볼 때 동시에 관측 가능한 빌딩 수 = 가장 높은 빌딩 수

가장 높은 빌딩들 사이에 빌딩들이 있으면 안 보이므로 A - C, B - C 개의 빌딩들은 각자 가장 높은 빌딩들 왼쪽, 오른쪽에 위치해야 한다. => 가장 높은 빌딩들은 배열의 중간에 둔다.

 

C는 A, B 동시에 관측 가능한 빌딩 수 이므로 최소로 필요한 빌딩 수(보이는 빌딩 수)는 (A - C) + C + (B - C) = A + B - C 가 된다.

최소로 필요한 빌딩 수가 N보다 큰 경우 불가능한 경우이므로 IMPOSSIBLE이 된다. 만약 최소로 필요한 빌딩 수가 N보다 크다면 Andre나 Sule이 안보이는 위치에 빌딩을 숨겨두면 된다. A + B - C가 보여야하는 빌딩 수 이므로 숨겨야 하는 빌딩 수는 N - (A + B - C) 가 된다.

이 때, 빌딩을 숨겨둘 수 있는 경우는 A - B나 B - C가 0보다 커야 한다. 예를 들어 N = 5, A = 1, B = 1, C = 1 라고 했을 때, 숨겨야 하는 빌딩 수는 N - (A + B - C) = 5 - 1 = 4. 4개를 숨겨야 하는데, 왼쪼이나 오른쪽에서 봤을 때 정해진 높이의 빌딩의 수는 정해져 있다. 그게 바로 C이다. 즉, C개의 빌딩은 가장 높은 높이로 정해져있다. 만약 이보다 관측 가능한 빌딩이 하나라도 있다면 이들 사이에 빌딩을 숨길 수 있다. ex) 2 _ _ _ 5 (A가 2, C가 1이라고 하면 _ 자리에 1개 이상의 빌딩을 숨길 수 있다. 이 때, 숨기는 빌딩의 높이는 1로 하고 보이는 빌딩들의 높이는 2이상으로 하면 된다.)

그러나 만약 A = C라면 빌딩을 숨길 수 없게 된다. ex) _ _ _ _ 5 (A = C = 1 이라고 하면 _ 자리에 1~5 어떤 수를 넣어도 정해진 조건을 만족할 수 없기 때문에 반드시 5 _ _ _ _ 이런식으로 빌딩이 나와야 한다.)

따라서 A = B = C 라면 왼쪽, 오른쪽 어디서도 빌딩을 숨길 때가 없기 때문에 이 경우 숨겨야 하는 빌딩 수가 1개 이상인 경우 IMPOSSIBLE이 된다. 그러나 A = B = C 라도 C가 2 이상인 경우는 가능하다. 최고층 빌등 사이에 빌딩을 숨길 수 있기 때문이다. ex) N = 5, A = B = C = 2라면 5 _ _ _ 5 이런식으로 빌딩이 있을 수 있다.

 

위 조건에 맞춰 IMPOSSIBLE인 경우를 걸러주고 정답 배열을 만들어보자.

최고층 빌딩들을 기준으로 왼쪽, 중간(최고층 빌딩 사이), 오른쪽에 몇 개의 빌딩을 숨겨야 하는지 먼저 구한다.

결국 각 구역에 빌딩들을 숨길 수 있냐, 없냐로 구분할 수 있다. (A = C인 경우 빌딩을 숨길 수 없다. A > C인 경우 1개 이상의 빌딩들을 숨길 수 있다.)

일단 총 숨길 수 있는 빌딩 수를 구한 뒤, 왼쪽, 중간, 오른쪽에 숨겨야 하는 빌딩 수를 구한다.

만약 왼쪽에 빌딩들을 숨길 수 있으면 왼쪽에 모두 숨기고 아니면 중간을 판단하고 이런식으로 한다. 

 

i) 왼쪽에 숨길 수 있는 경우 : A > C

왼쪽 구역에 빌딩을 숨긴다고 하면 보이는 빌딩들을 최좌측부터 A - C 개의 빌딩 수만큼 2를 넣고 숨겨야 하는 빌딩 수 만큼 1을 넣는다. ex) 2 3 4 1 1(A - C = 3, 숨겨야하는 빌딩 수 = 2 인경우)

ii) 중간에 숨길 수 있는 경우 : C > 1

최고층 빌딩을 넣어야 하므로 N 높이의 빌딩을 하나 넣고 숨겨야하는 빌딩들을 그 다음에 1 높이로 넣은 다음 C-1개의 N 높이의 빌딩을 차례대로 넣는다. ex) N 1 1 N N (C = 3, 숨겨야하는 빌딩 수 = 2 인경우)

iii) 오른쪽에 숨길 수 있는 경우 : B > C

숨겨야하는 빌딩 수만큼 1을 넣고 B - C개의 빌딩 수만큼 2를 넣는다.

ex) 1 1 4 3 2 (N = 5, B - C = 3, 숨겨야하는 빌딩 수 = 2 인경우)

 

가장 높은 빌딩은 N, 숨겨야하는 빌딩은 1, 이외에 보이는 빌딩은 2로 넣었는데, N이 2인 경우 가장 높은 빌딩이 아닌 빌딩 중 보이는 빌딩을 2로 넣으면 가장 높은 빌딩과 높이가 겹치므로 1로 넣어야한다. 이렇게 넣는다 하더라도 N이 2인 경우 나올 수 있는 TC로 위 알고리즘을 돌리면 숨길 수 있는 빌딩이 나올 수가 없으므로 올바른 정답이 나온다.

 

시간복잡도는 O(N).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/codejam/kickstart/2020/roundE/High%20Buildings.cpp

---

풀다가 아무리해도 안되서 5 1 1 1, 5 1 2 1, ... 처럼 N이 5일 때 모든 TC를 만들어서 돌려보고 output에서 틀린경우를 하나하나 찾아봤다. 

 

그렇게해서 잘못된 결과를 도출하는 TC를 찾았다.

[input] 5 4 3 4 -> [output] Case #19: IMPOSSIBLE

이전에는 가장 높은 빌딩들은 무조건 가운데에 일렬로 나열해놨는데 그 사이에도 빌딩이 들어갈 수 있다는 것을 간과하고 있었다. 그래서 hideMiddle 변수 추가하고 IMPOSSIBLE 조건을 변경했더니 Case #19: 5 1 5 5 5 결과를 얻을 수 있었다.

 

역시 알고리즘에는 평안한 마음가짐과 시원한 아메리카노가 좋은 각성제 역할을 하는 듯.

추적추적 내리는 빗소리가 bgm으로 추가되면 더할 나위 없구나 허허. 왜 안되는지 고민했던 나날이여 안녕~ 기분째지네