백준 2179 비슷한 단어

bunhine0452·2025년 12월 7일
알고리즘 문제풀이

알고리즘 문제풀이

목록 보기
13/14

문제 링크

1. 정의

문제에서 다루는 값들

  • N

    • 단어의 개수 (2 ≤ N ≤ 20,000)

  • 단어들

    • 모두 소문자 알파벳, 길이는 최대 100
    • 서로 다른 단어들만 주어짐 (중복 없음)

“비슷한 정도”의 정의

두 단어의 비슷한 정도 = 공통 접두사의 길이

  • 접두사: 두 단어의 맨 앞에서부터 연속으로 같은 문자열

    • 예:

      • "AHEHHEH" vs "AHAHEH" → 공통 접두사 "AH" → 길이 2
      • "AB" vs "CD" → 공통 접두사 없음 → 길이 0

우리가 해야 할 일:

N개의 단어 중에서, 공통 접두사 길이가 가장 긴 두 단어를 찾아 출력
(단, 두 단어는 서로 달라야 한다)

동률(접두사 길이 같을 때) 처리 규칙

접두사 최대 길이가 같은 쌍이 여러 개 있으면,

  1. 먼저, S가 입력상 더 앞에 있는 쌍을 선택
0번: apple
1번: apply
2번: banana

이 중 apple과 apply의 공통 접두사는 "appl"일 때,

두 단어의 인덱스는 (0, 1)

그래서 S = apple

T = apply
  1. 그런 쌍도 여러 개라면, 그 중에서 T가 더 앞에 있는 쌍을 선택
0번 단어: abcxxxx
1번 단어: abczzzz
2번 단어: abcqqqq
그럼 접두사(adc)는 3단어가 겹치는데,
이론적으로 만들 수 있는 쌍은:

(0,1)

(0,2)

(1,2)

이렇게 3개이다.

그런데 문제의 우선순위 규칙은:

<첫번째 조건>
먼저 “앞에 오는 단어(S)”가 가장 작은 인덱스여야 한다 → 즉 S=0

<두번째 조건>
S가 같다면 “뒤에 오는 단어(T)”가 가장 작은 인덱스여야 한다 → 즉 T=1

그래서 정답 쌍은 무조건 (0,1)이 된다.

왜냐하면 T(두 번째 단어)의 인덱스가 1보다 뒤에 있으니 (0,2)는 (0,1)에 밀린다.

즉, (i, j) 쌍을 고를 때

  • 공통 접두사 길이 최대인 쌍들 중에서
  • i(앞 단어 인덱스)가 가장 작은 쌍
  • i도 같다면, j가 가장 작은 쌍

을 고르면 된다. (이거 이해하느라 좀 시간걸림)

2. 스크래치

설계 스크래치

  1. 단어들을 입력받아 배열 words에 저장

  2. 모든 단어의 최대 길이 maxLen을 구함

  3. 접두사 길이 K를 maxLen부터 1까지 줄여가며,

    • 길이가 K 이상인 단어들의 앞 K글자 접두사를 기준으로
    • 같은 접두사를 가진 단어들을 그룹화
    • 각 접두사마다 “입력 순서 기준 앞에서 두 개” 단어의 인덱스를 저장

  4. 특정 K에서,

    • 같은 접두사를 공유하는 단어가 2개 이상 있는 그룹이 하나라도 존재한다면,
    • 그 중에서 “입력 순서 규칙”에 가장 잘 맞는 (S, T) 쌍을 찾아 정답 후보로 확정하고 반복 종료

  5. 만약 어떤 K에서도 두 단어 이상 겹치는 접두사가 없다면
    → 공통 접두사 길이 0이 최대이므로 (0번 단어, 1번 단어) 출력

K를 큰 값에서 작은 값으로 내려가는 이유

  • 우리는 공통 접두사 길이가 최대인 쌍을 원함

  • 그렇다면

    • 먼저 가장 긴 접두사 길이 K = maxLen 에서 가능한 쌍이 있는지 확인
    • 없으면 K = maxLen - 1, …, K = 1 순서로 내려오다가
    • 처음으로 쌍이 생기는 K가 곧 최대 접두사 길이가 됨

  • 그래서 “큰 K → 작은 K 순서”로 탐색하고,
    처음 성공하는 순간 바로 종료하면 된다.

K가 고정된 한 번의 사이클

K를 하나 정했다고 생각하고, 그 K에 대해 하는 일을 자세히 보면:

  1. map:

    • key = 길이 K의 접두사 문자열
    • value = int[2] 배열 = {해당 접두사를 가진 가장 앞에 입력된 단어 인덱스, 두 번째로 앞에 입력된 단어 인덱스}

  2. 모든 단어 i(0 ~ N-1)에 대해:

    • 단어 길이가 K 미만이면 스킵

    • 접두사 pref = words[i].substring(0, K) 추출

    • map에서 pref에 해당하는 pair 찾거나 새로 생성

    • pair 갱신 규칙

      • pair[0] = 가장 작은 인덱스
      • pair[1] = 그 다음으로 작은 인덱스

  3. 모든 단어를 처리한 후,

    • map의 각 pair를 돌며

    • pair[1] != -1 인 것만 (두 단어 이상 존재하는 접두사 그룹)

    • 그들 중에서

      • pair[0]이 가장 작은 것,
      • 같다면 pair[1]이 가장 작은 것을 candidate로 선택

  4. candidateFirst != -1 이라면
    → 이 K에서 답이 존재 → 이 K가 최대 접두사 길이 → 정답 확정 후 반복 종료

