문제

advent S24 세 명이 서로 친구인 관계 찾기
세 명이 오리라
(자세한 문제는 생략)

풀이 과정

문제/데이터 이해

edges 테이블에서 동일한 row에 있는 A와 B는 친구이다

해당 테이블은 이미 A < B로 정리가 되어 있다 (따라서, 문제에서 요구하는 "중복된 세 친구 관계를 제외하기 위해 user_a_id < user_b_id < user_c_id를 만족하는 경우만 출력되어야 합니다."는 별도로 고려할 필요가 없다)

따라서 해당 문제는 아래 2가지 조건을 만족하면 해결된다
(1) A-B, A-C, B-C의 상호 친구 관계를 모두 만족
(2) 셋 중에 적어도 한 명은 3820

셀프 조인 : a와 b는 친구다

보자마자 떠오른 방법은 셀프 조인이다
어차피 주어진 테이블도 1개 뿐이고, 이걸 반복하여 JOIN함으로써 셋의 친구 관계를 찾을 수 있다

문제에서 요구하는 바는 user_id가 a<b<c 순서로 나열되는 것이다
그렇기에 먼저 a<b가 친구인 관계를 구하는 것으로 시작한다

SELECT
  a.user_a_id
  , a.user_b_id
  , b.user_b_id as "user_c_id"
FROM
  edges A
  INNER JOIN edges b
    ON a.user_a_id = b.user_a_id
;

이렇게 도출된 테이블은 "a와 b가 친구이면서, a와 c가 친구인 경우"이다.
다만 아직 'b와 c가 친구'인지 검증되지 않았다 (b와 c가 동일인인 경우도 출력되고 있고)

JOIN 조건 설정 : b와 c는 친구다

앞서 도출한 테이블을, 다시 edges 테이블과 조인한다.
단, 이때 조인 조건을 통해 new_b를 old_a에, new_c를 old_b라고 설정해줄 수 있다.
이를 통해 new_b와 new_c가 '서로 친구 관계'라는 것을 적용할 수 있다.

WITH bbb AS (
  SELECT
    a.user_a_id
    , a.user_b_id
    , b.user_b_id as "user_c_id"
  FROM
    edges A
    INNER JOIN edges b
      ON a.user_a_id = b.user_a_id
)
SELECT
  a.user_a_id
  , a.user_b_id
  , a.user_c_id
FROM
  bbb a
  INNER JOIN edges b
    ON (a.user_b_id = b.user_a_id)
      AND (a.user_c_id = b.user_b_id)
;

적어도 한 명은 3820

마지막 조건은 쉽다
그냥 or 조건으로 3820 여부를 묶어주면 된다

최종적으로 코드는 아래와 같다.

WITH a_is_butterfly AS (
  -- A와 B가 친구이면서, A와 C가 친구인 케이스
  -- 셀프조인을 통해 구현. 아직 B와 C가 친구인 지는 검증되지 않음
  SELECT
    a.user_a_id
    , a.user_b_id
    , b.user_b_id as "user_c_id"
  FROM
    edges A
    INNER JOIN edges b
      ON a.user_a_id = b.user_a_id
)
SELECT
  a.user_a_id
  , a.user_b_id
  , a.user_c_id
FROM
  a_is_butterfly a
  INNER JOIN edges b
    -- "A와 B가 친구이면서 A와 C가 친구인 케이스"에 'B와 C가 친구'라는 상황을 주기 위한 조건
    -- B와 C를 'edges에서 A-B의 친구 관계에 일치하는 값'만 출력하도록 조건 설정
    ON (a.user_b_id = b.user_a_id)
      AND (a.user_c_id = b.user_b_id)
WHERE
  -- A, B, C 중 적어도 하나는 3820
  (a.user_a_id = 3820)
  OR (a.user_b_id = 3820)
  OR (a.user_c_id = 3820)
;