Coding Interview Prep · 课时

查找序列中的间隙

Q: 「查找序列中的间隙」这节课中我会学到什么？

检测缺失值以及每个间隙的起点和终点 你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

检测缺失值以及每个间隙的起点和终点

查找序列中的间隙 是 CoddyKit 上的免费 Coding Interview Prep 课时。这是第 3 节课，共 4 节。你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。这是 Coding Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Coding Interview Prep 课程共包含 4 节课。

이제 공백을 찾아봅시다

지금까지는 행을 구간으로 묶었습니다. 이와 반대되는 면접 질문은 어떤 값이 빠졌는가?입니다. 면접관은 이를 '이 ID 수열의 공백을 찾으십시오', '건너뛴 청구서 번호는 무엇입니까', 또는 '활동이 없었던 날은 언제입니까'와 같이 표현합니다.

공백은 구간 사이에 있는 빈 공간입니다. 여기서 중요한 점은 보통 누락된 값을 하나씩 모두 나열할 필요가 없다는 것입니다. 대신 각 공백 범위의 시작과 끝을 보고해야 하며, 이것이 훨씬 간결하고 면접관이 기대하는 방식입니다.

공백 예시 데이터셋

seq(n) 테이블에 있는 기존 값 1, 2, 3, 7, 8, 10을 다시 사용하겠습니다. 보고해야 할 공백은 다음과 같습니다.

4부터 6까지 (첫 번째 구간 뒤, 7 앞)
9부터 9까지 (8과 10 사이)

공백을 범위로 표현한다는 점에 주목하십시오. 공백 시작 값은 마지막으로 존재하는 값 + 1이고, 공백 끝 값은 다음으로 존재하는 값 - 1입니다. 아래의 핵심 기법이 목표로 하는 것이 바로 이 간결한 형식입니다.

CREATE TABLE seq (n INT);
INSERT INTO seq VALUES (1),(2),(3),(7),(8),(10);

공백을 찾는 LEAD 접근법

가장 깔끔한 공백 탐지 방법은 LEAD를 사용하여 각 행을 다음 행과 비교하는 것입니다. 다음 값이 현재 값보다 1 초과로 크다면 두 값 사이에 공백이 있습니다.

그러한 각 행에서 공백은 n + 1에서 시작하고 next_n - 1에서 끝납니다. 먼저 가공하지 않은 LEAD 결과를 살펴보십시오.

SELECT
  n,
  LEAD(n) OVER (ORDER BY n) AS next_n
FROM seq
ORDER BY n;

공백 범위 보고하기

LEAD 결과를 CTE로 감싼 뒤 다음 값으로의 증가 폭이 1을 초과하는 행만 남기십시오. 해당 행이 공백을 나타냅니다.

이 결과는 공백 4-6과 공백 9-9를 정확히 반환합니다. 또한 next_n - n - 1 표현식은 각 공백에서 누락된 값의 개수도 알려 주므로 자주 이어지는 추가 질문에 활용할 수 있습니다.

WITH stepped AS (
  SELECT n, LEAD(n) OVER (ORDER BY n) AS next_n
  FROM seq
)
SELECT
  n + 1            AS gap_start,
  next_n - 1       AS gap_end,
  next_n - n - 1   AS missing_count
FROM stepped
WHERE next_n - n > 1
ORDER BY gap_start;

대칭적인 LAG 변형

대신 LAG를 사용하여 이전 방향을 살펴보아도 같은 공백을 찾을 수 있습니다. 이전 값이 현재 값보다 1 초과로 작다면 현재 행 앞에 공백이 있습니다.

두 방법은 완전히 동일하므로 질문에 더 자연스럽게 읽히는 쪽을 선택하십시오. 일부 면접관은 공백을 그 앞의 행을 기준으로 설명하는 LEAD를 선호합니다. 사람들이 말하는 방식과 더 잘 맞기 때문입니다.

WITH stepped AS (
  SELECT n, LAG(n) OVER (ORDER BY n) AS prev_n
  FROM seq
)
SELECT prev_n + 1 AS gap_start,
       n - 1       AS gap_end
FROM stepped
WHERE n - prev_n > 1
ORDER BY gap_start;

누락된 값 모두 나열하기

때로는 면접관이 범위만이 아니라 누락된 숫자의 전체 목록을 요구합니다. 이때는 예상되는 전체 수열을 생성한 뒤 실제로 존재하는 값과 반조인하는 것이 가장 견고한 방법입니다. Postgres에서는 generate_series로 전체 범위를 만들 수 있습니다.

seq에 존재하지 않는 예상 범위 내의 모든 정수가 누락된 값입니다. 의도한 최솟값과 최댓값을 알고 있다면 이 방법으로 양 끝의 공백도 처리할 수 있습니다.

SELECT g.n AS missing_value
FROM generate_series(
       (SELECT MIN(n) FROM seq),
       (SELECT MAX(n) FROM seq)
     ) AS g(n)
LEFT JOIN seq s ON s.n = g.n
WHERE s.n IS NULL
ORDER BY g.n;

데이터베이스별 수열 생성

모든 엔진에 generate_series가 있는 것은 아닙니다. 다음 대안을 알아 두십시오.

Postgres: generate_series(1, 100)
SQL Server: 재귀 CTE 또는 숫자 테이블을 사용합니다.
MySQL 8: 최댓값까지 세는 재귀 CTE를 사용합니다.

재귀 CTE는 이식성이 높은 대체 방법입니다. 반조인할 동일한 예상 수열을 생성합니다.

