[백준 Java]_신촌 통폐합 계획 (31423)

NANO·2026년 3월 18일

Java 백준 알고리즘

[Algorithm]

목록 보기

10/10

문제 정보

출처 및 난이도: 백준 골드5
링크: https://www.acmicpc.net/problem/31423
분류: 문자열, 그래프 이론, DFS, 연결 리스트, 자료구조

문제 요약

N개 대학교 이름이 주어질 때, N-1번의 합치기 연산 (i, j) 를 순서대로 수행

s_i 뒤에 s_j를 이어 붙이고 s_j를 빈 문자열로 만든 뒤, 최종 이름을 출력하는 문제.

풀이 접근

시도 1 - LinkedList<String>

직관적으로 연결 리스트 사용
합치기 연산마다 리스트 탐색이 필요해 시간 초과

시도 2 - ArrayList<StringBuilder>

list.get(i).append(list.get(j))로 문자열 직접 합치기
N이 최대 100,000이고 이름 길이도 길어서 합칠 때마다 문자열 복사 발생 → O(N²) 시간 초과

최종 - next[] + tail[] 배열로 연결 리스트 구현
1. next[i]: i번 대학 다음에 연결된 대학 번호 (초기값 -1)
2. tail[i]: i번 체인의 마지막 노드 번호 (초기값 자기 자신 i)
3. 합치기 (i, j) 시:

next[tail[i]] = j → i 체인 끝에 j 체인 연결
tail[i] = tail[j] → i 체인의 꼬리 갱신

마지막 answer(=i)부터 next 따라가며 이름 출력

연결 리스트?

연결 리스트(Linked List)는 데이터를 저장할 때 하나의 데이터와 그 다음 데이터로의 위치를 함께 저장하여 논리적으로 연결(link)하는 방식으로 자료를 저장한다.

데이터는 논리적으로 연결되어 있으므로 배열과 달리 데이터의 삽입 삭제가 자유로워지면서 자연스럽게 전체 크기를 늘리고 줄이는 것 또한 가능해진다.

보통 node로 저장을 하고, 그 안에 데이터(data)와 다음 노드의 주소나 참조(next)를 담는다. 즉, node: data + next

Java에서는 LinkedList 클래스를 기본으로 제공한다.

import java.util.LinkedList;

LinkedList<String> list = new LinkedList<>();

// 삽입
list.add("A");          // 맨 뒤
list.addFirst("B");     // 맨 앞
list.addLast("C");      // 맨 뒤

// 조회
list.get(0);            // 인덱스로 접근
list.getFirst();        // 첫 번째 요소
list.getLast();         // 마지막 요소

// 삭제
list.remove(0);         // 인덱스로 삭제
list.removeFirst();     // 첫 번째 삭제
list.removeLast();      // 마지막 삭제

// 크기
list.size();

이중 연결 리스트(Doubly Linked List) 구조로 구현되어 있다. 심지어 List와 Deque 인터페이스를 모두 구현하므로, 리스트뿐 아니라 스택/큐/덱으로도 활용 가능하다.

핵심 아이디어

실제로 문자열을 합치지 않고 포인터만 연결 → 합치기 연산이 O(1)
tail[] 배열이 핵심: 리스트 끝을 항상 O(1)에 알 수 있어서 이어붙이기가 빠름
출력할 때만 next를 따라가며 StringBuilder에 append → 전체 O(N)

코드

<시도 1>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        LinkedList<String> list = new LinkedList<>();
        // 이 문제는 인덱스 1부터 시작
        list.add("");

        int N = Integer.parseInt(br.readLine());
        for (int temp = 0; temp < N; temp++) list.add(br.readLine());

        String s = "";
        for (int temp = 0; temp < N-1; temp++) {
            String[] nums = br.readLine().split(" ");
            int i = Integer.parseInt(nums[0]);
            int j = Integer.parseInt(nums[1]);
            list.set(i, list.get(i) + list.get(j));
            if (temp == N - 2) s = list.get(i);
        }

        System.out.println(s);
    }
}

<시도 2>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        ArrayList<StringBuilder> list = new ArrayList<>();
        // 이 문제는 인덱스 1부터 시작
        list.add(new StringBuilder());

        int N = Integer.parseInt(br.readLine());
        for (int temp = 0; temp < N; temp++) list.add(new StringBuilder(br.readLine()));

        int answer = 0;
        for (int temp = 0; temp < N-1; temp++) {
            String[] nums = br.readLine().split(" ");
            int i = Integer.parseInt(nums[0]);
            int j = Integer.parseInt(nums[1]);
            list.get(i).append(list.get(j));
            list.get(j).setLength(0);
            answer = i;
        }

        System.out.println(list.get(answer));
    }
}

<최종>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        String[] unis = new String[N + 1];
        int[] next = new int[N + 1];
        int[] tail = new int[N + 1];

        for (int i = 1; i <= N; i++) {
            unis[i] = br.readLine();
            next[i] = -1;
            tail[i] = i;
        }

        int answer = 0;
        for (int temp = 0; temp < N - 1; temp++) {
            String[] nums = br.readLine().split(" ");
            int i = Integer.parseInt(nums[0]);
            int j = Integer.parseInt(nums[1]);

            next[tail[i]] = j;
            tail[i] = tail[j];
            answer = i;
        }
        StringBuilder sb = new StringBuilder();
        int next_num = answer;
        while (next_num != -1) {
            sb.append(unis[next_num]);
            next_num = next[next_num];
        }
        System.out.print(sb);
    }
}