이동준1
아웃풋 공부
이동준1
전체 방문자
오늘
어제
  • 분류 전체보기 (87)
    • airflow (8)
    • sql (23)
    • aws (12)
    • python (3)
    • 네트워크 (12)
    • 알고리즘 (2)
    • 짧은서평 (27)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 네트워크
  • 마음의기술
  • 고통의 비밀
  • AWS
  • regexp
  • 퓨처셀프
  • 마음의기술 서평
  • 통증해방
  • 고통의비밀
  • 통증해방 서평
  • 서평
  • Network
  • 유연함의힘

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
이동준1
sql

[SQL][HackerRank] Binary Tree Nodes

[SQL][HackerRank] Binary Tree Nodes
sql

[SQL][HackerRank] Binary Tree Nodes

2023. 1. 2. 17:53

 

https://www.hackerrank.com/challenges/binary-search-tree-1/problem?isFullScreen=true 

 

Binary Tree Nodes | HackerRank

Write a query to find the node type of BST ordered by the value of the node.

www.hackerrank.com

 

You are given a table, BST, containing two columns: N and P, where N represents the value of a node in Binary Tree, and P is the parent of N.

문제에서는 N칼럼과 P칼럼으로 이루어진 BST라는 테이블이 주어진다. N은 각 노드의 값을 나타내고, P는 노드의 부모를 표현한다. 루트 노드의 부모는 없으므로, null로 표현되어있다.

 

이 BST 을 이용해 각 노드가 Root 노드인지, Leaf 노드인지, 아니면 Inner 노드인지 파악하는것이 문제의 목적이다. 원하는 출력형태는 아래와 같다.

 

이 문제는 CASE WHEN을 적절히 이용하면 해결 가능하고 특별히 Inner 노드를 판단할때 서브쿼리를 잘 작성해줘야한다. 루트 노드는 P에 null값이 있기때문에 쉽게 판단이 가능하다. 그리고 Inner 노드는 해당 노드가 누군가의 부모일 경우 해당된다. 이는 노드(N)가 부모(P)필드에 있는지 확인하는 방식으로 판단한다. 루트 노드도 누군가의 부모가 되는 경우이지만, CASE WHEN은 조건을 위에서부터 차례대로 고려하기 때문에 조건 작성에 문제가 되지 않는다.

 

아래와 같은 방식으로 서브쿼리를 작성해주면 서브쿼리로 값의 집합을 만들게 되는 것이며, 그 집합안에 N이 있는지 판단하게 된다.

CASE
  WHEN P IS NULL THEN 'Root'
  WHEN N IN (SELECT P FROM BST) THEN 'Inner'

 

그리고 마지막으로 위의 두경우에 모두 속하지 않으면 Leaf 노드로 분류해주면 된다. 그리고 노드의 순서대로 정렬해주면 문제를 해결할 수 있다.

SELECT N,
    CASE
        WHEN P IS NULL THEN 'Root'
        WHEN N IN (SELECT P FROM BST) THEN 'Inner'
        ELSE 'Leaf' END
FROM BST
ORDER BY 1;

'sql' 카테고리의 다른 글

[SQL] Aggregation Without Grouping  (0) 2023.01.04
[SQL][HackerRank] The Blunder  (0) 2023.01.03
[SQL][HackerRank] Occupations  (0) 2022.12.27
[SQL] ROW_NUMBER / RANK / DENSE_RANK  (0) 2022.12.27
[SQL] NESTED CASE  (0) 2022.12.26
    'sql' 카테고리의 다른 글
    • [SQL] Aggregation Without Grouping
    • [SQL][HackerRank] The Blunder
    • [SQL][HackerRank] Occupations
    • [SQL] ROW_NUMBER / RANK / DENSE_RANK
    이동준1
    이동준1

    티스토리툴바

    개인정보

    • 티스토리 홈
    • 포럼
    • 로그인

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.