[python] 2469 - 사다리 타기

2469번: 사다리 타기 (acmicpc.net)

2469번: 사다리 타기

 

접근을 잘못했던 문제였다.

?로 주어지는 가로줄을 추측할 때에

['*', '-']에서 가로줄 크기 만큼 고르는 중복 순열로 접근을 했더니

문제가 굉장히 복잡해졌다.

 

더욱이 사다리 모양이 헷갈려서..

결국 구글 검색을 통해 풀이를 찾아보고 말았다.

 

그랬더니 엄청나게 간단한 풀이가 있었다.

왜 진작 이렇게 생각을 못했을까?

 

?가 나오는 배열 이전과 이후로 나눠 바로 직전의 문자 배열을 구한 후

'-'에 따라 문자 배열의 위치를 바꿔주면 ?의 모양을 간단하게 알 수 있다.

 

 

# 2469 사다리 타기
import sys

input = sys.stdin.readline

n = int(input())
m = int(input())
final = list(map(str, input().strip()))
start = sorted(final)

left = 0
right = []

for _ in range(m):
    ladder = list(map(str,input().strip()))
    
    if ladder == ['?' for _ in range(n-1)]:
        left = right
        right = []
        continue
    right.append(ladder)

while left:
    ladder = left.pop(0)
    for i in range(n-1):
        if ladder[i] == '-':
            start[i], start[i+1] = start[i+1], start[i] 

while right:
    ladder = right.pop()
    for j in range(n-1):
        if ladder[j] == '-':
            final[j], final[j+1] = final[j+1], final[j]
            
ans = ['*' for _ in range(n-1)]
for k in range(n-1):
    if start[k] == final[k+1] and start[k+1] == final[k]:
        ans[k] = '-'
        start[k], start[k+1] = start[k+1], start[k]
        
if start != final:
    ans = ['x' for _ in range(n-1)]
print(''.join(ans))

 

* 참고 [백준] 2469. 문자열_사다리타기 - Python (tistory.com)

* 모든 코드는 github에서 관리합니다.  seinShin (SEIN SHIN) (github.com)

seinShin - Overview