[코딩테스트] 3. 실전 사례 분석

사례 1: BOJ 21921 블로그 (시간 초과)

문제 조건

항목	값
시간 제한	1초
메모리 제한	512MB
N (일수)	최대 250,000
X (기간)	최대 N

X일 동안 가장 많이 들어온 방문자 수와, 그런 기간이 몇 개인지 구하는 문제다.

---

시간 초과 코드

int max = Integer.MIN_VALUE;
for (int i = 0; i < input.length - x + 1; i++) {
    int now = 0;
    for (int j = 0; j < x; j++)
        now += input[i + j];
    max = Math.max(max, now);
}

int r = 0;
for (int i = 0; i < input.length - x + 1; i++) {
    int now = 0;
    for (int j = 0; j < x; j++)
        now += input[i + j];
    if (now == max) r++;
}

• 바깥 루프가 N - X + 1번, 안쪽 루프가 X번 돌면서 매번 구간 합을 처음부터 다시 계산한다
• 게다가 이 이중 루프가 두 번 반복된다 (최대값 찾기 + 개수 세기)
• 총 연산 횟수: 2 × (N - X + 1) × X

최악의 경우 연산 횟수 계산

N = 250,000, X = 125,000 (N/2일 때 연산이 최대)

2 × (250,000 - 125,000 + 1) × 125,000
= 2 × 125,001 × 125,000
≈ 31,250,000,000 (약 312억)

Java 기준 1초 ≈ 1억 연산이므로, 약 312초가 필요하다. 시간 초과는 당연한 결과다.

허용 복잡도 표를 떠올려보면, N ≤ 250,000이면 O(N log N) 이하가 필요하다. O(N × X)는 최악의 경우 O(N²)이므로 처음부터 통과 불가능한 접근이었다.

---

수정 코드 (슬라이딩 윈도우)

int max = 0;
int count = 1;
int now = 0;

for (int i = 0; i < x; i++)
    now += input[i];

for (int i = x; i < input.length; i++) {
    now = now - input[i - x] + input[i];
    if (max < now) {
        max = now;
        count = 1;
    } else if (max == now) {
        count++;
    }
}

• 첫 번째 루프에서 처음 X일의 합을 구한다 → O(X)
• 두 번째 루프에서 윈도우를 한 칸씩 밀면서, 빠지는 값은 빼고 들어오는 값은 더한다 → 각 반복이 O(1)
• 최대값 비교와 개수 세기를 한 번의 루프에서 동시에 처리한다
• 총 복잡도: O(N)

핵심 아이디어는 간단하다. 연속 구간을 한 칸 옮기면, 전체를 다시 더할 필요 없이 왼쪽 끝 하나 빼고, 오른쪽 끝 하나 더하면 된다. 이것이 슬라이딩 윈도우의 본질이다.

[ 1  3  2  5  4 ]  윈도우 크기 3

첫 번째:  [1  3  2] 5  4   합 = 6
두 번째:   1 [3  2  5] 4   합 = 6 - 1 + 5 = 10
세 번째:   1  3 [2  5  4]  합 = 10 - 3 + 4 = 11

사례 2: BOJ 2559 수열 (메모리 초과)

문제 조건

항목	값
시간 제한	1초
메모리 제한	128MB
N (날짜 수)	최대 100,000
K (연속 일수)	최대 N

연속 K일의 온도 합이 최대가 되는 값을 구하는 문제다. 블로그 문제와 거의 같은 구조지만, 메모리 제한이 128MB로 더 엄격하다.

---

메모리 초과 코드

for (int i = 0; i < k; i++) {
    int sum = IntStream.of(Arrays.copyOfRange(temps, i, i + k)).sum();
    answer = Math.max(sum, answer);
}

• 매 반복마다 Arrays.copyOfRange가 크기 K짜리 새 배열을 생성한다
• IntStream.of()도 내부적으로 스트림 객체를 생성한다
• 루프 조건도 i < k로 잘못되어 있다 (N - K + 1번 돌아야 하는데 K번만 돈다)

왜 메모리 초과인가

단순 계산으로 보면, 루프마다 int[K] 배열(4K bytes)이 생성된다. K = 100,000이면 배열 하나가 약 400KB다.

문제는 Java의 GC가 루프가 빠르게 도는 동안 수거를 제때 못 할 수 있다는 것이다. 배열 객체와 스트림 객체가 메모리에 쌓이면서 128MB 제한을 넘게 된다.

그리고 시간 측면에서도 O(K²)이므로 (K번 루프 × K개 복사+합산), K가 크면 시간 초과도 함께 발생할 수 있다.

---

수정 코드 (슬라이딩 윈도우)

int sum = IntStream.of(Arrays.copyOfRange(temps, 0, k)).sum();
int answer = sum;

for (int i = 1; i < n - k + 1; i++) {
    sum = sum - temps[i - 1] + temps[i + k - 1];
    answer = Math.max(answer, sum);
}

• 초기 합만 한 번 구하고, 이후에는 배열을 새로 만들지 않는다
• 루프 안에서 빼기 하나 + 더하기 하나 + 비교 하나 → O(1)
• 전체 복잡도: O(N), 추가 메모리: O(1)

메모리 초과 문제는 결국 "불필요한 객체 생성을 줄이기"로 해결된다. 슬라이딩 윈도우는 시간뿐 아니라 공간 효율성에서도 압도적이다.

두 사례의 공통 패턴

두 문제 모두 "연속 구간의 합"을 구하는 문제였고, 둘 다 같은 실수를 했다.

항목	시간 초과 풀이	슬라이딩 윈도우
매 구간마다	처음부터 끝까지 다시 합산	양 끝만 갱신
시간복잡도	O(N × K)	O(N)
공간복잡도	O(K) 또는 그 이상	O(1)
핵심 차이	중복 계산	이전 결과 재활용

실전 판단 프로세스 적용

이 두 문제에 판단 프로세스를 적용하면 이렇게 된다.

BOJ 21921

1. N ≤ 250,000 확인
2. 허용 복잡도 표에서 → O(N log N) 이하 필요
3. 이중 for문 = O(N × X) ≈ O(N²) → 통과 불가
4. "연속 구간 합" → 슬라이딩 윈도우 = O(N) → 통과 가능
5. 구현

BOJ 2559

1. N ≤ 100,000 확인
2. 허용 복잡도 표에서 → O(N log N) 이하 필요
3. copyOfRange 루프 = O(N × K) ≈ O(N²) → 통과 불가 + 메모리 위험
4. 슬라이딩 윈도우 = O(N) → 통과 가능
5. 구현

두 경우 모두 2~3번 단계에서 "이건 안 되겠다"고 판단할 수 있었다. 코드를 쓰기 전에 계산하는 습관이 있었다면, 시간 초과를 받지 않고 바로 올바른 접근을 했을 것이다.

---

면접 대비 Q&A