재구성 출제 고지: 이 편의 문제 4개는 실제 온라인 저지의 기출 문제를 옮긴 것이 아니라, 03~16편에서 다룬 여러 유형을 섞어 새로운 상황으로 재구성한 문제입니다. · 형식: LeetCode처럼 class Solution의 메서드를 완성하는 방식입니다. 마지막에는 이 저장소 전체를 정리하는 오답 노트 작성법을 다룹니다.
이 편에서 만드는 파일
coding-test/
└── 19-mock-test-3/
├── 01-pair-sum-limit/
│ ├── solution.js (+)
│ └── solution.test.js (+)
├── 02-bracket-variants/
│ ├── solution.js (+)
│ └── solution.test.js (+)
├── 03-kth-smallest-heap/
│ ├── solution.js (+)
│ └── solution.test.js (+)
├── 04-network-delay/
│ ├── solution.js (+)
│ └── solution.test.js (+)
└── README.md (+, 오답 노트)문제 3·4의 solution.js는 12편의 lib/MinHeap.js를 그대로 import합니다. 같은 자료구조를 편마다 다시 구현하지 않고, 이미 검증된 MinHeap(compare)를 재사용합니다.
문제
문제 1. 합이 limit 이하인 최대 쌍 개수 (난이도: 하, 투 포인터)
정수 배열 nums와 정수 limit이 주어집니다. 서로 다른 두 원소를 하나씩 짝지어 합이 limit 이하가 되게 할 때, 각 원소를 최대 한 번만 쓸 수 있다면 만들 수 있는 쌍의 최대 개수를 구하는 countPairs(nums, limit) 메서드를 작성하세요.
입력: nums = [1, 2, 3, 4, 5], limit = 6
출력: 2문제 2. 혼합 괄호 유효성 검사 (난이도: 중, 스택)
소괄호 (, 대괄호 [, 중괄호 {와 그 짝, 그리고 그 외의 일반 문자가 섞인 문자열 text가 주어집니다. 괄호가 아닌 문자는 무시하고, 괄호만 봤을 때 종류와 순서가 올바르게 짝지어지면 true, 아니면 false를 반환하는 isValid(text) 메서드를 작성하세요.
입력: "a(b[c]{d}e)f"
출력: true입력: "([)]"
출력: false문제 3. K번째로 작은 원소 (난이도: 중상, 힙)
정수 배열 nums와 정수 k가 주어집니다. 배열을 정렬하지 않고 12편의 MinHeap을 재사용해 k번째로 작은 값(1번째가 가장 작은 값)을 구하는 findKthSmallest(nums, k) 메서드를 작성하세요.
입력: nums = [7, 2, 9, 4, 1], k = 3
출력: 4문제 4. 네트워크 신호 전달 최소 시간 (난이도: 상, 최단 경로)
1번부터 n번까지 노드가 있는 방향 그래프에서 간선 정보 edges(각 원소는 [from, to, weight])와 신호를 보내는 시작 노드 start가 주어집니다. start에서 모든 노드까지의 최단 시간 중 가장 오래 걸리는 시간을 구하는 networkDelayTime(n, edges, start) 메서드를 작성하세요. 모든 노드에 도달할 수 없으면 -1을 반환합니다. 11~12편에서 다룬 힙 기반 다익스트라와 같은 방식으로 O((V+E)logV)에 구현하세요.
입력: n = 4, edges = [[1, 2, 1], [2, 3, 2], [1, 3, 4], [3, 4, 1]], start = 1
출력: 4풀이
문제 1 풀이 — 합이 limit 이하인 최대 쌍 개수
접근
배열을 오름차순 정렬한 뒤 양 끝에서 시작하는 두 포인터를 둡니다. 가장 작은 값과 가장 큰 값의 합이 limit 이하면 짝을 짓고 양쪽 포인터를 좁힙니다. 합이 limit을 넘으면 가장 큰 값은 남은 어떤 값과도 짝지을 수 없으므로 그 값만 포기하고 오른쪽 포인터만 좁힙니다.
복잡도
정렬에 O(n log n), 두 포인터 이동에 O(n)이 걸려 전체 O(n log n)입니다.
코드
// coding-test/19-mock-test-3/01-pair-sum-limit/solution.js
// 시간복잡도: O(n log n) — 정렬 후 두 포인터로 한 번 순회한다
// 공간복잡도: O(n) — 정렬된 복사본 배열을 만든다
export class Solution {
countPairs(nums, limit) {
const sorted = [...nums].sort((a, b) => a - b);
let left = 0;
let right = sorted.length - 1;
let pairCount = 0;
while (left < right) {
if (sorted[left] + sorted[right] <= limit) {
pairCount += 1;
left += 1;
right -= 1;
} else {
right -= 1;
}
}
return pairCount;
}
}테스트
// coding-test/19-mock-test-3/01-pair-sum-limit/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { Solution } from './solution.js';
test('합이 limit 이하인 쌍의 최대 개수를 구한다', () => {
const solution = new Solution();
assert.strictEqual(solution.countPairs([1, 2, 3, 4, 5], 6), 2);
});
test('짝지을 수 있는 쌍이 하나뿐이면 1을 반환한다', () => {
const solution = new Solution();
assert.strictEqual(solution.countPairs([3, 5, 3, 4], 6), 1);
});
test('원소가 하나면 0을 반환한다', () => {
const solution = new Solution();
assert.strictEqual(solution.countPairs([5], 10), 0);
});함정
정렬하지 않고 두 포인터를 바로 적용하면 가장 작은 값과 가장 큰 값을 알 수 없어 그리디 자체가 성립하지 않습니다. 또한 합이 limit을 넘었을 때 left가 아니라 right를 줄여야 합니다. 남은 값 중 가장 작은 값(left)과도 짝지을 수 없는 값은 가장 큰 값(right)이기 때문입니다.
문제 2 풀이 — 혼합 괄호 유효성 검사
접근
여는 괄호는 스택에 쌓고, 닫는 괄호를 만나면 스택 맨 위와 짝이 맞는지 확인합니다. 괄호가 아닌 문자는 그냥 지나칩니다.
복잡도
시간 복잡도는 O(n)입니다(n은 문자열 길이).
코드
// coding-test/19-mock-test-3/02-bracket-variants/solution.js
// 시간복잡도: O(n) — 문자열 길이만큼 한 번 순회한다
// 공간복잡도: O(n) — 여는 괄호를 담는 스택을 사용한다
const CLOSING_TO_OPENING = {
')': '(',
']': '[',
'}': '{',
};
const OPENING_CHARS = new Set(['(', '[', '{']);
export class Solution {
isValid(text) {
const stack = [];
for (const char of text) {
if (OPENING_CHARS.has(char)) {
stack.push(char);
continue;
}
if (char in CLOSING_TO_OPENING) {
const lastOpening = stack.pop();
if (lastOpening !== CLOSING_TO_OPENING[char]) {
return false;
}
}
// 괄호가 아닌 문자는 무시합니다.
}
return stack.length === 0;
}
}테스트
// coding-test/19-mock-test-3/02-bracket-variants/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { Solution } from './solution.js';
test('일반 문자가 섞여도 괄호만 검사한다', () => {
const solution = new Solution();
assert.strictEqual(solution.isValid('a(b[c]{d}e)f'), true);
});
test('종류는 맞지만 순서가 어긋나면 false다', () => {
const solution = new Solution();
assert.strictEqual(solution.isValid('([)]'), false);
});
test('닫는 괄호가 남으면 false다', () => {
const solution = new Solution();
assert.strictEqual(solution.isValid('((('), false);
});
test('괄호가 없는 문자열은 true다', () => {
const solution = new Solution();
assert.strictEqual(solution.isValid('abc'), true);
});함정
닫는 괄호를 만났을 때 char in CLOSING_TO_OPENING처럼 명시적으로 확인하지 않고 그냥 CLOSING_TO_OPENING[char]가 있는지만 느슨하게 검사하면, 괄호가 아닌 문자까지 스택 연산에 끼어드는 실수가 생기기 쉽습니다. 여는 괄호(OPENING_CHARS)와 닫는 괄호(CLOSING_TO_OPENING) 판정을 분리해두면 이런 실수를 줄일 수 있습니다.
문제 3 풀이 — K번째로 작은 원소
접근
12편에서 만든 배열 기반 최소 힙 MinHeap을 그대로 import해 재사용합니다. 모든 원소를 힙에 넣은 뒤 최솟값을 k번 꺼내면 k번째로 작은 값을 얻습니다.
복잡도
원소를 하나씩 push해 힙을 만드는 데 O(n log n)(배열을 통째로 힙 구조로 바꾸는 heapify는 O(n)이지만, 하나씩 넣는 이 방식은 그보다 느립니다), 이후 k번 추출하는 데 O(k log n)이 걸려 전체 O(n log n)입니다.
코드
// coding-test/19-mock-test-3/03-kth-smallest-heap/solution.js
// 시간복잡도: O(n log n) — 원소 n개를 힙에 넣고(O(n log n)) k번 꺼낸다
// 공간복잡도: O(n) — 모든 원소를 힙에 저장한다
import { MinHeap } from '../../12-tree-heap/lib/MinHeap.js';
export class Solution {
findKthSmallest(nums, k) {
const heap = new MinHeap();
for (const value of nums) {
heap.push(value);
}
let result;
for (let i = 0; i < k; i += 1) {
result = heap.pop();
}
return result;
}
}테스트
// coding-test/19-mock-test-3/03-kth-smallest-heap/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { Solution } from './solution.js';
test('k가 1이면 최솟값을 반환한다', () => {
const solution = new Solution();
assert.strictEqual(solution.findKthSmallest([7, 2, 9, 4, 1], 1), 1);
});
test('k번째로 작은 값을 정확히 찾는다', () => {
const solution = new Solution();
assert.strictEqual(solution.findKthSmallest([7, 2, 9, 4, 1], 3), 4);
});
test('k가 배열 길이와 같으면 최댓값을 반환한다', () => {
const solution = new Solution();
assert.strictEqual(solution.findKthSmallest([7, 2, 9, 4, 1], 5), 9);
});함정
힙에 원소를 전부 넣고 k번 꺼내는 방식은 k가 배열 크기와 비슷하면 정렬과 성능 차이가 거의 없습니다. k가 매우 작을 때는 “크기 k짜리 최대 힙만 유지”하는 방식이 더 효율적이지만, 이 문제는 12편의 MinHeap을 재사용하는 것이 목적이라 단순한 방식을 씁니다.
문제 4 풀이 — 네트워크 신호 전달 최소 시간
접근
다익스트라 알고리즘을 최소 힙으로 최적화합니다. 12편의 MinHeap(compare)에 [거리, 노드] 쌍을 거리 기준으로 비교하는 함수 (a, b) => a[0] - b[0]을 넘겨, 항상 현재까지 가장 가까운 노드부터 꺼내 인접 노드의 거리를 갱신합니다.
복잡도
시간 복잡도는 O((V+E)logV)입니다(V는 노드 수, E는 간선 수).
코드
// coding-test/19-mock-test-3/04-network-delay/solution.js
// 시간복잡도: O((V+E)logV) — 간선마다 최대 한 번씩 힙에 넣고 꺼낸다
// 공간복잡도: O(V + E) — 거리 배열과 힙, 인접 리스트를 사용한다
import { MinHeap } from '../../12-tree-heap/lib/MinHeap.js';
export class Solution {
networkDelayTime(n, edges, start) {
const adjacencyList = Array.from({ length: n + 1 }, () => []);
for (const [from, to, weight] of edges) {
adjacencyList[from].push([to, weight]);
}
const shortestDistance = new Array(n + 1).fill(Infinity);
shortestDistance[start] = 0;
// [거리, 노드] 쌍을 거리 기준으로 비교하는 최소 힙입니다.
const heap = new MinHeap((a, b) => a[0] - b[0]);
heap.push([0, start]);
while (heap.size > 0) {
const [distance, node] = heap.pop();
if (distance > shortestDistance[node]) continue;
for (const [neighbor, weight] of adjacencyList[node]) {
const candidateDistance = distance + weight;
if (candidateDistance < shortestDistance[neighbor]) {
shortestDistance[neighbor] = candidateDistance;
heap.push([candidateDistance, neighbor]);
}
}
}
let maxDistance = 0;
for (let node = 1; node <= n; node += 1) {
if (shortestDistance[node] === Infinity) return -1;
maxDistance = Math.max(maxDistance, shortestDistance[node]);
}
return maxDistance;
}
}테스트
// coding-test/19-mock-test-3/04-network-delay/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { Solution } from './solution.js';
test('모든 노드에 도달 가능하면 가장 오래 걸리는 시간을 반환한다', () => {
const solution = new Solution();
const edges = [[1, 2, 1], [2, 3, 2], [1, 3, 4], [3, 4, 1]];
assert.strictEqual(solution.networkDelayTime(4, edges, 1), 4);
});
test('도달할 수 없는 노드가 있으면 -1을 반환한다', () => {
const solution = new Solution();
assert.strictEqual(solution.networkDelayTime(3, [[1, 2, 1]], 1), -1);
});함정
힙에서 꺼낸 [distance, node]가 이미 알고 있는 shortestDistance[node]보다 크면 그냥 버려야 합니다(if (distance > shortestDistance[node]) continue;). 이 검사를 빼면, 나중에 더 짧은 경로가 발견되기 전에 넣어둔 오래된(더 긴) 거리 값까지 다시 꺼내 인접 노드를 불필요하게 재처리하게 됩니다.
오답 노트 작성법
문제를 채점 없이 스스로 검증할 때는 틀린 이유를 감으로 넘기지 말고 아래처럼 유형별로 분류해 기록합니다. 같은 유형이 반복되면 그 유형만 집중적으로 복습할 수 있습니다.
| 유형 | 증상 | 점검 방법 | 예방 습관 |
|---|---|---|---|
| 문제 이해 오류 | 테스트는 통과했는데 새로운 입력에서 전혀 다른 결과가 나옴 | 문제 조건을 다시 읽고 주어진 예시를 손으로 직접 계산 | 코드를 짜기 전에 입력과 출력 예시를 표로 먼저 정리 |
| 자료구조 선택 오류 | 결과는 맞지만 입력이 커지면 눈에 띄게 느려짐 | 사용한 자료구조의 조회·삽입 복잡도를 02편 표로 재확인 | 코드를 짜기 전에 “이 연산을 몇 번 반복하는가”부터 계산 |
| 경계값 누락 | 특정 테스트(빈 입력, 단일 원소, 중복값)만 실패 | 빈 배열·최솟값·최댓값을 직접 넣어 재현 | 코드 작성 전 함정이 될 만한 입력을 먼저 나열 |
| 오프바이원 | 결과가 정답보다 근소하게 크거나 작음 | 작은 예시를 손으로 인덱스까지 추적 | 반복문 경계에 <를 쓸지 <=를 쓸지 항상 다시 확인 |
| 상태 갱신 순서 실수 | 첫 번째 또는 마지막 처리 결과만 이상함 | 상태를 읽는 시점과 쓰는 시점을 주석으로 표시해 순서 확인 | ”읽기 → 계산 → 쓰기” 순서를 고정 패턴으로 삼기 |
README 오답 노트 예시
coding-test/19-mock-test-3/README.md에 아래 형식으로 틀린 문제를 기록합니다. 날짜와 파일명, 위 분류표의 유형, 증상과 원인, 고친 방법, 재발 방지책을 한 세트로 남깁니다.
# 오답 노트
## 2026-09-20 - problem3-max-score-path
- 유형: 오프바이원
- 증상: 패드가 2개일 때 결과가 예상보다 작게 나옴
- 원인: dp 배열은 1-indexed인데 scores 배열 접근을 0-indexed 그대로 써서 한 칸 어긋남
- 고친 방법: dp[i]가 몇 번째 패드인지 주석으로 표시하고 n=2 예시를 손으로 다시 추적
- 재발 방지: 인덱스 방식이 섞이는 함수는 상단에 1-indexed 여부를 주석으로 남긴다직접 해보기
- 이번 편 4문제 중 스스로 가장 오래 걸린 문제 하나를 골라, 위 분류표 중 어떤 유형에 해당하는지 README 형식으로 직접 기록해보세요.
- 문제 3의
findKthSmallest를 힙 크기를k로 제한하는 “최대 힙 유지” 방식으로 바꿔 같은 테스트가 통과하는지 확인해보세요.
자주 하는 실수
| 증상 | 원인 | 고치는 법 |
|---|---|---|
| 틀린 문제를 다시 풀 때 왜 틀렸는지 기억이 안 남 | 채점 직후 원인을 기록하지 않고 넘어감 | 틀린 즉시 위 분류표 형식으로 짧게라도 기록 |
| 같은 유형의 실수가 계속 반복됨 | 오답 노트를 문제별로만 적고 유형별로 모아보지 않음 | 주기적으로 README를 유형별로 다시 훑어봄 |
MinHeap을 가져다 쓰기만 하고 동작 원리를 모름 | import만 하고 내부 구현은 다시 보지 않음 | 12편의 push/pop/bubbleUp/bubbleDown을 손으로 다시 짤 수 있는지 스스로 확인 |