물고기 종류 별 대어 찾기 [프로그래머스]

물고기 종류 별로 가장 큰 물고기의 ID(ID), 물고기 이름(FISH_NAME), 길이(LENGTH)를 출력하는 SQL 문을 작성해주세요.

테이블

FISH_INFO 테이블: ID, FISH_TYPE, LENGTH, TIME
FISH_NAME_INFO 테이블: FISH_TYPE, FISH_NAME

해결 방안

물고기 종류 별로 가장 길이가 긴 것을 찾는 거니 GROUP BY, HAVING으로 해결할 수 있을거라 생각했지만, GROUP BY를 사용하면 다음 두 가지 사항만 SELECT 문에 포함할 수 있다.

1. GROUP BY 절에 명시된 기준 컬럼
2. 집계함수가 사용된 컬럼

HAVING 절도 다음과 같은 제약사항을 갖는다.

1. GROUP BY 절에 명시된 컬럼만 명시 가능
2. 무조건 이 컬럼에 대해 집계 함수를 사용해야 함

그래서 이중 SQL 문으로 짜야겠구나 싶었다.

물고기 종류별로 가장 긴 길이를 찾는 경우기 때문에 각 fish_type 별 가장 긴 길이를 뽑은 임시 집합(fish_type, length)을 만들고, 이와 일치하는 행의 정보를 뽑았다.

답

select id, fni.fish_name, length from fish_info join fish_name_info fni on fish_info.fish_type = fni.fish_type
where (fni.fish_type, length) in (
    select fish_type, max(length)
    from fish_info
    group by fish_type
)
order by id asc;

Second Highest Salary [LeetCode #176]

두번째로 높은 유니크 salary 값을 출력한다. 값이 존재하지 않으면 null을 출력한다

테이블

Employee: id, salary

해결 방안

실제로 두번째로 높은 고유 salary값이 존재하지 않으면 아무 값도 출력되지 않는다.

그러므로 나는 case 문으로 고유한 salary 값이 두개 이상일 경우와 두 개 미만일 경우를 구분해서 해결했다.

select 
case
    when count(distinct salary) >= 2 then (
        select distinct salary 
        from Employee
        order by salary desc
        limit 1, 1
    )
    else null 
end as SecondHighestSalary
from Employee;

Populating Next Right Pointers in Each Node [LeetCode#117]

각 노드가 left 자식과 right 자식을 갖는 트리 구조에서 같은 레벨의 노드들을 next로 연결시킨다.

내 풀이

BFS를 사용했다.

Map<Node, Integer>로 각 노드의 레벨을 저장하고, Map<Integer, List<Node>>로 각 레벨당 노드 집합을 순서를 갖춰서 관리했다.

if (root == null) return root;
ArrayDeque<Node> queue = new ArrayDeque<>();
Map<Integer, ArrayList<Node>> distance = new HashMap<>();
Map<Node, Integer> map = new HashMap<>();

queue.addLast(root);
map.put(root, 0);

while (!queue.isEmpty()) {
    Node node = queue.pollFirst();
    int dist = map.get(node);
    if (!distance.containsKey(dist + 1)) distance.put(dist + 1, new ArrayList<Node>());
    if (node.left != null) {
        map.put(node.left, dist + 1);
        distance.get(dist + 1).add(node.left);
        queue.add(node.left);
    } 
    if (node.right != null) {
        map.put(node.right, dist + 1);
        distance.get(dist+1).add(node.right);
        queue.add(node.right);
    } 
}

BFS를 모두 마친 후, distance 맵으로 각 레벨의 노드를 연결시키는 작업을 수행했다.

int dist = 1;
while (distance.containsKey(dist)) {
    List<Node> connected = distance.get(dist);
    for (int i = 0; i < connected.size()-1; i++) {
        connected.get(i).next = connected.get(i+1);
    }

    dist++;
}

아쉬웠던 점

짜기 쉬웠지만 좋은 코드는 아니라는 생각이 들었다. 어차피 BFS로 모든 노드를 탐색하는데, 한 번의 탐색으로 각 레벨의 노드 연결까지 끝내는 방법은 없을까?

보완한 풀이

public Node connect(Node root) {

    if (root == null) return root;
    ArrayDeque<Node> queue = new ArrayDeque<>();
    queue.offer(root); // 노드 레벨부터 시작한다.


    while (!queue.isEmpty()) {

        int size = queue.size(); // queue의 크기는 가변적이기 때문에 현재 레벨에 있는 노드의 탐색으로만 제한하기 위해 변수에 저장한다
        Node prev = null; // 각 레벨을 처음 시작하면 현재 노드의 이전 노드는 없다.

        for (int i = 0; i < size; i++) {
            Node node = queue.pollFirst();

            if (prev != null) {
                prev.next = node; // 현재 레벨의 첫 노드를 제외하고는 모두 거칠 과정
            }

            prev = node; // 현재 노드는 다음 노드의 이전 노드가 될 것이다.

			// null이 아닌 모든 자식을 왼쪽부터 큐에 더해서 다음 while 루프에 탐색되도록 한다
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }

    }
    return root;
}

Permutations II [LeetCode#47]

중복 숫자가 가능한 집합에 대하여 모든 숫자를 사용하는 고유 순열을 모두 출력한다

문제

입력값: int[] nums
반환값: List<List<Integer>>

해결방안

고유 순열이 핵심이다.

입력 배열을 정렬한 다음, 탐색 조건에 제약을 추가해서 결과가 만들어진 다음 확인하는 작업을 간소화한다.

주로 탐색 조건은 !visited[i]가 전부이지만, 이번에는 현재 i번째 요소와 이전 요소 (i-1)가 동일한 값인지 확인하고, 동일한 값이라면 이전 요소를 방문했는지 확인한다.

i-1번째 값, i번째 값 모두 1인데, i-1번째 값을 방문하지 않은 상태에서 i번째 값을 방문하면, 어차피 같은 결과가 나온다.

112와 112는 같다.

class Solution {
    static List<List<Integer>> result;
    public List<List<Integer>> permuteUnique(int[] nums) {
        result = new ArrayList<>();
        Arrays.sort(nums);
        genPerm(0, nums.length, new boolean[nums.length], new ArrayList<Integer>(), nums);
        return result;
    }

    private void genPerm(int depth, int N, boolean[] visited, List<Integer> tmp, int[] nums) {
        if (depth == N) {
            result.add(new ArrayList<>(tmp));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            
            if (visited[i] || (i > 0 && nums[i]==nums[i-1] && !visited[i-1])) continue;

            visited[i] = true;
            tmp.add(nums[i]);
            genPerm(depth + 1, N, visited, tmp, nums);
            tmp.remove(tmp.size()-1);
            visited[i] = false;
        }
    } 
}