[Python/코테] 백준 13413 오셀로 재배치

13413 오셀로 재배치 

문제 및 조건 설명: https://www.acmicpc.net/problem/13413

 

알고리즘 설계

💡idea.

가능한 동작은 '바꿔치기' 또는 '뒤집기'이다. 이 때 바꿔치기는 한 번에 두 말을 바꿀 수 있으므로, 최소 횟수를 구하기 위해서는 최대한 바꿔치기를 해주고, 남는 것들을 뒤집어 주어야 한다.

초기 말 상태를 순회하면서 이 바꿔치기를 바로바로 해결할 수 있는데, 나는 별도의 stack 변수를 이용했다. 

stack은 기존에 있던 말을 꺼내오고, 바꿔치기가 가능하다면 바로 삭제하는 연산이 쉽다. (pop으로 한 번에!)

 

🎲step.

1. 초기 상태 말을 순회하며, 바꿔야 하는 말이 있으면 검사를 시작한다.

2. 바꿔야 하는 말을 저장하는 stack 변수에 있던 말과 '바꿔치기'가 가능하다면, 곧장 해준다.

    '바꿔치기'가 바로 안되면 같은 색의 말이라는 뜻이다.

3. 1~2번을 반복하며 다른 색의 말이 들어올 때마다 '바꿔치기' 해준다.

4. 바꿔야 하는 말을 저장하는 stack 변수에는 서로 바꿔치기가 불가능한, 전부 같은 색상의 말만 모인다. 즉 길이를 횟수에 더해서 '뒤집기' 연산 횟수를 더한다. 

 

알고리즘 구현

from collections import deque

t = int(input())


def solution(N, arr, answer):
    count = 0
    change = deque()    # 바꿔야 하는 말을 담을 스택

    for i in range(N):
        if arr[i] != answer[i]:
            if change:
                piece = change.pop()
                if piece != arr[i]:     # 바꿔치기가 가능하면
                    count += 1
                else:
                    change.append(piece)    # 꺼낸 말 다시 넣어주기
                    change.append(arr[i])   # 이번 말도 추가해주기
            else:
                change.append(arr[i])

    count += len(change)
    
    return count


for _ in range(t):
    n = int(input())
    arr = input()
    answer = input()

    print(solution(n, arr, answer))

나다어

• 배열 순회는, 요소를 하나씩 검사할 수 있는 기회이기도 하다. 바로 해결할 수 있는 문제들은 다시 순회할 필요 없이 바로 동작이 가능한 것.