Misfits 아카데미

 

Python 구현 시뮬레이션 나머지 연산 Silver

Misfits 아카데미 — 종이 방향과 나머지 연산 풀이

원형 종이 전달 시뮬레이션에서 나쁜 말을 쓴 아이를 찾아라

n명의 아이들이 원형으로 앉아 종이를 왼쪽으로 돌리며 메시지를 씁니다.
N(나쁜 메시지)을 발견하면 누가 썼는지 역추적하는 문제입니다.
핵심은 "종이 전달 방향"과 "나머지 연산"으로 작성자 인덱스를 정확히 계산하는 것입니다.

1. 문제 이해 & 접근법

처음 이 문제를 보면 활동의 서사에 집중하게 된다. 하지만 실제 로직으로 추상화하면 단순한 구조가 드러난다.

핵심 관찰

종이는 왼쪽으로 전달된다

입력 순서가 곧 왼쪽 방향이다. 0번 아이의 종이는 1번 → 2번 → ... → (n-1)번 순으로 전달된 뒤 0번에게 돌아온다.

자기 종이에 자기가 메시지를 쓰지 않는다

이름을 적자마자 왼쪽으로 넘기기 때문에, 종이에는 항상 n-1개의 메시지만 존재한다.

어떻게 접근할까?

1

i번 종이의 j번째 메시지(0-indexed)를 쓴 사람의 인덱스를 구한다

2

메시지가 N이면 → "작성자 was nasty about 종이주인" 기록

3

종이 순서대로, 왼쪽→오른쪽 순으로 출력

💡 핵심 공식
i번 종이의 j번째 메시지를 쓴 사람 = (i - j - 1) % n
종이는 왼쪽으로 전달되므로, 먼저 쓴 사람은 주인 바로 왼편(= 인덱스가 하나 작은 쪽)에서 온다.

2. 실제 입출력 분석

전체 입출력

# 입력
5
Ann P N P P
Bob P P P P
Clive P P P P
Debby P N P P
Eunice P P P P
6
Zheng P P P P P
...
0

# 출력
Group 1
Clive was nasty about Ann   # ← 실제 정답과 다름! 방향 확인 필요
Ann was nasty about Debby

Group 2
Nobody was nasty

그룹 1 상세 분석 (n = 5)

아이들 순서: Ann(0), Bob(1), Clive(2), Debby(3), Eunice(4)

Ann(0)의 종이: P N P P

Ann 종이는 왼쪽으로 전달되므로, 먼저 받는 쪽은 인덱스가 작은 방향 → Eunice(4) → Debby(3) → Clive(2) → Bob(1) 순서로 메시지를 작성한다.

j (메시지 순서)	공식 (0 - j - 1) % 5	작성자	메시지
0	(0-0-1)%5 = 4	Eunice	P
1	(0-1-1)%5 = 3	Debby	N ← 나쁜 말!
2	(0-2-1)%5 = 2	Clive	P
3	(0-3-1)%5 = 1	Bob	P

→ Debby was nasty about Ann

Debby(3)의 종이: P N P P

Debby 종이 전달 순서: Clive(2) → Bob(1) → Ann(0) → Eunice(4)

j (메시지 순서)	공식 (3 - j - 1) % 5	작성자	메시지
0	(3-0-1)%5 = 2	Clive	P
1	(3-1-1)%5 = 1	Bob	N ← 나쁜 말!
2	(3-2-1)%5 = 0	Ann	P
3	(3-3-1)%5 = 4	Eunice	P

→ Bob was nasty about Debby

3. 핵심 아이디어 — 전달 방향과 나머지 연산

공식	의미
(i - j - 1) % n	i번 종이의 j번째 메시지 작성자
i - 1	첫 번째 메시지 작성자 (왼쪽 바로 옆)
% n	원형 구조 처리 (음수 인덱스도 올바르게 처리)

⚠️ 방향 주의
"왼쪽으로 전달"은 인덱스가 감소하는 방향이다.
처음에 (i + j + 1) % n으로 계산하면 방향이 반대가 되어 틀린다.
반드시 (i - j - 1) % n을 사용할 것!

4. 전체 코드

import sys
input = sys.stdin.readline

group = 1
results_all = []

while True:
    n = int(input())
    if n == 0:
        break

    papers = []
    names = []
    for _ in range(n):
        line = input().split()
        names.append(line[0])
        papers.append(line[1:])

    results = []
    for i in range(n):           # i = 종이 주인 인덱스
        for j in range(n - 1):    # j = 메시지 순서
            if papers[i][j] == 'N':
                writer = (i - j - 1) % n   # 작성자 인덱스
                results.append(
                    f"{names[writer]} was nasty about {names[i]}"
                )

    results_all.append((group, results))
    group += 1

# 모든 그룹 읽은 후 출력 (마지막 그룹 뒤 빈 줄 없음)
for idx, (g, results) in enumerate(results_all):
    print(f"Group {g}")
    if results:
        for r in results:
            print(r)
    else:
        print("Nobody was nasty")
    if idx < len(results_all) - 1:
        print()

5. 알고리즘 흐름

1

n 입력 — n이 0이면 종료, 아니면 해당 그룹을 처리한다.

2

n줄 이름·메시지 읽기 — split()으로 이름과 메시지를 분리해 저장한다.

3

N 탐색 — i번 종이의 j번째 메시지가 N이면 작성자 = (i - j - 1) % n.

4

결과 저장 — 모든 그룹을 읽은 뒤 한 번에 출력해 마지막 빈 줄 문제를 방지한다.

5

그룹 출력 — N이 없으면 Nobody was nasty, 그룹 사이에만 빈 줄을 삽입한다.

🗂 핵심 정리

항목	내용
전달 방향	왼쪽 = 인덱스 감소 방향
작성자 공식	(i - j - 1) % n
메시지 수	종이당 n-1개 (자기 자신 제외)
출력 순서	종이 순서대로, 각 종이 내 왼쪽→오른쪽
빈 줄	그룹 사이에만 삽입, 마지막 그룹 뒤엔 없음
시간 복잡도	O(n²) — 모든 종이의 모든 메시지 확인

전체 흐름 요약: 이름·메시지 읽기 → i번 종이 j번째 N 발견 → (i-j-1)%n으로 작성자 계산 → 결과 출력