240909_TIL

아무리 사소하더라도 배움이 없는 날은 없다.

SQL 문제풀이 복습

문제 링크

SELECT e1.name
FROM   employee e1
       JOIN employee e2
         ON e1.id = e2.managerid
GROUP  BY e1.id
HAVING Count(*) >= 5;

문제 링크
recursive CTE를 안 쓰고 풀려고 시도했는데 결국 잘 안돼서
GPT의 도움을 받아서 해결했다.

먼저 내가 시도했던 쿼리는 아래와 같다.
케이스 테스트는 거의 다 통과했는데, 마지막 하나의 케이스에서 막혔다.

WITH temp
AS
  (
           SELECT   num,
                    frequency
           FROM     numbers
           ORDER BY num ),
  cte
AS
  (
           SELECT   group_concat(REPEAT(concat(num,','), frequency) ORDER BY num SEPARATOR '') AS array
           FROM     temp ),
  length
AS
  (
         SELECT length(array) - length(REPLACE(array, ',', '')) AS array_length
         FROM   cte )
  SELECT
         CASE
                WHEN array_length % 2 = 1 THEN cast(substring_index(substring_index(array, ',', ceil(array_length / 2)), ',', -1) AS signed)
                WHEN array_length % 2 = 0 THEN round( (cast(substring_index(substring_index(array, ',', array_length / 2), ',', -1) AS signed) + cast(substring_index(substring_index(array, ',', (array_length / 2) + 1), ',', -1) AS signed)) / 2, 1 )
         end AS median
  FROM   cte,
         length;

위의 쿼리가 해결하지 못한 마지막 테스트 케이스는
group_concat을 실행한 결과가 기본 제한인 1024 바이트를 넘어서는 경우였다.
이 문제를 해결하려면 세션 내에서

SET SESSION group_concat_max_len = 1000000;

이 쿼리를 실행해서 group_concat의 최대 허용 길이를 늘리면 되는데,
문제는 leetcode의 실행환경상 두 개의 쿼리를 잇달아 실행시키는 게 불가능하다는 점.
따라서 위의 쿼리는 논리적으로는 정답에 가깝지만
문제풀이에 활용하지는 못하게 됐다.

아래는 recursive CTE 없이 정답을 도출하는 과정이다.

1. 먼저 frequency의 누적합과 총합을 포함한 첫 번째 CTE를 만든다.

WITH a
AS
  (
           SELECT   num,
                    frequency,
                    sum(frequency) over (ORDER BY num) AS cumulative_frequency,
                    sum(frequency) over ()             AS total_frequency
           FROM     numbers)

2. 이어서 CTE a로부터, 중앙값(median)의 위치가 어디일지를 결정한다. 예를 들어 total_frequency가 12와 같은 짝수라면 중앙값은 6번째 값과 7번째 값의 평균으로 결정되고, 5와 같은 홀수라면 중앙값은 3번째 값이 된다.

WITH a
AS
  (
           SELECT   num,
                    frequency,
                    sum(frequency) over (ORDER BY num) AS cumulative_frequency,
                    sum(frequency) over ()             AS total_frequency
           FROM     numbers),
  b
AS
  (
         SELECT total_frequency,
                CASE
                       WHEN total_frequency%2 = 1 THEN (total_frequency+1)/2
                       ELSE total_frequency                               /2
                end AS "median_position",
                CASE
                       WHEN total_frequency%2 = 1 THEN (total_frequency+1)/2
                       ELSE (total_frequency/2)+1
                end AS "median_position2"
         FROM   a
         LIMIT  1)

3. 마지막으로 CTE a와 b로부터 본 쿼리를 구해주면 정답인데,
   where절 조건에 cumulative_frequency가 median_position보다 크거나 같다는 조건과, cumulative_frequency에서 frequency를 뺀 조건이 median_position2보다 작다는 조건이 반드시 들어가야 한다.
   
   첫 번째 중앙값 포인트median_position에 도달해야 하고, (where의 첫 번째 조건) 동시에 frequency를 뺀 값이 두 번째 중앙값 포인트median_position2보다는 작아야 중앙값을 구할 조건이 모두 성립되기 때문. 직관적으로 이해하기 어려운 조건이긴 한데, 찬찬히 생각해보면 이해가 아주 안 되는 것은 아니다.

아래는 완성된 정답 쿼리.
recursive CTE는 안 썼지만 이것도 복잡한 풀이인 건 마찬가지다.

WITH a
AS
  (
           SELECT   num,
                    frequency,
                    sum(frequency) over (ORDER BY num) AS "cumulative_frequency",
                    sum(frequency) over ()             AS "total_frequency"
           FROM     numbers),
  b
AS
  (
         SELECT total_frequency,
                CASE
                       WHEN total_frequency%2 = 1 THEN (total_frequency+1)/2
                       ELSE total_frequency                               /2
                end AS "median_position",
                CASE
                       WHEN total_frequency%2 = 1 THEN (total_frequency+1)/2
                       ELSE (total_frequency/2)+1
                end AS "median_position2"
         FROM   a
         LIMIT  1)
  SELECT round(avg(num),1) AS "median"
  FROM   a,
         b
  WHERE  cumulative_frequency >= median_position
  AND    cumulative_frequency - frequency < median_position2;

문제 링크
CTE를 쓸 것도 없이 그냥 바로 구할 수 있는 문제.

SELECT c.name
FROM   candidate c
       JOIN vote v
         ON c.id = v.candidateid
GROUP  BY 1
ORDER  BY Count(*) DESC
LIMIT  1; 

오늘은 두 번째 문제를 해결하느라 시간을 너무 많이 썼다.
얼른 다음 할 일로 넘어가야지.