루미 알고리즘

#1129실버가위바위보가위바위보

KOI 2026 1차코딩초등부 2번출제 이유찬이 문제가 어렵다면 — 배우는 순서 보기

원문 PDF 의 글을 화면용으로 옮겼습니다. 내용이 다르면 원문이 맞습니다. (검수일 2026-11-20)

가위바위보

원제: 가위바위보

문제

11번부터 NN번까지 번호가 부여된 NN명의 사람이 일렬로 서 있다. ii (1≤i≤N1 \le i \le N)번 사람은 왼쪽에서 ii번째에 서 있으며, 하나의 카드 AiA_i를 가지고 있다. 각 카드는 가위(S), 바위(R), 보(P) 중 하나이다.

서로 다른 두 사람 사이에 다른 사람이 없다면, 그 두 사람은 서로 인접하다고 하자. 여러분은 인접한 두 사람을 골라 대결시킬 수 있다. 한 번의 대결은 다음과 같이 진행된다.

  • 두 사람의 카드가 서로 다르면, 가위바위보 규칙에 따라 승자가 결정된다. 즉, 바위(R)는 가위(S)를 이기고, 가위(S)는 보(P)를 이기고, 보(P)는 바위(R)를 이긴다.
  • 두 사람의 카드가 같으면, 여러분이 승자를 임의로 정할 수 있다.
  • 패자는 퇴장하며, 승자는 자신의 카드를 그대로 유지한 채 그 자리에 남는다. 퇴장으로 인해 새롭게 인접해지는 두 사람이 생길 수 있으며, 두 사람은 이후 대결을 할 수 있다.

여러분은 정확히 N−1N - 1번의 대결을 진행하여 단 한 명의 우승자만 남기려 한다. 각 사람에 대해, 그 사람이 우승자가 될 수 있도록 대결하는 방법이 존재하는지 판별하는 프로그램을 작성하라.

제약 조건

  • 1≤N≤200 0001 \le N \le 200\,000
  • AA는 영어 알파벳 대문자 S, R, P로만 이루어진 길이 NN의 문자열이다.

부분문제

  1. (13점) N≤3N \le 3
  2. (16점) 문자열 AA는 최대 두 종류의 문자로만 이루어져 있다.
  3. (47점) N≤100N \le 100
  4. (31점) N≤5 000N \le 5\,000
  5. (43점) 추가 제약 조건 없음.

입력 형식

첫 줄에 정수 NN이 주어진다.

그다음 줄에 길이 NN의 문자열 AA가 주어진다. AA의 ii번째 문자 AiA_i는 ii번 사람이 가진 카드를 나타내며, 영어 알파벳 대문자 S, R, P 중 하나이다 (1≤i≤N1 \le i \le N).

출력 형식

첫 줄에 길이 NN의 문자열을 출력한다. 이 중 ii번째 문자는, ii번 사람이 우승자가 될 수 있다면 1, 아니면 0이어야 한다 (1≤i≤N1 \le i \le N).

예제

예제 1

입력
3
RPP
출력
011

22번과 33번을 먼저 대결시키면 두 사람의 카드가 같으므로, 여러분이 임의로 승자를 정할 수 있다. 22번을 승자로 정했다면, 남은 11번과 22번이 대결하면 보(P)가 바위(R)를 이기므로, 22번이 우승자가 될 수 있다.

22번과 33번을 대결시켜 33번을 승자로 정한 후, 11번과 대결시키면, 33번이 우승자가 될 수 있다.

바위(R)는 보(P)를 이길 수 없으므로, 11번은 절대로 우승자가 될 수 없다.

예제 2

입력
3
RPS
출력
101

22번과 33번을 먼저 대결시키면 가위(S)가 보(P)를 이겨 33번이 이긴다. 남은 11번과 33번이 대결하면 바위(R)가 가위(S)를 이기므로, 11번이 우승자가 될 수 있다.

11번과 22번을 먼저 대결시키면 보(P)가 바위(R)를 이겨 22번이 이긴다. 남은 22번과 33번이 대결하면 가위(S)가 보(P)를 이기므로, 33번이 우승자가 될 수 있다.

22번은 절대로 우승자가 될 수 없다.

자료

출처 표기

출처: 한국정보올림피아드(KOI) 2026년 1차 대회 · 원문 페이지 · 이용 조건 CC BY-NC-SA 4.0 · 원문 그대로 실었으며 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-비영리-동일조건변경허락 4.0 국제. 비영리 목적으로만 이용할 수 있습니다.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.