[리트코드] 176 - Second Highest Salary

176. Second Highest Salary

Medium

---

Table: Employee

+-------------+------+
| Column Name | Type |
+-------------+------+
| id          | int  |
| salary      | int  |
+-------------+------+
id is the primary key (column with unique values) for this table.
Each row of this table contains information about the salary of an employee.

 

Write a solution to find the second highest distinct salary from the Employee table. If there is no second highest salary, return null (return None in Pandas).

The result format is in the following example.

 

Example 1:

Input: 
Employee table:
+----+--------+
| id | salary |
+----+--------+
| 1  | 100    |
| 2  | 200    |
| 3  | 300    |
+----+--------+
Output: 
+---------------------+
| SecondHighestSalary |
+---------------------+
| 200                 |
+---------------------+

Example 2:

Input: 
Employee table:
+----+--------+
| id | salary |
+----+--------+
| 1  | 100    |
+----+--------+
Output: 
+---------------------+
| SecondHighestSalary |
+---------------------+
| null                |
+---------------------+

분류

데이터베이스

---

문제 풀이

문제 분석

이 문제는 Employee 테이블에서 두 번째로 높은 고유 급여(second highest distinct salary)를 찾는 것입니다.

• 입력: id (기본 키, 정수)와 salary (정수) 컬럼을 가진 Employee 테이블
• 출력: SecondHighestSalary라는 단일 컬럼을 가진 결과 테이블. 두 번째로 높은 급여가 존재하지 않으면 null 반환
• 핵심 조건:
  • 고유(Distinct) 급여 기준이므로 중복 급여는 하나로 취급
  • 데이터가 1개만 있거나 모든 급여가 동일하면 결과는 null

---

접근 방법

이 문제를 해결하기 위해 **윈도우 함수(Window Function) 중 DENSE_RANK()**를 사용했습니다.

• 선택 이유:
  • DENSE_RANK()는 동일한 값에 같은 순위를 부여하고, 다음 순위를 건너뛰지 않습니다. (예: 300, 200, 200, 100 → 순위 1, 2, 2, 3)
  • RANK()를 사용하면 동점자 이후 순위가 건너뛰어져(1, 2, 2, 4) 두 번째 고유 급여를 순위 2로 정확히 매핑하기 어렵습니다.
  • ROW_NUMBER()는 동점자에게도 다른 번호를 부여하므로 부적절합니다.
• 대안: 서브쿼리에서 MAX(salary)를 이용해 최고 급여를 제외한 최대값을 구하는 방식(WHERE salary < (SELECT MAX...))도 가능하지만, 윈도우 함수를 사용하면 정렬과 순위 계산을 한 번에 처리하여 가독성이 좋고 확장성(예: 3번째 높은 급여)에도 유리합니다.

---

구현 설명

1단계: 내부 서브쿼리에서 급여별 순위 계산

SELECT
    salary,
    DENSE_RANK() OVER (ORDER BY salary DESC) AS salary_rank
FROM Employee

• Employee 테이블의 모든 행을 대상으로 salary 컬럼을 내림차순(DESC) 정렬합니다.
• DENSE_RANK() 함수를 적용하여 가장 높은 급여는 1위, 그다음으로 높은 고유 급여는 2위, 그다음은 3위... 와 같이 순위(salary_rank)를 부여합니다.
• 중복된 급여가 있어도 같은 순위를 가지며, 순위가 건너뛰지 않습니다.

2단계: 외부 쿼리에서 2순위 필터링 및 최대값 조회

SELECT MAX(salary) AS SecondHighestSalary
FROM ( ... ) ranked
WHERE salary_rank = 2;

• 1단계에서 생성된 가상 테이블(ranked)에서 salary_rank = 2인 행들만 필터링합니다.
• DENSE_RANK 특성상 2순위에 해당하는 급여는 두 번째로 높은 고유 급여 하나만 남게 됩니다(중복 시 여러 행이지만 값은 동일).
• MAX(salary)를 사용하여 해당 급여 값을 단일 값으로 추출합니다.
• 중요: 만약 2순위 데이터가 없다면(데이터가 1개뿐이거나 모두 같은 급여), WHERE 절 결과가 빈 집합이 되고, 집계 함수 MAX는 NULL을 반환하여 문제 요구사항을 자연스럽게 충족합니다.

---

⏱복잡도 분석

• 시간 복잡도: O(N log N)
  • DENSE_RANK() 계산을 위해 salary 컬럼을 정렬하는 과정이 필요합니다. 일반적인 데이터베이스 정렬 알고리즘의 복잡도는 O(N log N)입니다. (N: Employee 테이블의 행 개수)
• 공간 복잡도: O(N)
  • 정렬 및 윈도우 함수 계산을 위해 임시로 N개의 행에 대한 순위 정보를 저장할 공간이 필요합니다.

---

핵심 포인트

1. DENSE_RANK() 함수의 특성 이해: 동점자에게 같은 순위를 주고 다음 순위를 건너뛰지 않으므로, '두 번째로 높은 고유 값'을 찾을 때 순위 2번이 정확히 그에 해당합니다.
2. MAX() 집계 함수의 NULL 반환 특성: 조건에 맞는 행이 없을 때(2순위 없을 때) MAX()는 에러 대신 NULL을 반환하므로, 별도의 IFNULL이나 CASE WHEN 처리 없이 문제의 "null 반환" 조건을 자동으로 만족시킵니다.
3. 내림차순 정렬 (ORDER BY salary DESC): 순위 함수는 정렬 기준에 따라 동작하므로, 가장 높은 값이 1위가 되도록 내림차순 정렬하는 것이 필수입니다.

풀이 코드

# Write your MySQL query statement below
SELECT MAX(salary) AS SecondHighestSalary
FROM (
    SELECT
        salary,
        DENSE_RANK() OVER (ORDER BY salary DESC) AS salary_rank
    FROM Employee
) ranked
WHERE salary_rank = 2;