22877번 - 가위바위보 버블 정렬 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 361 | 133 | 113 | 53.810% |
문제
이환이는 4차 산업혁명 시대에 살고 있는 천재 5살 아기이다. 가위바위보를 즐기는 이환이는 집에서도 혼자 가위바위보를 하고 싶어서 창의력을 발휘해 카드를 이용한 게임을 만들었다. 게임을 하려면 먼저 '가위', '바위' 또는 '보'가 그려진 카드 $N$장을 일렬로 나열해 놓아야 한다. 그러고 나서, 가장 왼쪽에 있는 카드부터 차례대로 보면서 만약 그 카드가 바로 오른쪽에 있는 카드를 이긴다면 두 카드의 위치를 바꾸고, 그렇지 않다면 그대로 두는 것을 반복한다. 이렇게 마지막에서 두 번째 카드까지 한 번씩 훑어보면 놀이 한 번이 끝난다.
이환이는 이 놀이의 과정이 버블 정렬과 비슷하기 때문에 '가위바위보 버블 정렬'이라고 부르기로 했다. 카드의 승패 관계는 다음과 같다.
- '가위'가 그려진 카드는 '보'가 그려진 카드를 이긴다.
- '바위'가 그려진 카드는 '가위'가 그려진 카드를 이긴다.
- '보'가 그려진 카드는 '바위'가 그려진 카드를 이긴다.
계산이 아주 빠른 이환이는 이 놀이를 무려 $T$번이나 했다! 피곤해진 이환이는 내일 이 놀이를 계속하기로 하고 잠을 자러 가려고 했으나, 카드 위를 지나가다 그만 카드들이 뒤섞여 버렸다. 이환이는 뛰어난 기억력을 가진 천재이기 때문에 맨 처음 카드들의 배열을 기억해 냈지만, 마지막 카드 배열은 기억하지 못했다. 놀이를 $T$번 한 후의 배열을 복원해서 이환이를 도와 주자.
입력
첫 번째 줄에는 카드의 개수 $N$($ 2 \leq N \leq 500\ 000 $)과 놀이를 한 횟수 $T$($1 \leq T \leq 1\ 000\ 000\ 000$)가 주어진다.
두 번째 줄에는 맨 처음 카드들의 배열을 나타내는 길이 $N$의 문자열이 주어진다. $i$번째 문자는 $i$번째 위치에 놓인 카드의 종류를 나타낸다. '가위'가 그려진 카드는 S, '바위'가 그려진 카드는 R, '보'가 그려진 카드는 P이다.
출력
$T$번 놀이를 한 후 카드들의 배열을 길이 $N$의 문자열로 출력한다. 마찬가지로 '가위'는 S, '바위'는 R, '보'는 P이다.
예제 입력 1
5 1 RSPSP
예제 출력 1
SRPPS
예제 입력 2
10 3 RSRRRRRRSR
예제 출력 2
SRRRRSRRRR
노트
첫 번째 예제에서, 이환이는 한 번의 놀이를 한다.
- 첫 번째 카드
R(바위)은 두 번째 카드S(가위)를 이기므로 두 카드를 서로 바꾼다. 이때 배열은SRPSP가 된다. - 두 번째 카드
R(바위)은 세 번째 카드P(보)에게 지므로 위치를 바꾸지 않는다. - 세 번째 카드
P(보)는 네 번째 카드S(가위)에게 지므로 위치를 바꾸지 않는다. - 네 번째 카드
S(가위)는 마지막 카드P(보)를 이기므로 두 카드를 서로 바꾼다. 이때 배열은SRPPS가 된다.
따라서 놀이가 끝난 후 카드들의 배열은 SRPPS이다.
두 번째 예제에서, 이환이는 세 번의 놀이를 한다. 각 놀이가 끝난 후 카드들의 배열은 다음과 같이 변한다.
RSRRRRRRSR $\rightarrow$ SRRRRRRSRR $\rightarrow$ SRRRRRSRRR $\rightarrow$ SRRRRSRRRR
따라서 놀이가 끝난 후 카드들의 배열은 SRRRRSRRRR이다.
출처
University > 전국 대학생 프로그래밍 대회 동아리 연합 > UCPC 2021 E번
Contest > Open Cup > 2021/2022 Season > Stage 17: Grand Prix of Seoul E번
- 문제를 검수한 사람: ainta, cki86201, doju, evenharder, functionx, jh05013, koosaga, pichulia, taeyeon_ss, xiaowuc1
- 문제를 만든 사람: benedict0724
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호