3. 설계

입력 및 준비

int N = Integer.parseInt(br.readLine().trim());

String[] words = new String[N];
int maxLen = 0;

for (int i = 0; i < N; i++) {
    words[i] = br.readLine().trim();
    maxLen = Math.max(maxLen, words[i].length());
}
  • N : 단어 개수
  • words : 단어들을 저장하는 배열
  • maxLen : 등장하는 단어 중 가장 긴 길이 (접두사 최대 길이 상한)

최종 정답을 저장할 변수들

int bestFirst = -1;   // 정답 S의 인덱스
int bestSecond = -1;  // 정답 T의 인덱스
int bestLen = 0;      // 최대 공통 접두사 길이
  • 아직 정답을 못 찾았을 때는 -1로 초기화

접두사 길이 K를 줄여가며 탐색

for (int K = maxLen; K >= 1; K--) {
    HashMap<String, int[]> map = new HashMap<>();
  • 각 K마다 새 map을 사용
  • 한 K 사이클에서만 의미 있는 그룹들이기 때문

K 길이의 접두사로 묶기

for (int i = 0; i < N; i++) {
    if (words[i].length() < K) continue; 
    String pref = words[i].substring(0, K);

    int[] pair = map.get(pref);
    if (pair == null) {
        pair = new int[]{i, -1};
        map.put(pref, pair);
    } else {
        int first = pair[0];
        int second = pair[1];

        if (i == first) {
            continue;
        }
        if (i < first) {
            pair[1] = first;
            pair[0] = i;
        } else if (i > first && (second == -1 || i < second)) {
            pair[1] = i;
        }
    }
}

<깨우친 사실>

  • map의 value인 pair는 항상

    • pair[0] < pair[1] (둘 다 인덱스)
    • 즉, 입력 순서대로 가장 작은 인덱스, 두 번째로 작은 인덱스

  • 갱신 로직 자세히:

    • 처음 본 접두사면 {현재 인덱스, -1} 로 저장

    • 이미 있는 접두사면:

      • i < first → 현재 i가 제일 앞이니까:

        • 기존 first 를 second로 밀어내고
        • first를 i로 교체

      • i > first이면서

        • second가 아직 없거나 (-1)
        • 혹은 i < second → 두 번째로 앞선 인덱스로 갱신

이렇게 하면 접두사별로 늘 앞에서 두 개만 잘 유지할 수 있음.

이 K에서 후보 쌍 고르기

int candidateFirst = -1;
int candidateSecond = -1;

for (int[] pair : map.values()) {
    if (pair[1] == -1) continue; // 한 단어만 있으면 쌍이 안 됨
    int f = pair[0];
    int s = pair[1];

    if (candidateFirst == -1 ||
            f < candidateFirst ||
            (f == candidateFirst && s < candidateSecond)) {
        candidateFirst = f;
        candidateSecond = s;
    }
}

  • 이 K에서 가능한 모든 접두사 그룹을 돌며

  • “입력 순서 상 앞에 오는 쌍”을 찾는 로직:

    1. 아직 후보가 없다면 (candidateFirst == -1) → 바로 채택
    2. 현재 f가 기존 후보의 candidateFirst보다 앞이면 → 교체
    3. f가 같다면, s가 더 앞이면 → 교체

→ 문제에서 요구하는 우선순위 조건을 그대로 구현한 부분.

이 K에서 쌍을 찾았다면 정답 확정 후 break

if (candidateFirst != -1) {
    bestLen = K;
    bestFirst = candidateFirst;
    bestSecond = candidateSecond;
    break;
}
  • 이 K에서 두 단어 이상 같은 접두사를 가진 그룹이 있었다는 뜻
  • 그리고 K는 큰 값에서 내려오는 중이므로,
    이 순간의 K가 전체에서 최대 공통 접두사 길이
  • 이후 작은 K들은 볼 필요가 없으므로 바로 종료

어떤 K에서도 못 찾았을 때(공통 접두사 길이 0이 최대)

if (bestFirst == -1) {
    bestFirst = 0;
    bestSecond = 1;
}
  • 공통 접두사 길이 0이 최대인 경우
  • 동률 처리 규칙에 따르면
    (0번째 단어, 1번째 단어)가 가장 앞에 오는 쌍

출력

bw.write(words[bestFirst]);
bw.newLine();
bw.write(words[bestSecond]);
bw.newLine();
bw.flush();
  • 인덱스에서 실제 단어 문자열로 바꿔 출력

4. 근거

알고리즘 선택 이유, 그냥 부르트 포스가 아닌 효율적인 부르트 포스

  • 접두사 길이를 기준으로 이분 탐색하는 것이 아니라,
    길이가 작은 상수(≤ 100)라는 점을 이용해서

    • K = maxLen ... 1 까지 순회

  • 각 K에 대해

    • HashMap<String, int[]>로 “K 길이 접두사가 같은 단어들”을 빠르게 그룹화 후 완전탐색

  • 시간 복잡도(대략):

    • 최악: K 100개 × 단어 20,000개 × 접두사 잘라내기 O(K)
    • → O(N * L^2) 정도, 여기서 L ≤ 100 이라 상수 취급 가능
    • 실제로는 20,000 × 100 × 100 = 200,000,000 연산 정도인데
      자바로 충분히 감당 가능한 수준

왜?

  1. L(단어 길이)가 매우 작다 (≤ 100)
    → 접두사 길이 K를 일일이 내려가며 확인해도 큰 문제가 안 됨

  2. 문제의 핵심은 “접두사가 같은 단어들만 비교하면 된다”는 점
    → 모든 쌍 i, j를 전부 비교하면 O(N²L)이지만,
    → 동일 접두사 그룹 안에서만 “앞에서 두 개”를 관리하면
    중복 계산을 많이 줄일 수 있음

  3. 우선순위 규칙(입력 순서)을 index 로 자연스럽게 처리

    • map에는 단어를 입력 순서대로 넣으므로,
      작은 인덱스가 자동으로 우선순위가 높음
    • pair[0], pair[1]에 “가장 앞 / 두 번째로 앞 단어”만 저장하면
      복잡한 비교 없이도 규칙을 만족

5. 코드

사용자 코드 그대로 두고, 의미를 붙여 다시 보여줄게요.

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine().trim());

        // 1. 단어 입력 및 최대 길이 계산
        String[] words = new String[N];
        int maxLen = 0;

        for (int i = 0; i < N; i++) {
            words[i] = br.readLine().trim();
            maxLen = Math.max(maxLen, words[i].length());
        }

        // 2. 최종 정답 인덱스, 길이
        int bestFirst = -1;   // 정답 S의 인덱스
        int bestSecond = -1;  // 정답 T의 인덱스
        int bestLen = 0;      // 최대 접두사 길이

        // 3. 접두사 길이 K를 큰 것부터 줄여가며 탐색
        for (int K = maxLen; K >= 1; K--) {
            HashMap<String, int[]> map = new HashMap<>();

            // 3-1. 길이 K의 접두사로 그룹화
            for (int i = 0; i < N; i++) {
                if (words[i].length() < K) continue;
                String pref = words[i].substring(0, K);

                int[] pair = map.get(pref);
                if (pair == null) {
                    pair = new int[]{i, -1};
                    map.put(pref, pair);
                } else {
                    int first = pair[0];
                    int second = pair[1];

                    if (i == first) {
                        continue;
                    }
                    if (i < first) {
                        pair[1] = first;
                        pair[0] = i;
                    } else if (i > first && (second == -1 || i < second)) {
                        pair[1] = i;
                    }
                }
            }

            // 3-2. 이 K에서 조건을 만족하는 가장 앞쪽 쌍 찾기
            int candidateFirst = -1;
            int candidateSecond = -1;

            for (int[] pair : map.values()) {
                if (pair[1] == -1) continue; // 단어가 한 개뿐인 그룹 제외
                int f = pair[0];
                int s = pair[1];

                if (candidateFirst == -1 ||
                        f < candidateFirst ||
                        (f == candidateFirst && s < candidateSecond)) {
                    candidateFirst = f;
                    candidateSecond = s;
                }
            }

            // 3-3. 이 K에서 하나라도 쌍이 있으면 이게 최대 접두사 길이
            if (candidateFirst != -1) {
                bestLen = K;
                bestFirst = candidateFirst;
                bestSecond = candidateSecond;
                break;
            }
        }

        // 4. 어떤 K에서도 쌍을 못 찾으면 (공통 접두사 길이 0이 최대)
        if (bestFirst == -1) {
            bestFirst = 0;
            bestSecond = 1;
        }

        // 5. 출력
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(words[bestFirst]);
        bw.newLine();
        bw.write(words[bestSecond]);
        bw.newLine();
        bw.flush();
    }
}

고난

  • pair 갱신할 때

    • pair[0]와 pair[1]의 인덱스 순서(작은 것, 그 다음 것)를 항상 유지해야 함

  • candidateFirst, candidateSecond 비교할 때

    • 조건문에서 우선순위를 정확히 지켜야 함:

      • 먼저 f 비교 → 같을 때 s 비교

  • bestFirst == -1일 때 fallback 처리

    • 이 부분이 없으면 “공통 접두사 길이 0” 케이스에서 정답이 비어버림

회고

  • 문제 어려웠다. 어후
profile
bunhine0452
이전 포스트

프로그래머스 42861 섬 연결하기

다음 포스트

BOJ 1937 욕심쟁이 판다

0개의 댓글