[알고리즘/그리디] 1343번 : 폴리오미노 - python

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

1343번: 폴리오미노

 

---

• 문제
• 소요시간: 21분 36초

---

• 설계하기(접근방법) 

1. 입력받기

문자열을 입력받는다

 

2. 구현하기

구현 문제를 많이 풀다보니 그대로 구현해버렸다.

파이썬의 replace 함수를 사용하면 매우 쉽게 풀 수 있지만 구현한 내용은 다음과 같다

 

앞에서부터 X의 개수를 세서 리스트에 넣는다

'.'도 '.'으로 리스트에 넣어준다

 

리스트를 순회하며

int인 경우 4의 배수 이면

'AAAA'를 

 

아니라면

'AAAA'를 4로 나눈 몫만큼 출력 후

'BB'를 출력한다

 

'.'인 경우

'.'을 출력한다

 

만약 홀수가 있다면 -1 만 출력해준다

 

3. 출력하기 

구현한 내용과 같다

 

 

---

• 코드(출력)

n = input()

cnt = 0
ABlist =[]

for i in range(len(n)):
    if n[i] == 'X':
        cnt += 1
        if i == len(n) - 1:
            ABlist.append(cnt)
    elif n[i] == '.' and cnt > 0:
        ABlist.append(cnt)
        cnt = 0
        ABlist.append('.')
    elif n[i] == '.' and cnt == 0:
        ABlist.append('.')

checker = 0

for i in ABlist:
    for j in ABlist:
        if type(j) == int:
            if j % 2 != 0:
                print(-1)
                checker = 1
                break
    if checker == 1: 
        break
    if type(i) == int:
        if i % 4 == 0:
            print('AAAA' * (i // 4), end= '') 
        else:
            print('AAAA' * (i // 4), end= '') 
            print('BB', end= '')
    else:
        print(i, end = '')

 

n = input()

n = n.replace('XXXX','AAAA')
n = n.replace('XX', 'AA')

if 'X' in n:
	print(-1)
else:
	print(n)

 

---

• 얻어갈 부분

1. 다른 풀이를 보니 replace 함수를 통해 상당히 쉽게 구현하였다. 다른 문제에서 replace를 사용해 시간을 단축해보자