Baekjoon 32034. 동전 쌍 뒤집기 / Python

32034. 동전 쌍 뒤집기

난이도 : 플래티넘 5
소요 시간 : 25분
날짜 : 2025.01.02
언어 : 파이썬
알고리즘 유형 : 스택, 그리디

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. N개의 동전이 일렬로 놓여있다.
2. 조작을 원하는대로 할 수 있다.
   • 서로 이웃하고, 같은 면인, 두 개의 동전을 둘 다 뒤집기
3. 모든 동전이 앞면이 보이게 할 수 있는가? 가능하다면 최소 조작횟수를 구하라.

2. 해결 방식

자료구조 : 스택을 활용한다.

1. 먼저 뒷면의 위치를 저장하고 개수를 센다.
2. 뒷면의 개수가 2로 나누어지지 않으면 불가능, 0이면 답이 0
3. 뒷면인 동전들을 돌면서 스택을 활용한다.
   • 스택이 비어있다면 스택에 넣기
   • 스택의 마지막 요소와 현재 요소의 인덱스 차이가 짝수라면, 가운데의 앞면을 다 뒤집고 다시 뒷면으로 다 뒤집으면 모두 앞면이 되므로, 스택에서 pop()해주고, 인덱스 차이만큼 결과값에 더해주기
   • 스택의 마지막 요소와 현재 요소의 인덱스 차이가 홀수라면, 스텍에 넣기

3. 정답 코드

import sys; input = sys.stdin.readline

def sol(s):
    t_loc = []
    res = 0
    for i, c in enumerate(s):
        if c == 'T':
            t_loc.append(i)

    size = len(t_loc)
    if size % 2:
        print(-1)
        return 
    if not size:
        print(0)
        return 

    stack = []
    for i in range(size):
        if not stack:
            stack.append(i)
            continue

        j = stack[-1]
        if (t_loc[i] - t_loc[j]) % 2:
            res += (t_loc[i] - t_loc[j])
            stack.pop()
        else:
            stack.append(i)

    print(-1 if stack else res)


for _ in range(int(input())):
    _, S = input(), input().strip()
    sol(S)