핵심 요약
- 팰린드롬(Palindrome)은 앞으로 읽으나 뒤로 읽으나 똑같은 문자열을 의미하며, DP를 이용해 O(N^2)에 해결할 수 있습니다.
- 백준 10942번 문제는 로직의 정확성뿐만 아니라 대량의 입출력(I/O) 처리 능력을 평가하는 까다로운 문제입니다.
- 질문의 개수(M)가 100만 개일 때,
Scanner와System.out.println을 사용하면 I/O 오버헤드로 인해 필연적으로 시간 초과가 발생합니다. - StringBuilder를 사용하여 정답을 메모리 버퍼에 담아두었다가 한 번에 출력하는 패턴은 코딩 테스트 고득점을 위한 필수 테크닉입니다.
- DP 테이블을 채울 때는 ‘길이(Length)’를 기준으로 반복문을 구성해야, 작은 구간의 결과를 큰 구간에서 참조할 수 있습니다.
목차
- 1. “로직은 완벽한데 왜 틀릴까?” 개발자를 미치게 하는 시간 초과
- 2. 팰린드롬의 수학적 정의와 DP 접근법
- 3. [실패 분석] 처음 작성한 코드가 느린 이유 (Scanner & println)
- 4. [해결 전략] 트럭에 짐을 실어라 (BufferedReader & StringBuilder)
- 5. 최종 정답 코드 및 구현 디테일
- 6. 마치며: 알고리즘 그 너머의 최적화
1. “로직은 완벽한데 왜 틀릴까?” 개발자를 미치게 하는 시간 초과
코딩 테스트 현장에서 가장 당혹스러운 순간은 언제일까요? 아예 모르는 문제가 나왔을 때보다, “분명히 맞는 로직인데 시간 초과(Time Limit Exceeded)가 뜰 때”가 훨씬 더 고통스럽습니다. 수십 번 코드를 뜯어보고 점화식을 다시 세워봐도 로직에는 흠잡을 데가 없습니다. 도대체 무엇이 문제일까요?
오늘 다룰 백준 10942번 (팰린드롬?) 문제는 바로 이런 상황을 유도하는 대표적인 함정 문제입니다. 이 문제는 표면적으로는 다이나믹 프로그래밍(DP) 능력을 묻는 것처럼 보이지만, 그 이면에는 대용량 데이터 입출력(I/O) 처리라는 또 다른 테스트가 숨겨져 있습니다. 로직이 아무리 빨라도 데이터를 읽고 쓰는 방식이 느리면 탈락하는, 아주 현실적이고 잔혹한 문제죠. 지금부터 그 원인과 해결책을 낱낱이 파헤쳐 보겠습니다.
2. 팰린드롬의 수학적 정의와 DP 접근법
먼저 알고리즘의 핵심인 팰린드롬(Palindrome)에 대해 짚고 넘어갑시다. ‘기러기’, ‘토마토’, ‘12321’ 처럼 거꾸로 읽어도 원본과 똑같은 문자열을 말합니다. 컴퓨터 과학에서 이를 판별하는 방법은 크게 두 가지가 있습니다.
(1) 무식하게 다 해보기 (Brute-Force)
질문이 들어올 때마다 해당 구간 [S, E]를 잘라내어 앞뒤를 비교하는 방식입니다. 구간의 최대 길이는 N이고, 질문의 개수는 M입니다. 이 경우 시간 복잡도는 O(N * M)이 됩니다. 문제 조건에서 N은 2,000, M은 1,000,000이므로, 최악의 경우 20억 번의 연산이 필요합니다. 1초에 약 1억 번 연산하는 컴퓨터에게 20억 번을 시키면 당연히 시간 초과가 납니다.
(2) 똑똑하게 기억하기 (Dynamic Programming)
그래서 우리는 DP를 사용해야 합니다. 핵심 아이디어는 “큰 팰린드롬은 작은 팰린드롬을 포함한다”는 것입니다. 예를 들어 1 2 3 2 1이 팰린드롬인지 알기 위해서는, 양 끝의 1과 1이 같은지 확인하고, 그 안쪽인 2 3 2가 팰린드롬인지 확인하면 됩니다.
이를 점화식으로 표현하면 다음과 같습니다. 배열을 A, DP 테이블을 D라고 합시다.
D[i][j] = (A[i] == A[j]) AND (D[i+1][j-1] == 1)
즉, “겉포장지가 같고, 내용물도 팰린드롬이어야 한다”는 논리입니다. 이 방식을 사용하면 DP 테이블을 채우는 데 O(N^2), 약 400만 번의 연산만 필요하므로 시간 내에 충분히 계산 가능합니다. 그런데 왜 처음에 작성한 코드는 시간 초과가 났을까요?
3. [실패 분석] 처음 작성한 코드가 느린 이유 (Scanner & println)
사용자님이 처음에 작성하셨던 코드를 그대로 가져왔습니다. DP 로직은 완벽했지만, 입출력 방식이 문제의 발목을 잡았습니다.
// [사용자님의 초기 실패 코드]
import java.util.*;
class Main {
static int n, m;
static int[] list;
static int[][] dp;
static void run() {
// DP 로직은 아주 훌륭합니다. O(N^2)으로 충분히 빠릅니다.
for (int w=1; w<=n; w++) {
for (int i=1; i<=n; i++) {
int j=i+w;
if (j>n) break;
if (list[i]==list[j]) {
if (w==1) dp[i][j]=1;
else dp[i][j]=dp[i+1][j-1];
} else {
dp[i][j]=0;
}
}
}
}
public static void main(String[] args) {
// ❌ 문제점 1: Scanner 사용
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
list=new int[n+1];
dp=new int[n+1][n+1];
for (int i=1; i<=n; i++) {
list[i]=sc.nextInt();
dp[i][i]=1;
}
m=sc.nextInt();
run();
// ❌ 문제점 2: 반복문 내 System.out.println 사용
for (int i=0; i<m; i++) {
int s=sc.nextInt();
int e=sc.nextInt();
// 여기가 치명적인 병목 구간입니다!
System.out.println(dp[s][e]);
}
}
}
왜 느릴까요?
- Scanner의 한계:
Scanner는 사용하기 편리하지만, 내부적으로 정규식(Regex)을 사용하여 입력을 파싱합니다. 입력 데이터가 100만 개 단위가 되면 이 파싱 시간만으로도 0.5초 이상을 잡아먹습니다. - System.out.println의 부하: 가장 큰 원인입니다. 이 함수는 호출될 때마다 자바 프로그램이 운영체제(OS)에게 "화면에 출력해줘"라고 요청하는 시스템 콜(System Call)을 발생시킵니다. 또한 출력 버퍼를 매번 비우는(Flush) 작업을 수행합니다. 마치 택배 기사가 상자 100만 개를 트럭에 싣지 않고, 상자 하나를 들고 배달지까지 100만 번 왕복하는 것과 같습니다.
4. [해결 전략] 트럭에 짐을 실어라 (BufferedReader & StringBuilder)
해결책은 간단합니다. 느린 Scanner 대신 버퍼를 사용하는 BufferedReader를 쓰고, println 대신 StringBuilder를 사용하는 것입니다.
StringBuilder의 역할 (트럭):
- 메모리 연산: 문자열을 합치는 작업이 순수하게 메모리 내부에서만 일어납니다. OS를 호출하지 않으므로 매우 빠릅니다.
- 배치 처리: 마지막에
System.out.println(sb);를 딱 한 번만 호출합니다. 100만 번의 시스템 콜이 단 1번으로 줄어듭니다.
5. 최종 정답 코드 및 구현 디테일
이제 로직과 입출력 최적화가 모두 적용된 최종 코드를 소개합니다. 주석을 통해 각 라인의 의미를 곱씹어 보시기 바랍니다.
import java.io.*;
import java.util.*;
class Main {
// 전역 변수 선언: 힙 메모리를 사용하여 스택 오버플로우 방지 및 접근 편의성
static int n, m;
static int[] list; // 숫자들을 저장할 배열
static int[][] dp; // 메모이제이션을 위한 2차원 배열 (1: 팰린드롬, 0: 아님)
// 핵심 로직: DP 테이블 채우기
static void run() {
// [중요] w는 '구간의 길이'입니다. (Gap)
// 길이가 1인 구간부터 N-1인 구간까지 순서대로 구해야 합니다.
// 왜냐하면 길이가 5인 구간을 알기 위해선 길이가 3인 구간(내부)의 정보가 필요하기 때문입니다.
for (int w = 1; w < n; w++) {
// i는 시작 인덱스
for (int i = 1; i + w <= n; i++) {
int j = i + w; // j는 끝 인덱스
// 조건 1: 시작 숫자와 끝 숫자가 같아야 함
if (list[i] == list[j]) {
// 조건 2:
// Case A: 길이가 2라면(w=1) 무조건 팰린드롬 (ex: 1, 1)
// Case B: 그 사이 구간(i+1, j-1)이 이미 팰린드롬이라면 성공
if (w == 1 || dp[i + 1][j - 1] == 1) {
dp[i][j] = 1;
}
}
// (else dp[i][j]는 초기값 0 유지)
}
}
}
public static void main(String[] args) throws IOException {
// ✅ 해결책 1: BufferedReader 사용 (입력 속도 최적화)
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
list = new int[n + 1];
dp = new int[n + 1][n + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
list[i] = Integer.parseInt(st.nextToken());
// [기저 조건] 길이가 1인 구간(자기 자신)은 무조건 팰린드롬
dp[i][i] = 1;
}
// DP 알고리즘 수행 (이때 모든 구간의 팰린드롬 여부가 판별됨)
run();
m = Integer.parseInt(br.readLine());
// ✅ 해결책 2: StringBuilder 사용 (출력 속도 최적화)
StringBuilder sb = new StringBuilder();
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int s = Integer.parseInt(st.nextToken());
int e = Integer.parseInt(st.nextToken());
// 정답을 바로 출력하지 않고 메모리(버퍼)에 저장
sb.append(dp[s][e]).append('\n');
}
// 100만 개의 정답을 단 한 번의 I/O로 화면에 출력
System.out.print(sb);
}
}
6. 마치며: 알고리즘 그 너머의 최적화
백준 10942번은 단순히 '팰린드롬을 구할 줄 아느냐'를 묻는 문제가 아닙니다. "제한된 자원(시간) 안에서 대량의 데이터를 얼마나 효율적으로 다룰 수 있느냐"를 묻는 시스템적인 문제입니다.
앞으로 코딩 테스트에서 질문의 개수(M)나 출력해야 할 라인 수가 10만 단위를 넘어간다면, 반사적으로 System.out.println 사용을 멈추세요. 대신 StringBuilder나 BufferedWriter를 꺼내 드는 습관을 들여야 합니다. 이 작은 습관 하나가 '시간 초과'와 '맞았습니다'를 가르는 결정적인 열쇠가 될 것입니다. 오늘 겪은 이 시행착오가 여러분을 더 단단한 개발자로 만들어 줄 것입니다.