[CodeJam][2017][Round 1B] B. Stable Neigh-bors

문제 : https://code.google.com/codejam/contest/8294486/dashboard#s=p1&a=1

---

우선은 R, Y, B만 있는 경우를 생각하자.

이 때는 두 번에 나눠서 정답을 만들 수 있다.

1회차에 R, Y, B를 순서대로 나열한다. (R+Y+B / 2의 오름차순 한 개수만큼만 넣는다. - 반)

예를 들어, R 3개, Y 2개, B 1개라고 하면 먼저 3개를 나열한다. ex) RRR

그리고 2회차에 만든 정답 문자열 사이사이에 알파벳을 다시 차례대로 넣는다. ex) RYRYRB

알파벳 R, Y, B가 (R+Y+B)/2 보다 크다면 2회차 때 연속되게 나올 수 밖에 없기 때문에 정답이 불가능하다. -> IMPOSSIBLE

주의할 점은 R, Y, B를 순서대로 나열하면 안된다는 것이다.

예를 들어, R 1개, Y 2개, B 1개인 경우

RYYB가 될 수도 있기 때문이다. Y가 연속되서 나오기 때문에 정답이 불가능하다.

이 때, Y -> R -> B 순으로 위 알고리즘을 적용한다면

YRYB가 된다. 

따라서 R, Y, B의 개수를 기준으로 정렬(오름차순, 내림차순 상관 無) 한 뒤 그 순서대로 알파벳을 집어넣는다.

예시에서는 내림차순 정렬으로 Y(2), R(1), B(1) 순서로 정렬한 뒤 넣었다.

이때까지는 SMALL인 경우(혼합 색상 없는 경우. O = G= V = 0) 이다.

여기에서 혼합 색상이 들어가는 경우는 정답 배열을 앞에서부터 탐색하면서 

'R'인 경우 뒤에 "GR"을 붙이고, 

'V'인 경우 뒤에 "VY"를 붙이고 

'B'인 경우 "OB"를 붙여가며 

정답을 만들어간다.

혼합 색상(O,G,V)은 해당 문자 하나만 나오거나(하지만 문제 조건에서 N이 3이상이기 때문에 이경우는 생각하지 않아도 된다.)

"RGR", "VYV", "BOB"와 같이만 나올 수 있기 때문이다.

혼합 색상을 만들 때, R, Y, B는 혼합 색상 하나당 하나가 소모된다.

따라서 SMALL을 위한 알고리즘에서 정답 문자열을 만들 때 미리, R, Y, B 개수를 혼합 색을 만들 때 사용되는 개수만큼 빼주고 진행한다.

즉, R이 2개 G가 하나 있다면 R은 1개만 사용해서 SMALL 알고리즘을 적용하여 정답 문자열을 만든다.

이 때, G가 R보다 많은 경우는 정답을 만들 수 없다. 이 경우 IMPOSSIBLE을 반환한다.

시간복잡도는 O(N).

---

소스코드 : https://gist.github.com/fpdjsns/b17b9b4ea98ef265a87bf7cd42165576