학회에서 가장 많이 마주친 사람

문제

N명의 참가자가 학회의 다섯 세션에 모두 참여했다. 세션마다 여러 트랙이 동시에 열리고, 참가자는 각 세션에서 트랙 하나를 골라 듣는다. 두 참가자가 어떤 세션에서 같은 트랙을 들었다면 그 세션에서 마주쳤다고 한다.

다섯 세션 동안 한 번이라도 마주친 사람의 수가 가장 많은 참가자를 찾는다. 여러 명이면 번호가 가장 작은 참가자를 답으로 한다.

• 3 ≤ N ≤ 1000, 트랙 번호는 1 이상 9 이하의 정수
• 입력: 첫 줄에 N, 둘째 줄부터 N줄에 걸쳐 1번 참가자부터 차례로 세션 1~5의 트랙 번호 다섯 개
• 출력: 참가자 번호

입력            출력
6               3
1 1 1 1 1
1 1 1 1 1
2 3 4 5 6
7 3 8 9 7
8 9 4 7 8
9 8 7 5 9

3번 참가자는 세션 2에서 4번(트랙 3), 세션 3에서 5번(트랙 4), 세션 4에서 6번(트랙 5)과 마주쳐 모두 3명이다. 1번과 2번은 다섯 세션 내내 같은 트랙이었지만 서로 한 사람씩만 마주친 것이므로 각각 1명이다. 따라서 답은 3번.

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비의 1120번 문제를 소재와 예제만 바꿔 재구성했다.

공통 코드

아래 시도들은 입력을 읽는 부분을 공유한다. 각 시도에서는 답을 구하는 부분만 보여준다.

import java.util.Scanner;

public class Main {
    static final int SESSIONS = 5;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // track[i][s] = 참가자 i가 세션 s에서 들은 트랙 (i, s 모두 0부터)
        int[][] track = new int[n][SESSIONS];
        for (int i = 0; i < n; i++)
            for (int s = 0; s < SESSIONS; s++)
                track[i][s] = sc.nextInt();

        int answer = 0;
        // ... 답을 구하는 부분 (각 시도 참고)
        System.out.println(answer);
    }
}

참가자는 코드 안에서 0번부터 세고, 출력할 때만 + 1 한다.

시도 1 — 세션마다 같은 트랙인 쌍을 세기

접근

“세션을 하나씩 보면서, 그 세션에서 같은 트랙인 두 사람을 찾을 때마다 양쪽 카운트를 1씩 올린다”는 계획이다. 참가자 한 명마다 나머지 전원을 다시 훑는 대신 세션 안에서만 비교하니 더 빠를 것 같았다.

int[] cnt = new int[n];
for (int s = 0; s < SESSIONS; s++) {
    for (int i = 0; i < n; i++) {
        for (int k = i + 1; k < n; k++) {
            if (track[i][s] == track[k][s]) {
                cnt[i]++;
                cnt[k]++;
            }
        }
    }
}

int max = -1;
for (int i = 0; i < n; i++) {
    if (cnt[i] > max) {
        max = cnt[i];
        answer = i + 1;
    }
}

결과

실패 — 예제에서 1번을 출력. 정답은 3번.

cnt가 [5, 5, 3, 1, 1, 1]로 나왔다. 1번과 2번은 다섯 세션 내내 같은 트랙이라 같은 쌍이 다섯 번 세어져 5가 됐고, 실제로 세 명과 마주친 3번(3)을 눌러 버렸다.

강의 예제처럼 한 세션에 세 명 이상이 같은 트랙일 때도 같은 일이 생긴다. 3·4·5번이 한 트랙이면 (3,4) (3,5) (4,5) 세 쌍이 각각 처리되어 세 사람 모두 2씩 올라간다. 3번이 실제로 마주친 사람도 4번과 5번, 2명이라 이 세션만 보면 숫자가 맞는 것처럼 보인다. 하지만 이 2는 “사람 2명”이 아니라 “쌍 2개”에서 온 값이다. 그래서 다음 세션에서 3번과 4번이 또 같은 트랙이 되면 쌍 (3,4)가 한 번 더 세어져 cnt[3]은 3이 되는데, 3번이 마주친 사람은 여전히 4번과 5번, 2명이다.

분석

이 코드가 세는 것은 사람 수가 아니라 횟수다. 같은 트랙인 쌍을 만날 때마다 올리므로, 두 사람이 세션 다섯 개에서 겹치면 5가 되고 세 사람이 한 트랙에 모이면 각자 2가 된다. 문제가 묻는 “한 번이라도 마주친 사람의 수”는 두 경우 모두 그보다 작다.

