[백준] 1343번 폴리오미노

https://www.acmicpc.net/problem/1343

1343번: 폴리오미노

 

 

풀이

출력
첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.
출력 조건이 사전순이기 때문에 'AAAA'를 넣을 수 있으면 무조건 넣어야하는 문제라 단순하게 풀 수 있다.

 

 

count = 0
answer = ""

for i in input_string:
    if i == 'X':
        count += 1
        if count == 4:
            answer += "AAAA"
            count = 0

문자는  X , . 두 종류가 있고
X이면 count를 증가시켰다.
count가 4가 되면 AAAA를 넣을 수 있기 때문에 정답에 추가한 뒤 count를 초기화한다.

 

    elif i == '.':
        if count == 0:
            answer += '.'
        elif count == 2:
            answer += "BB."
            count = 0
        else:
            answer = -1
            break

.이라면 count가 0이거나(바로 전에 AAAA를 추가한 경우 또는 첫 문자가 .인경우)
count가 2인 경우(BB.를 넣을 수 있는 상황)을 확인하여 문자열에 BB. 또는 .을 추가했다.
만약 .을 만났을 때 count가 2나 0이 아닌 경우는 BB로 다 채울 수 없기 때문에 모두 덮지 못하는 문자열이 된다.

 

if count == 2:
    answer += "BB"
elif count > 0:
    answer = -1


print(answer)

문자열 판별이 끝난 이후
나올 수 있는 count는 0, 1, 2, 3뿐이다. (4이상인 경우는 이미 AAAA가 들어가고 0으로 초기화 되었다.)
0이나 2인 경우는 문자열 치환 종료, 또는 BB를 넣으면 되지만 1이거나 3이면 모두 덮지 못하는 문자열이 된다.

 

 

전체 코드

import sys

input_string = sys.stdin.readline()

count = 0
answer = ""

for i in input_string:
    if i == 'X':
        count += 1
        if count == 4:
            answer += "AAAA"
            count = 0
    elif i == '.':
        if count == 0:
            answer += '.'
        elif count == 2:
            answer += "BB."
            count = 0
        else:
            answer = -1
            break

if count == 2:
    answer += "BB"
elif count > 0:
    answer = -1


print(answer)

단순 구현문제로 그리디 알고리즘을 이용하면 풀 수 있었다.