이 문서의 네 문제는 학습용으로 새로 구성한 문제입니다. 먼저 solution 함수만 직접 완성한 뒤 풀이를 확인하세요.
응시 방법
- 각 문제의 매개변수와 반환값부터 확인합니다.
- 제한사항을 근거로 목표 복잡도를 정합니다.
- 예시와 직접 만든 경계 사례를 손으로 검산합니다.
- 코드는 정답 값을
return하는solution함수로 작성합니다.
문제 1. 2인용 셔틀
승객 몸무게 배열 weights와 셔틀 한 대의 제한 무게 limit가 주어집니다. 셔틀에는 최대 두 명이 탈 수 있을 때 필요한 최소 셔틀 수를 반환하세요.
함수 시그니처: solution(weights, limit)
제한사항
- weights의 길이는 1 이상 200,000 이하입니다.
- 각 몸무게는 limit 이하입니다.
입출력 예
| 매개변수 | 반환값 |
|---|---|
[70, 50, 80, 50], 100 | 3 |
풀이와 코드 보기
핵심 패턴: 가장 무거운 사람을 기준으로 가장 가벼운 사람과 짝짓기
function solution(weights, limit) {
const sorted = [...weights].sort((a, b) => a - b);
let left = 0;
let right = sorted.length - 1;
let count = 0;
while (left <= right) {
if (left < right && sorted[left] + sorted[right] <= limit) left += 1;
right -= 1;
count += 1;
}
return count;
}- 시간복잡도:
O(n log n) - 공간복잡도:
O(n) - 경계 사례: 한 명만 남아도 셔틀 한 대 필요
문제 2. 최소 처리 속도
작업량 배열 jobs와 제한 시간 h가 주어집니다. 한 시간에 speed만큼 한 작업을 처리하고 다음 작업으로 넘어갈 때, h시간 안에 끝내는 최소 speed를 반환하세요.
함수 시그니처: solution(jobs, h)
제한사항
- jobs의 길이는 1 이상 100,000 이하입니다.
- h는 jobs의 길이 이상입니다.
입출력 예
| 매개변수 | 반환값 |
|---|---|
[3, 6, 7, 11], 8 | 4 |
풀이와 코드 보기
핵심 패턴: 속도가 충분한지 판정하며 최솟값 이분 탐색
function solution(jobs, h) {
let left = 1;
let right = jobs.reduce((max, job) => Math.max(max, job), 0);
while (left < right) {
const speed = Math.floor((left + right) / 2);
const hours = jobs.reduce((sum, job) => sum + Math.ceil(job / speed), 0);
if (hours <= h) right = speed;
else left = speed + 1;
}
return left;
}- 시간복잡도:
O(n log M) - 공간복잡도:
O(1) - 경계 사례: 속도 1로 가능하면 1 반환
문제 3. 격자 최단 이동
0은 이동 가능, 1은 벽인 직사각 격자 grid가 주어집니다. 왼쪽 위에서 오른쪽 아래까지 상하좌우 최단 이동 횟수를 반환하고 도달할 수 없으면 -1을 반환하세요.
함수 시그니처: solution(grid)
제한사항
- 행과 열은 각각 1 이상 500 이하입니다.
- 시작 칸과 도착 칸도 벽일 수 있습니다.
입출력 예
| 매개변수 | 반환값 |
|---|---|
[[0,0,1],[1,0,0],[1,1,0]] | 4 |
풀이와 코드 보기
핵심 패턴: 간선 비용이 같은 격자의 BFS
function solution(grid) {
const rows = grid.length;
const cols = grid[0].length;
if (grid[0][0] === 1 || grid[rows - 1][cols - 1] === 1) return -1;
const queue = [[0, 0, 0]];
const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
visited[0][0] = true;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let head = 0;
while (head < queue.length) {
const [row, col, distance] = queue[head++];
if (row === rows - 1 && col === cols - 1) return distance;
for (const [dr, dc] of directions) {
const nr = row + dr;
const nc = col + dc;
if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
if (grid[nr][nc] === 1 || visited[nr][nc]) continue;
visited[nr][nc] = true;
queue.push([nr, nc, distance + 1]);
}
}
return -1;
}- 시간복잡도:
O(RC) - 공간복잡도:
O(RC) - 경계 사례: 시작 또는 도착이 벽이면 즉시 -1
문제 4. 최대 상담 수
상담 시간 구간 배열 intervals가 주어집니다. 한 상담이 끝난 시각에 다음 상담을 시작할 수 있을 때 겹치지 않게 선택할 수 있는 최대 상담 수를 반환하세요.
함수 시그니처: solution(intervals)
제한사항
- intervals의 길이는 1 이상 200,000 이하입니다.
- 각 구간은 [시작, 종료]이며 시작은 종료보다 작습니다.
입출력 예
| 매개변수 | 반환값 |
|---|---|
[[1,4],[2,3],[3,5],[5,7]] | 3 |
풀이와 코드 보기
핵심 패턴: 종료 시각이 빠른 구간부터 선택
function solution(intervals) {
const sorted = [...intervals].sort((a, b) => a[1] - b[1] || a[0] - b[0]);
let end = -Infinity;
let count = 0;
for (const [start, finish] of sorted) {
if (start < end) continue;
end = finish;
count += 1;
}
return count;
}- 시간복잡도:
O(n log n) - 공간복잡도:
O(n) - 경계 사례: 종료와 시작이 같은 두 상담은 함께 선택 가능
중급 모의고사 점검표
- 문제를 읽자마자 자료구조를 정하지 않고 제한사항부터 확인했는가
- 풀이의 정당성을 한두 문장으로 설명할 수 있는가
- 빈 결과, 한 원소, 중복, 도달 불가 같은 경계를 확인했는가
- 시간복잡도와 공간복잡도를 직접 계산했는가
확인 문제
문제 14지선다
2인용 셔틀의 핵심 풀이 패턴은?
문제 24지선다
2인용 셔틀 풀이의 시간복잡도는?
문제 34지선다
2인용 셔틀에서 확인할 경계 사례는?
문제 44지선다
최소 처리 속도의 핵심 풀이 패턴은?
문제 54지선다
최소 처리 속도 풀이의 시간복잡도는?
문제 64지선다
최소 처리 속도에서 확인할 경계 사례는?
문제 74지선다
격자 최단 이동의 핵심 풀이 패턴은?
문제 84지선다
격자 최단 이동 풀이의 시간복잡도는?
문제 94지선다
격자 최단 이동에서 확인할 경계 사례는?
문제 104지선다
최대 상담 수의 핵심 풀이 패턴은?
문제 114지선다
최대 상담 수 풀이의 시간복잡도는?
문제 124지선다
최대 상담 수에서 확인할 경계 사례는?
문제 134지선다
제한사항을 먼저 읽는 가장 중요한 이유는?
문제 144지선다
정렬이 필요하지만 원본 배열도 이후 사용한다면?
문제 154지선다
채점기가 확인하는 최종 결과는?
참고 자료
Last updated on