루프의 바깥이 세션이고 안쪽이 쌍이라 “이 사람과 전에도 마주쳤었나”를 기억할 자리가 없다. 사람 수를 세려면 사람이 루프의 축이어야 한다. 그래야 상대 한 명에 대해 “한 번이라도”를 한 번만 판정할 수 있다.

시도 2 — 참가자마다 상대를 돌며 “한 번이라도”를 판정 (채택)

접근

바깥 루프를 참가자 i, 그 안을 상대 j로 두고, 두 사람의 다섯 세션을 비교하다 같은 트랙을 처음 찾는 순간 cnt를 1 올리고 break로 다음 상대로 넘어간다. 같은 상대와 몇 세션이 겹치든 1만 더해진다.

int max = -1;
for (int i = 0; i < n; i++) {
    int cnt = 0;
    for (int j = 0; j < n; j++) {
        if (i == j) continue;
        for (int s = 0; s < SESSIONS; s++) {
            if (track[i][s] == track[j][s]) {
                cnt++;
                break;
            }
        }
    }
    if (cnt > max) {
        max = cnt;
        answer = i + 1;
    }
}

결과

성공 — 예제에서 3번을 출력.

복잡도: 시간 O(N²), 공간 O(1). 참가자 N명마다 상대 N명을 보고, 각 상대와 세션 5개(상수)를 비교한다. 시도 1도 세션 5개마다 N² 쌍을 봤으니 시간은 같다.

• i == j는 자기 자신이라 건너뛴다.
• 같은 트랙을 찾으면 break — 나머지 세션은 보지 않으므로 한 상대는 최대 1만 더해진다.
• cnt > max에 등호가 없어서, 같은 값이면 먼저 본 작은 번호가 유지된다. “여러 명이면 가장 작은 번호”가 따로 처리 없이 지켜진다.

분석

시도 1과 시간 복잡도는 같은데 답이 다른 이유는 세는 단위다. 시도 1은 (세션, 쌍)마다 1을 더해 마주친 횟수를 세고, 시도 2는 상대 한 명마다 “마주친 적 있다/없다”를 0 또는 1로 더해 마주친 사람 수를 센다.

“한 번이라도”라는 조건은 첫 매칭에서 break하는 것으로 충분히 표현된다. 별도의 플래그 없이도 안쪽 루프 자체가 “있다/없다” 판정이 된다.

다른 방법 — 쌍 중심을 유지하고 중복만 막기

시도 1의 구조가 더 편하다면, “이 쌍은 이미 셌다”를 기억하는 표를 두면 된다.

boolean[][] met = new boolean[n][n];
for (int s = 0; s < SESSIONS; s++) {
    for (int i = 0; i < n; i++) {
        for (int k = i + 1; k < n; k++) {
            if (track[i][s] == track[k][s]) {
                met[i][k] = true;
                met[k][i] = true;
            }
        }
    }
}

int max = -1;
for (int i = 0; i < n; i++) {
    int cnt = 0;
    for (int j = 0; j < n; j++)
        if (met[i][j]) cnt++;
    if (cnt > max) {
        max = cnt;
        answer = i + 1;
    }
}

복잡도는 시간 O(N²)로 같지만 공간이 O(N²)로 늘어난다(N = 1000이면 백만 칸). 같은 쌍을 여러 번 만나도 true를 덮어쓸 뿐이라 중복이 사라진다. 다만 표를 하나 더 두고 두 번 훑어야 하므로, 이 문제에서는 시도 2가 더 간단하다. “마주친 쌍” 자체를 나중에 또 써야 하는 문제라면 이쪽이 낫다.

정리

시도	핵심	복잡도	결과
1. 세션마다 쌍 세기	같은 트랙인 쌍을 만날 때마다 +1	O(N²)	오답 — 사람 수가 아닌 횟수
2. 참가자마다 “한 번이라도” 판정 (채택)	상대 한 명당 첫 매칭에서 break	O(N²)	정답
다른 방법. 쌍 + 중복 표	boolean[n][n]으로 셌던 쌍 기억	O(N²), 공간 O(N²)	정답, 표 하나 추가

채택: 시도 2. 추가 공간 없이 문제가 묻는 단위(사람 수)를 그대로 세고, “한 번이라도”가 break 한 줄로 표현된다.

• 세기 전에 단위부터 정한다. “몇 번”과 “몇 명”은 같은 루프에서 나오지 않는다. 몇 명을 원하면 사람이 바깥 루프여야 한다.
• “한 번이라도 ~”는 첫 매칭에서 break 한다. 세지 말고 있다/없다만 판정하면 중복이 생기지 않는다.