[Google Kick Start] 2021 구글 킥스타트 Round H Painter 풀이

 

 

문제

---

https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435914/00000000008d9a88#problem

Kick Start - Google’s Coding Competitions

 

 

나의 풀이

---

문제가 조금 복잡하지만 구현 자체는 생각보다 단순하다. 

d = {'R':['R'], 'B':['B'], 'Y':['Y'], 'O':['R', 'Y'], 'P':['R', 'B'], 'G':['Y', 'B'], 'A':['R', 'Y', 'B'], 'U':[]}

위와 같이 각 컬러마다 필요한 원소색깔을 담은 딕셔너리를 만들어 둔다. 이 문제의 핵심은 결국 몇 번의 붓질로 모두 다 칠할 수 있는지 그 최소 횟수를 구하는 것이다. 만약 주어진 데이터가 YYBBGG라면 이를 원소색으로 분리하면

Y   Y   B   B   Y,B   Y,B

위와 같이 된다. 여기서 원소색인 Y와 B를 따로 분류해내서 아래와 같이 별도의 리스트로 만든 뒤, 해당 인덱스 자리에 해당 원소색이 있으면 1로 만들어준다. 위의 예시는 아래와 같이 나타낼 수 있다.

Y_list = [1, 1, 0, 0, 1, 1]

B_list = [0, 0, 1, 1, 1, 1]

3번째, 4번째 자리에는 Y가 필요없기 때문에 0이 된다. 결국 칠해주어야 하는 색은 3원색들이기 때문에 위와 같은 리스트에서 연속된 1의 갯수를 카운트 해주면 답이 된다. Y_list와 B_list에서 연속된 1의 갯수는 각각 2개, 1개이다. 따라서 답은 2+1=3이 된다.

시간복잡도는 O(n)이 된다.

 

코드

---

# https://codingcompetitions.withgoogle.com/kickstart/round/0000000000435914/00000000008d9a88

import copy

d = {'R':['R'], 'B':['B'], 'Y':['Y'], 'O':['R', 'Y'], 'P':['R', 'B'], 'G':['Y', 'B'], 'A':['R', 'Y', 'B'], 'U':[]}
T = int(input())
for t in range(T):
    n = int(input())
    s = input()
    job = []
    for i in range(n):
        job.append(copy.deepcopy(d[s[i]]))
    cnt = 0
    R_list, B_list, Y_list = [0]*n, [0]*n, [0]*n
    for i in range(len(job)):
        if 'R' in job[i]:
            R_list[i] = 1
        if 'B' in job[i]:
            B_list[i] = 1
        if 'Y' in job[i]:
            Y_list[i] = 1
    if R_list[0] == 1:
        cnt += 1
    for i in range(1,n):
        if R_list[i-1]==0 and R_list[i]==1:
            cnt += 1
    if B_list[0] == 1:
        cnt += 1
    for i in range(1,n):
        if B_list[i-1]==0 and B_list[i]==1:
            cnt += 1 
    if Y_list[0] == 1:
        cnt += 1
    for i in range(1,n):
        if Y_list[i-1]==0 and Y_list[i]==1:
            cnt += 1
    print(f'Case #{t+1}: '+str(cnt))