WITH RECURSIVE nums AS (
  SELECT (SELECT MIN(n) FROM seq) AS n
  UNION ALL
  SELECT n + 1 FROM nums
  WHERE n + 1 <= (SELECT MAX(n) FROM seq)
)
SELECT nums.n AS missing_value
FROM nums
LEFT JOIN seq s ON s.n = nums.n
WHERE s.n IS NULL;

달력 날짜의 공백

누락된 날짜를 찾으려면 하루 간격으로 전체 달력을 생성한 뒤 반조인하십시오. 이것은 '주문이 없었던 날은 언제인가'라는 질문에 대한 표준 쿼리입니다.

실제 날짜에 LEAD를 적용하여 개별 날짜가 아닌 누락된 날짜의 기간을 보고하면 범위 기법과 결합할 수 있습니다. 경계에는 + INTERVAL '1 day'를 사용하십시오.

SELECT d::date AS missing_day
FROM generate_series(
       DATE '2026-01-01', DATE '2026-01-31',
       INTERVAL '1 day') AS d
LEFT JOIN daily_logins l ON l.login_date = d::date
WHERE l.login_date IS NULL
ORDER BY missing_day;

데이터 범위를 넘어선 양 끝의 공백

미묘한 함정이 하나 있습니다. LEAD와 LAG는 현재 값이 존재하는 값 사이의 공백만 찾습니다. 현재 존재하는 최솟값보다 앞이나 최댓값보다 뒤에 숫자가 누락되어 있으면 이 윈도우 접근법으로는 찾을 수 없습니다. 인접한 행이 없기 때문입니다.

면접관이 예상되는 전체 범위(예: ID 1부터 100까지)를 정의했는데 데이터가 5에서 시작한다면, 데이터 자체의 최솟값과 최댓값이 아니라 선언된 범위를 경계로 하는 generate_series 반조인을 사용해야 합니다. 예상 경계가 고정되어 있는지 항상 확인하십시오.

SELECT g.n AS missing_value
FROM generate_series(1, 100) AS g(n)
LEFT JOIN seq s ON s.n = g.n
WHERE s.n IS NULL;

그룹별 공백 탐지

사용자별 공백을 찾으려면 그룹 열을 기준으로 LEAD와 LAG를 PARTITION하십시오. 이렇게 하면 서로 다른 사용자의 흐름을 가로질러 공백이 보고되는 일이 없습니다.

각 사용자의 누락 범위가 독립적으로 계산됩니다. 구간을 찾을 때와 마찬가지로 PARTITION을 빠뜨리면 사용자가 조용히 합쳐져 서로 관계없는 행 사이에 가짜 공백이 생깁니다.

WITH stepped AS (
  SELECT user_id, n,
    LEAD(n) OVER (PARTITION BY user_id ORDER BY n) AS next_n
  FROM seq_per_user
)
SELECT user_id, n + 1 AS gap_start, next_n - 1 AS gap_end
FROM stepped
WHERE next_n - n > 1
ORDER BY user_id, gap_start;

알맞은 공백 탐지 방법 선택하기

면접에서 사용할 판단 기준은 다음과 같습니다.

간결한 범위가 필요하고 데이터 내부의 공백만 찾는다면 LEAD와 LAG를 사용하고, 증가 폭이 1을 초과하는 경우만 필터링하십시오.
누락된 값을 하나씩 모두 찾거나 데이터 양 끝을 넘어선 공백까지 찾아야 한다면 선언된 전체 범위와 generate_series 반조인을 사용하십시오.

두 방법을 모두 언급하고 각각 언제 적용하는지 설명하면 깊이 있는 이해를 보여 줄 수 있습니다. LEAD 방법은 비용이 더 적고, 수열 방법은 더 완전합니다.

빠른 확인

양 끝의 공백과 관련된 함정을 확실히 이해하십시오.

정리: 공백 찾기

이제 공백 탐지를 정리해 보겠습니다.

공백은 범위로 보고하십시오. 공백 시작 값 = 값 + 1, 공백 끝 값 = 다음 값 - 1입니다.
증가 폭이 1을 초과하는 경우만 필터링한 LEAD(또는 대칭적인 LAG)로 데이터 내부의 공백을 저렴하게 찾을 수 있습니다.
generate_series 반조인은 누락된 값을 하나씩 나열하고, 선언된 범위를 기준으로 양 끝의 공백도 찾습니다.
generate_series가 없는 곳에서는 재귀 CTE로 수열을 생성합니다.
사용자별 공백을 찾으려면 그룹 열을 기준으로 PARTITION하십시오.
예상되는 경계를 항상 확인하십시오.

마지막으로 날짜와 상태 변경으로 정의되는 가장 풍부한 형태의 구간을 살펴보겠습니다.

常见问题解答

「查找序列中的间隙」课时是免费的吗？

是的 — 「查找序列中的间隙」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Coding Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 Coding Interview Prep 课程共包含 4 节课。

「查找序列中的间隙」这节课中我会学到什么？

检测缺失值以及每个间隙的起点和终点你通过在浏览器中直接运行的动手代码来练习 Coding Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。

学习 Coding Interview Prep 需要有经验吗？

无需任何先前经验。CoddyKit 上的 Coding Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。这是第 3 节课，共 4 节。

「查找序列中的间隙」课时需要多长时间？

大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。

我能在这节 Coding Interview Prep 课中编写并运行代码吗？

能。每节 Coding Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。

此课程中的所有课时

← 返回 Coding Interview Prep