[백준] 22877번 가위바위보 버블 정렬 (Python3)

 

 

출처

https://www.acmicpc.net/problem/22877

22877번: 가위바위보 버블 정렬

 

문제

이환이는 4차 산업혁명 시대에 살고 있는 천재 5살 아기이다. 가위바위보를 즐기는 이환이는 집에서도 혼자 가위바위보를 하고 싶어서 창의력을 발휘해 카드를 이용한 게임을 만들었다. 게임을 하려면 먼저 '가위', '바위' 또는 '보'가 그려진 카드 N장을 일렬로 나열해 놓아야 한다. 그러고 나서, 가장 왼쪽에 있는 카드부터 차례대로 보면서 만약 그 카드가 바로 오른쪽에 있는 카드를 이긴다면 두 카드의 위치를 바꾸고, 그렇지 않다면 그대로 두는 것을 반복한다. 이렇게 마지막에서 두 번째 카드까지 한 번씩 훑어보면 놀이 한 번이 끝난다.

이환이는 이 놀이의 과정이 버블 정렬과 비슷하기 때문에 '가위바위보 버블 정렬'이라고 부르기로 했다. 카드의 승패 관계는 다음과 같다.

• '가위'가 그려진 카드는 '보'가 그려진 카드를 이긴다.
• '바위'가 그려진 카드는 '가위'가 그려진 카드를 이긴다.
• '보'가 그려진 카드는 '바위'가 그려진 카드를 이긴다.

계산이 아주 빠른 이환이는 이 놀이를 무려 T번이나 했다! 피곤해진 이환이는 내일 이 놀이를 계속하기로 하고 잠을 자러 가려고 했으나, 카드 위를 지나가다 그만 카드들이 뒤섞여 버렸다. 이환이는 뛰어난 기억력을 가진 천재이기 때문에 맨 처음 카드들의 배열을 기억해 냈지만, 마지막 카드 배열은 기억하지 못했다. 놀이를 T번 한 후의 배열을 복원해서 이환이를 도와 주자.

 

코드

import sys

def solution(n, t, strCard):
    cardList = list(strCard)


    repeatCount = 1 #i번째 카드의 반복횟수
    for i in range(len(cardList) - 1):

        #i번째 카드가 이겼을 경우
        if isWin(cardList[i], cardList[i + 1]):
            replaceIndex = 0
            if repeatCount < t:
                replaceIndex = i + 1 - repeatCount
            else:
                replaceIndex = i + 1 - t

            #(replaceIndex, i + 1)번째 카드 스왑
            tmp = cardList[replaceIndex]
            cardList[replaceIndex] = cardList[i + 1]
            cardList[i + 1] = tmp

        #비겼을 경우
        elif cardList[i] == cardList[i + 1]:
            repeatCount += 1
            
        #졌을 경우
        else:
            repeatCount = 1

    return ''.join(cardList)


def isWin(left, right):
    winCondition = ''
    
    if left == 'S':
        winCondition = 'P'
    elif left == 'R':
        winCondition = 'S'
    elif left == 'P':
        winCondition = 'R'

    if right == winCondition:
        return True
    else:
        return False

#main
newLine = sys.stdin.readline

NT = newLine().split()
strCard = newLine().strip()

N = int(NT[0])
T = int(NT[1])

result = solution(N, T, strCard)

print(result)

 

코드 설명

카드 위치가 바뀔 수 있는 경우는 다음과 같다.

SP → PS

RS → SR

PR → RP

 

만약 첫 번째 놀이에서 SP → PS로 카드 교환이 일어난다고 한다면, 두 번째 놀이에서 다시 교환이 일어나기 위해서는 반드시 PS의 앞과 뒤에 SPS 또는 PSP의 형태로 카드 배열이 구성되어 있어야 교환이 발생할 수 있다. (SPS → PSS, PSP → PPS)

두 번째 놀이에서 SPS, PSP의 형태가 되기 위해서는 첫 번째 놀이전의 기존 배열이 SSP 또는 SPP 형태여야만 한다.

따라서 기존의 카드 배열에서 SS, PP와 반복되는 부분이 존재해야만 두 번째 놀이에서 카드 교환이 발생할 수 있다는 것을 알 수 있으며, 두 번째 놀이부터는 기존 카드배열이 반복되는 부분만 고려하면 된다는 것을 유추할 수 있다.

예를들어, SPRSSSSSSP의 카드 배열이 주어졌을 때 첫번째 놀이 이후 PSRSSSSSPS의 카드 배열이 되며 그 다음 배열부터는 PSRSSSSPSS, PSRSSSPSSS와 같이 앞부분의 PSR은 유지되고 뒷부분은 처음 배열형태의 SSSSSSP에서 P만 앞으로 한칸씩 이동하게 된다.

 

알고리즘 분류

- 애드 혹

      

테스트 케이스

▶ 입력

5 10

PPPRR

 

▶ 출력: RRPPP