[코드트리] 흰검 칠하기

https://www.codetree.ai/missions/5/problems/painting-white-black?&utm_source=clipboard&utm_medium=text

 

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

< 입력 형식 >

첫 번째 줄에는 n이 주어집니다.

두 번째 줄부터는 n개의 줄에 걸쳐 명령이 주어집니다. 형태는 “x L” 혹은 “x R” 입니다.

• 1 ≤ n ≤ 1,000
• 1 ≤ x ≤ 100

< 풀이 >

문제 상황 그대로 시뮬레이션 하듯이 옮겨본다.

검은색과 흰색 타일이 각각 두 번 이상 칠해지면 회색 타일로 변하는 것에 유의한다.

따라서 검은색 타일과 흰색 타일이 칠해진 개수를 기억할 필요가 있다고 생각했다.

조건에 따르면 n이 가질 수 있는 최대값은 1000, x의 경우는 100이므로 시뮬레이션을 위해 왼쪽 최대 100000개, 오른쪽 최대 100000개, 다 합해서 최대 200000개의 entry를 담고 있는 리스트가 필요하다.

또한 개수를 세기 위해 현재 어느 색이 칠해져있는지도 기억할 필요가 있다. 'N(None)', 'W(White)', 'B(Black)' 값 중 하나를 갖는 리스트로 정의한다.

n = int(input())

arr = ['N' for _ in range(200001)]
black_count = [0 for _ in range(200001)]
white_count = [0 for _ in range(200001)]

 

n번 루프를 돌면서 입력을 받고, 타일을 칠할 때 현재 위치를 포함하는 것과 각 명령 이후에는 제자리에 그대로 위치해있음에 유의한다.

cursor = 100000
for _ in range(n):
    distance, direction = input().split()

    for i in range(int(distance)):
        print_tile(cursor, direction)
        if direction == 'L':
            cursor -= 1
        else:
            cursor += 1
    # 제자리에 멈춰야함
    if direction == 'L':
        cursor += 1
    else:
        cursor -= 1

 

가독성을 위해 print_tile로 타일을 칠하는 시뮬레이션을 실제로 행하는 함수를 분리한다.

왼쪽은 흰색, 오른쪽은 검은색을 칠한다. 기억하자.

def print_tile(cursor, direction):
    now = arr[cursor]
    if direction == 'L':
        white_count[cursor] += 1
        if check_gray(cursor):
            arr[cursor] = 'G'
        else:
            arr[cursor] = 'W'
    else: # 'R'
        black_count[cursor] += 1
        if check_gray(cursor):
            arr[cursor] = 'G'
        else:
            arr[cursor] = 'B'

 

타일을 칠할 때 검은색과 흰색 타일이 각각 두 번 이상 칠해지면 회색 타일로 변하게 되므로, 이를 체크하는 함수 역시 check_gray()로 별도로 분리한다.

def check_gray(cursor):
    return black_count[cursor] >= 2 and white_count[cursor] >= 2

 

답을 출력한다

w = arr.count('W')
b = arr.count('B')
g = arr.count('G')

print(w, b, g, sep=" ")

< 느낀 점 >

check_gray()를 작성할 때 2 이상이 아니라 '== 2'로 두는 실수를 해서 꽤 헤맸다. 테스트케이스 중 일부만 성공했기에, 알고리즘 자체에 문제가 있는줄 알고 여러번 고쳐쓰기도 했다. 검은색 타일이 2번, 흰색 타일이 2번 칠해지면 회색으로 변한다는 사실에 매몰되어, cursor가 이미 회색 타일인 지점을 계속 지나갈 수도 있는 상황을 고려하지 못했던 것 같다.