[백준/Java] 3178 : 코코스

백준 3178번 '코코스' 풀이입니다. 앞쪽 K글자는 공통 접두사를, 뒤쪽 K글자는 공통 접미사를 최대한 공유하도록 만들어야 합니다. 각 단어를 앞뒤로 나누고, 뒷부분은 뒤집어서 저장한 뒤 각각 정렬해 인접 문자열끼리 비교했습니다. 그래프를 직접 구성하려 했으나 복잡해서 레퍼런스를 통해 이 방식을 알게 되었습니다.

---

📌 문제 정보

• 번호: 3178
• 제목: 코코스
• 난이도: Gold 3
• 분류: 문자열, 정렬, 트리/트라이, 구현

---

💡 접근 방식

각 단어를 앞뒤로 나누고, 뒤쪽 글자는 뒤집어서 처리한 후 각각 정렬하여 인접한 문자열끼리 비교했습니다.

---

🔹 단계별 풀이

1단계: 각 단어에서 앞/뒤 분리. suffix는 뒤집어서 저장

2단계: 정렬 후 인접 원소 비교로 공통 접두사 길이를 계산, K에서 빼서 추가 노드 수 산출

3단계: 첫 문자열의 앞뒤는 2K가 초기값, 이후 각 인접 원소마다 누적

---

💻 핵심 코드

int ans = K * 2;

for (int i = 1; i < N; i++) {
    ans += (K - count(prefix[i - 1], prefix[i]));
    ans += (K - count(suffix[i - 1], suffix[i]));
}

static int count(String s1, String s2) {
    int count = 0;
    for (int i = 0; i < s1.length(); i++) {
        if (s1.charAt(i) == s2.charAt(i)) count++;
        else break;
    }
    return count;
}

---

⏳ 복잡도 분석

• 시간 복잡도: O(N log N × K)
• 공간 복잡도: O(N × K)

---

📄 전체 코드

package B3178;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        String[] prefix = new String[N];
        String[] suffix = new String[N];
        for (int i = 0; i < N; i++) {
            String str = br.readLine();
            prefix[i] = str.substring(0, K);
            suffix[i] = new StringBuilder(str.substring(K)).reverse().toString();
        }
        Arrays.sort(prefix);
        Arrays.sort(suffix);
        int ans = K * 2;
        for (int i = 1; i < N; i++) {
            ans += (K - count(prefix[i - 1], prefix[i]));
            ans += (K - count(suffix[i - 1], suffix[i]));
        }
        System.out.println(ans);
    }

    static int count(String s1, String s2) {
        int count = 0;
        for (int i = 0; i < s1.length(); i++) {
            if (s1.charAt(i) == s2.charAt(i)) count++;
            else break;
        }
        return count;
    }
}