페이스메이커 짝 세기
문제
달리기 모임에 N명이 있다. 모임은 M번의 기록회를 열었고, 기록회마다 결승선에 들어온 순서를 기록했다.
모임은 실력 차가 분명한 두 사람을 짝지어 앞선 사람이 페이스메이커, 뒤처진 사람이 따라 뛰는 사람이 되게 하려 한다. A가 B의 페이스메이커가 되려면 M번의 기록회 모두에서 A가 B보다 먼저 들어왔어야 한다.
만들 수 있는 (페이스메이커, 따라 뛰는 사람) 짝이 모두 몇 가지인지 센다.
- 1 ≤ N ≤ 20, 1 ≤ M ≤ 10
- 입력: 첫 줄에 N과 M. 둘째 줄부터 M줄에 걸쳐 각 기록회의 결과가 들어온 순서대로 선수 번호로 주어진다. 예를 들어
3 4 1 2는 3번이 1등, 4번이 2등, 1번이 3등, 2번이 4등이라는 뜻이다. - 출력: (페이스메이커, 따라 뛰는 사람) 짝의 개수
입력 출력
5 3 3
2 1 4 3 5
2 1 5 4 3
3 1 4 2 5
2번은 세 기록회 모두 5번보다 먼저 들어왔으므로 (2, 5)는 짝이 된다. 1번은 4번과 5번보다 매번 앞섰으므로 (1, 4), (1, 5)도 짝이다. 2번과 1번은 첫 두 번은 2번이 앞섰지만 세 번째에 1번이 앞서서 짝이 아니다. 따라서 3가지.
출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비의 1121번 문제를 소재와 예제만 바꿔 재구성했다.
공통 코드
아래 시도들은 입력을 읽는 부분을 공유한다. 각 시도에서는 짝을 세는 부분만 보여준다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
// race[r][p] = r번째 기록회에서 p등으로 들어온 선수 번호 (r, p 모두 0부터)
int[][] race = new int[m][n];
for (int r = 0; r < m; r++)
for (int p = 0; p < n; p++)
race[r][p] = sc.nextInt();
int answer = 0;
// ... 짝을 세는 부분 (각 시도 참고)
System.out.println(answer);
}
}
시도 1 — 입력을 거꾸로 읽음
접근
race[r][p]를 “선수 p+1의 등수”로 읽었다. 그러면 값이 작을수록 앞선 것이니, 두 선수 a, b에 대해 모든 기록회에서 race[r][a] < race[r][b]인지 세면 된다고 생각했다.
for (int a = 0; a < n; a++) {
for (int b = 0; b < n; b++) {
if (a == b) continue;
int ahead = 0;
for (int r = 0; r < m; r++)
if (race[r][a] < race[r][b]) ahead++;
if (ahead == m) answer++;
}
}
결과
실패 — 예제에서 7을 출력. 정답은 3.
분석
입력 형식을 잘못 읽었다. 한 줄은 “선수별 등수”가 아니라 “등수 순으로 나열한 선수 번호”다. 즉 race[r][p]에서 인덱스 p가 등수, 값이 선수 번호다. 위 코드는 인덱스를 선수로, 값을 등수로 거꾸로 해석한 셈이라 전혀 다른 것을 세고 있었다.
문제를 다시 읽고 나서야 보였다. 선수 a가 r번째 기록회에서 몇 등인지 알려면, 값이 a인 칸을 찾아서 그 인덱스를 봐야 한다.
시도 2 — 등수를 찾아 비교, 플래그 없이
접근
입력을 바로 읽었으니 이제 두 선수의 등수를 비교한다. 각 기록회에서 두 선수의 위치(o, e)를 찾아, 페이스메이커 쪽이 앞(o < e)이면 다음 기록회로, 아니면 break한다.
쌍은 첫 기록회의 순서로 잡았다. race[0]에서 앞에 있는 선수를 leader, 뒤에 있는 선수를 follower로 두면 첫 기록회 조건은 자동으로 만족하므로, 나머지 기록회(r = 1부터)만 확인하면 된다.
for (int j = 0; j < n; j++) {
int leader = race[0][j];
for (int k = j + 1; k < n; k++) {
int follower = race[0][k];
for (int r = 1; r < m; r++) {
int o = 0, e = 0;
for (int p = 0; p < n; p++) {
if (race[r][p] == leader) o = p;
if (race[r][p] == follower) e = p;
}
if (o >= e) break;
answer++;
}
}
}
결과
실패 — 예제에서 11을 출력. 정답은 3.
분석
answer++가 기록회 루프 안에 있다. 그래서 한 쌍이 어떤 기록회를 통과할 때마다 1씩 올라간다. 모든 기록회를 통과한 쌍은 M−1만큼 더해지고, 중간에 떨어진 쌍도 떨어지기 전까지 통과한 횟수만큼 더해진다. 문제는 “짝이 몇 가지“인데 이 코드는 “조건을 통과한 횟수“를 세고 있다.
break로 실패는 막았지만, “모든 기록회에서”가 참이었는지를 기록회 루프가 끝난 뒤에 알 길이 없다. 루프를 빠져나온 게 끝까지 돌아서인지, break로 끊겨서인지 구분할 변수가 필요하다.
시도 3 — 플래그로 “모든 기록회” 판정 (채택)
접근
구조는 시도 2와 같고, answer++를 기록회 루프 밖으로 꺼냈다. 루프 앞에서 flag = true로 두고, 한 번이라도 뒤처지면 false로 바꾸며 break한다. 루프가 끝난 뒤 flag가 그대로 true면 모든 기록회를 통과한 것이므로 그때 한 번만 센다.
for (int j = 0; j < n; j++) {
int leader = race[0][j];
for (int k = j + 1; k < n; k++) {
int follower = race[0][k];
boolean flag = true;
for (int r = 1; r < m; r++) {
int o = 0, e = 0;
for (int p = 0; p < n; p++) {
if (race[r][p] == leader) o = p;
if (race[r][p] == follower) e = p;
}
if (o >= e) {
flag = false;
break;
}
}
if (flag) answer++;
}
}
결과
성공 — 예제에서 3을 출력.
복잡도: 시간 O(N³M), 공간 O(1). 쌍 N²개마다 기록회 M개를 보고, 각 기록회에서 두 선수의 위치를 찾느라 N칸을 훑는다. N ≤ 20, M ≤ 10이라 최대 8만 번 정도로 충분히 작다.
race[0]의 순서로 쌍을 잡아 첫 기록회는 비교하지 않는다.k = j + 1부터 돌기 때문에 (leader, follower)가 뒤집힌 쌍은 애초에 만들어지지 않는다.o >= e면flag = false후break. 남은 기록회는 볼 필요가 없다.flag가true로 살아남은 쌍만answer++.
분석
“모든 기록회에서 앞선다”는 전칭 조건이다. 별 세기에서와 똑같이, 전칭 조건은 반례 하나로 거짓이 되므로 true로 시작해 반례를 만나면 false로 바꾸고, 루프가 끝난 뒤 값이 살아 있는지로 판정한다.
시도 2와의 차이는 딱 하나, 판정 시점이다. 시도 2는 기록회마다 “지금까지는 괜찮다”를 세어 버렸고, 시도 3은 기록회 루프가 다 끝난 뒤에 “끝까지 괜찮았나”를 한 번 본다. break가 조기 종료를 맡고, flag가 그 결과를 루프 밖으로 들고 나온다.
다른 방법 1 — 통과 횟수를 세어 M과 비교
시도 2를 고치는 길은 플래그만이 아니다. 기록회 루프 안의 answer++를 cnt++로 바꾸고, 루프가 끝난 뒤 통과 횟수가 전체 횟수와 같은지(cnt == m) 보면 된다. 강의 풀이가 이 방식이다. 쌍도 1회차 순서에 기대지 않고 번호 i, j로 모든 순서쌍을 돌며, 기록회도 M번 전부 본다.
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int cnt = 0;
for (int r = 0; r < m; r++) {
int pi = 0, pj = 0;
for (int p = 0; p < n; p++) {
if (race[r][p] == i) pi = p;
if (race[r][p] == j) pj = p;
}
if (pi < pj) cnt++;
}
if (cnt == m) answer++;
}
}
i, j는 배열 인덱스가 아니라 선수 번호라 1부터 N까지 돈다 — 안쪽에서 race[r][p] == i로 칸의 값과 비교하기 때문이다. 반면 r, p, pi, pj는 인덱스라 0부터다. 시도 3은 leader = race[0][j]처럼 인덱스로 돌며 값을 꺼내 썼기 때문에 루프 변수가 전부 0부터였다.
i == j인 쌍은 pi == pj라 cnt가 M에 못 미쳐 자연히 걸러진다. 복잡도는 시간 O(N³M), 공간 O(1)로 시도 3과 같지만, 순서쌍 N²개를 M번 전부 보므로 비교 횟수는 시도 3의 두 배가 넘는다.
- 얻는 것:
break도 플래그도 없어 제어 흐름이 단순하고, “왜r = 1부터인가”를 읽는 사람이 생각할 필요가 없다. - 치르는 것: 떨어진 쌍도 끝까지 세므로 조기 종료가 없고, 뒤집힌 쌍과 자기 자신까지 돈다.
- 플래그와
break를 피하고 싶거나, M이 작아 조기 종료의 이득이 없을 때 이쪽을 고른다.
다른 방법 2 — 등수표를 미리 만들기
시도 3은 두 선수의 위치를 찾느라 기록회마다 N칸을 훑는다. 입력을 읽을 때 “선수 → 등수” 표를 만들어 두면 위치 찾기가 O(1)이 된다.
// rank[r][x] = r번째 기록회에서 선수 x의 등수 (선수 번호는 1부터)
int[][] rank = new int[m][n + 1];
for (int r = 0; r < m; r++)
for (int p = 0; p < n; p++)
rank[r][race[r][p]] = p;
for (int j = 0; j < n; j++) {
int leader = race[0][j];
for (int k = j + 1; k < n; k++) {
int follower = race[0][k];
boolean flag = true;
for (int r = 1; r < m; r++) {
if (rank[r][leader] >= rank[r][follower]) {
flag = false;
break;
}
}
if (flag) answer++;
}
}
복잡도는 시간 O(N²M), 공간 O(NM). 안쪽의 위치 탐색이 사라져 시도 3보다 N배 빠르다. 이 문제 크기에서는 차이가 없지만, 시도 1에서 “선수 번호로 등수를 바로 찾고 싶었던” 그 직관을 표를 하나 더 만들어 실제로 구현한 셈이라 짚어 둘 만하다. N이 수백을 넘어가면 이쪽을 고른다.
정리
| 시도 | 핵심 | 복잡도 | 결과 |
|---|---|---|---|
| 1. 입력을 거꾸로 읽음 | 인덱스와 값을 바꿔 해석 | — | 오답 |
| 2. 플래그 없이 | answer++가 기록회 루프 안 |
— | 오답 — 짝의 개수가 아닌 통과 횟수 |
| 3. 플래그로 판정 (채택) | 루프 밖에서 flag가 살아 있으면 +1 |
O(N³M) | 정답 |
| 다른 방법 1. 횟수 == M | 통과 횟수를 세어 루프 밖에서 cnt == m |
O(N³M) | 정답, 플래그·break 없음 |
| 다른 방법 2. 등수표 | rank[r][선수]를 미리 만들어 O(1) 조회 |
O(N²M), 공간 O(NM) | 정답, N배 빠름 |
채택: 시도 3. 추가 공간 없이 정답을 내고, “모든 기록회에서”라는 조건이 flag 하나로 그대로 읽히며 첫 실패에서 바로 끝난다. 플래그를 피하고 싶으면 다른 방법 1, N이 커지면 다른 방법 2가 낫다.
- 입력 설명을 읽을 때 인덱스가 무엇이고 값이 무엇인지 먼저 적어 두자. “등수 순으로 나열한 번호”와 “번호 순으로 나열한 등수”는 배열 모양이 같아서 코드만 봐서는 구분이 안 된다.
- “모든 ~에서”를 셀 때
answer++를 안쪽 루프에 두면 횟수가 된다. 조건이 끝까지 유지됐는지는 루프 밖에서 한 번 판정한다 — 플래그가 살아 있는지 보든, 통과 횟수가 전체 횟수와 같은지 보든.
댓글남기기