mysql 쿼리 문제를 풀다보면 consecutive numbers를 찾는 문제는 주로 n번 이상 연속으로 나오는 동일한 수를 찾거나 n번 이상 연속하는 수 전체를 찾는 유형으로 나눠지는 것 같다.
n번 이상 연속으로 나오는 동일한 수 : leetcode 180
⇒ 3,3,3,3 같이 같은 수가 n번 이상 연속해서 나옴
n번 이상 연속하는 수 전체 : leetcode 601
⇒ 3,4,5,6 같이 연속한 수를 n개 이상 나옴
MYSQL의 경우, consecutive numbers를 찾을 때 자주 사용하는 방법 self-join, window functions 특히lead, lag 이다.
이 외에도 연속하는 수의 특성을 이용한 방법이 있다.
오늘은 leetcode.601 풀이를 통해 lead,lag 함수를 이용해 푸는 법과 연속하는 수의 특성을 이용한 방법 모두 접근해보려고 한다.
Leetcode601번 문제 소개
본 문제의 stadium table은 위와 같으며, 문제를 요약하자면 id가 3번이상 연속하고, 방문자(people)가 100명 이상 넘는 날에 대해 쿼리를 작성해야한다.
본 문제의 primary key는 visit_date며, 중복은 없다.
stadium table의 예시 input은 아래와 같다.
expected output은 아래와 같다.
LEAD, LAG 함수를 이용하는 방법
LEAD, LAG 함수는 간단히 아래와 같이 설명할 수 있다.
LEAD : 특정 컬럼에 있는 값을 당겨서 가져올 수 있음
LAG : 특정 컬럼에 있는 값을 미뤄서 가져올 수 있음
위 테이블에 아래 쿼리를 돌리면 아래와 같이 아웃풋이 나온다.
SELECT id
, LEAD(id,1) OVER () n_id1
, LEAD(id,2) OVER () n_id2
, LAG(id,1) OVER () p_id1
, LAG(id,2) OVER () p_id2
, visit_date
, people
FROM stadium
LEAD를 쓰게되면 검은 선과 같이 id의 2가 n_id1의 첫 행, id의 3이 n_id2의 첫 행으로 당겨진다.
LEAD(당기고 싶은 컬럼, 당기고 싶은 row 수) OVER (PARTITION BY ORDER BY )
- PARTITION BY, ORDER BY는 필수는 아니다.
반면, LAG를 쓰면 푸른 선과 같이 id의 4가 p_id1에서는 5번째 행으로 1행 밀려났고, p_id2에서는 6번째 행으로 2행 밀려난걸 알 수 있다.
LAG(밀고 싶은 컬럼, 밀고 싶은 row 수) OVER (PARTITION BY ORDER BY )
- PARTITION BY, ORDER BY는 필수는 아니다.
이런 함수의 특성을 이용해서 601번을 풀면 아래와 같다.
WITH A AS (
SELECT id
, LEAD(id,1) OVER () n_id1
, LEAD(id,2) OVER () n_id2
, LAG(id,1) OVER () p_id1
, LAG(id,2) OVER () p_id2
, visit_date
, people
FROM stadium
WHERE people >= 100)
SELECT id
, visit_date
, people
FROM (
SELECT CASE WHEN id + 1 = n_id1 AND id + 2 = n_id2 THEN 'Y'
WHEN id - 1 = p_id1 AND id - 2 = p_id2 THEN 'Y'
WHEN id + 1 = n_id1 AND id - 1 = p_id1 THEN 'Y'
ELSE 'N' END csc
, id
, visit_date
, people
FROM a) b
WHERE csc = 'Y'연속하는 수의 특성 활용하는 방법
연속하는 수 정의하려면 크게 2단계를 거쳐야한다.
① LEAD, LAG를 통해 연속하는 컬럼 만들기
② CASE WHEN을 사용해서 연속하는 수 정의하기
연속하는 수
- n, n+1, n+2
- n-2, n-1, n
- n-1, n, n+1
그러나 LEAD, LAG말고 연속하는 수의 수학적 특성을 이용해서 더 간단하게 풀 수 있다.
실제로 아래 쿼리는 LEAD, LAG를 쓰는 것 보다 leetcode에서 더 빠른 쿼리로 나왔다(속도에 대한 부분은 와이파이 속도 등 영향받는 게 많아서 단정할 순 없다. 참고만 하기).
WITH a AS (SELECT id
, people
, visit_date
, ROW_NUMBER() OVER (ORDER BY visit_date) rn
, id - ROW_NUMBER() OVER (ORDER BY visit_date) diff
FROM stadium
WHERE people >= 100)
SELECT id
, visit_date
, people
FROM a
WHERE diff IN (
SELECT diff
FROM a
GROUP BY diff
HAVING COUNT(diff) >= 3 ) 여기서 핵심은 연속하는 수에 연속하는 수를 빼면 같은 수가 나온다는 점이다.
위 쿼리 중 WITH절 위주로 보면 rn이라는 새로운 컬럼을 ROW_NUMBER를 사용해서 추가하고, id에서 rn을 빼면 diff라는 차가 나온다.
연속하는 수 - 연속하는 수는 같은 차가 계속 발생하는 특성을 이용해서 푸는 것이다.
그럼 아래처럼 diff가 1과 2로 나눠져서 나타나게 되고, 각 값을 GROUP BY, COUNT를 사용하게 되면 연속하는 수가 3개 이상인 값을 구할 수 있다.
[참고자료]
https://www.youtube.com/watch?v=tDfAo7uw-3w
https://medium.com/geekculture/human-traffic-of-stadium-leetcode-beccaa98c83b
