[백준] 1343번 폴리오미노 (파이썬)

문제

 

1343번: 폴리오미노

 

 

풀이 (Python)

 

arr=list(input())

def poli():
    count=0
    for i in range(len(arr)):           #x의 개수가 4개 연속으로 있다면 A로 대체하기 위한 for문
        if arr[i]=="X": count+=1
        else:   count=0

        if count==4:
            for j in range(4):
                arr[i-j]="A"
            count=0

    count=0

    for i in range(len(arr)):       #x의 개수가 3개가 남아있는 case가 있다면 false리턴을 위한 for문
        if arr[i]=="X": count+=1
        else:   count=0
        if count==3:    return False



    for i in range(len(arr)-1):         #x의 개수가 2개 연속 xx가 있는경우 BB로 대체 하기 위한 for문
        if arr[i]=="X" and arr[i+1]=="X":
            arr[i],arr[i+1]="B","B"


    if "X" in arr:                  #모든 경우의 수를 전부 지웠음에도 X가 남아있다면, false리턴
        return False
    return True

if poli():          #poli함수가 정상적으로 종료된 경우
    print(*arr,sep="")
else:               #만들 수 없는 경우 poli함수가 false를 리턴하여 -1출력을 하기 위함
    print(-1)

 

 

설명  (Python)

 

폴리오미노 문제의 경우 "XX.XX"과 같은 입력을 받을 때 XX는 BB, XXXX는 AA로 대치하는 그리디알고리즘 문제이다.

파이썬의 특성상 다른 c계열 언어와 같이 다른 언어에 비해 문자열을 변경하거나 연산할 때 제약이 많이 없으므로, 쉬운 문제이다.

 

필자는 쉽게 풀이하기 위해 X가 4개 연속 나오는 경우부터 X가 1개 남은 경우까지 순서대로 진행하였다.

1. X가 4개인 경우 A로 대치
2. X가 3개인 경우 불가
3. X가 2개인 경우 B로 대치
4. X가 1개인 경우 불가

 

1.X가 4개인 경우 A로 대치

 

    for i in range(len(arr)):           #x의 개수가 4개 연속으로 있다면 A로 대체하기 위한 for문
        if arr[i]=="X": count+=1
        else:   count=0

        if count==4:
            for j in range(4):
                arr[i-j]="A"
            count=0

 

간단하게 count를 이용하여 X면 +1. 인경우 리셋하여 X가 4개인 경우 현 i부터 i-3까지 모두 A로 대치해 주었다.

 

 

 

 

 

2. X가 3개인 경우 불가

 

    for i in range(len(arr)):       #x의 개수가 3개가 남아있는 case가 있다면 false리턴을 위한 for문
        if arr[i]=="X": count+=1
        else:   count=0
        if count==3:    return False

 

x가 4개인 경우를 이미 다 처리를 하였기 때문에 X가 3개 연속 나온다면 XX는 B로 바뀐 후 X한개만 존재하게 되어 문제를 만족하지 못한다. 이와 같은 경우는 -1을 처리하기 위해 return False로 함수 탈출 후

 

if poli():          #poli함수가 정상적으로 종료된 경우
    print(*arr,sep="")
else:               #만들 수 없는 경우 poli함수가 false를 리턴하여 -1출력을 하기 위함
    print(-1)

 

if 함수리턴값을 통해 불가능한 경우 -1을 출력을 하는 else문으로 접근하게 된다.

 

 

 

3. X가 2개인 경우 B로 대치

    for i in range(len(arr)-1):         #x의 개수가 2개 연속 xx가 있는경우 BB로 대체 하기 위한 for문
        if arr[i]=="X" and arr[i+1]=="X":
            arr[i],arr[i+1]="B","B"

 

1번 경우와 조금 다르게 count를 사용할 필요 없이

for문의 끝을 len(arr)-1로 조절하고 i와 i+1의 경우를 동시 비교하여 대치해 주었다.

 

4. X가 1개인 경우 불가

 

    if "X" in arr:                  #모든 경우의 수를 전부 지웠음에도 X가 남아있다면, false리턴
        return False

 

XXXX일 때 AAAA로 바꾸고,  XX가 있는 경우 BB로 바꾼 상태에 아직도 X가 존재한다면,  X가 한 개 남아 있는 경우로 이때에는 False를 리턴하여 예외처리 해주었다.