꿀잠

https://leetcode.com/problems/single-number/description/

비트 조작 문제이다. 비트 연산자는 잘 사용하지 않았지만, 기본적인 원리 정도는 이해하고 있었다.

해당 카테고리를 보고 비트 연산자를 복습한 이후 문제 풀이를 진행했다.

java에서는 &, |, ^, ~ 를 비트 논리 연산자로 사용할 수 있다. 비트를 이동 시키는 연산자도 있지만 해당 문제를 해결하기 위해선 비트 논리 연산자를 이해하면 된다.

& 의 경우 비트의 값이 모두 1일 경우 1을 반환한다.(AND)
| 의 경우 비트의 값 중 하나가 1일 경우 1을 반환한다.(OR)
^의 경우 비트의 값이 다를 경우(0, 1), (1, 0) 일 경우 1을 반환한다.(XOR)
~의 경우 비트의 값을 반대로 변환한다.(NOT)

해당 문제를 해결하기 위해선 XOR 연산자가 적절하였다. 개인적으로는 4가지 논리에서 가장 생소한 부분으로 느껴지기도 했지만 문제를 읽고서 해당 논리 연산자가 필요한 것을 알 수 있었다.

문제는 한 번 등장한 값을 반환하는 것이 목표이다.
기본 시작 값을 0으로 하여, 값들에 XOR 연산자를 더 할 경우 첫 번째 등장 시에는 비트에 값이 1로 새겨지며 더해지겠지만, 두번째 값이 등장 시 비트를 0으로 바꾸어 값을 지우게 된다. 최종적으로 한 번 등장한 값만 비트에 값을 새기며 정답의 2진수에 맞게 된다. 서로 다른 값이 같은 비트를 수정한다 하더라도 짝수 번 반복하여 값을 지우기 때문에 다른 값이 같은 비트를 수정하는 경우도 문제가 되지 않는다. 아래는 비트 논리 연산자를 사용하여 해당 문제를 해결한 코드이다.

public class Solution {  
    public int singleNumber(int[] nums) {  
        int answer = 0;  
  
        for(int num : nums){  
            answer = answer^num;  
        }  
  
        return answer;  
    }  
}

https://leetcode.com/problems/merge-intervals/submissions/2096919730/

간격들이 주어졌을 때 서로 겹칠 수 있는 간격이면 합쳐서 최대한 압축한 형태의 간격 집합을 정답으로 내는 문제이다.

두 간격이 있을 때 겹친다고 하는 것은 앞 간격의 끝 값이 뒷 간격의 첫 값을 넘어서면 된다고 정의할 수 있다.

이 때 비교하는 두 간격을 정하기 위해서 간격의 앞 부분을 기준으로 순서대로 나열하면 차례대로 비교할 수 있다고 생각하고 PriorityQueue를 사용하였다. PriorityQueue에 간격 값들을 넣은 후 하나 씩 꺼내서 이어질때까지 잇는 작업을 while 문을 통해 진행한 이후 정답 List에 넣어 주었다. 최종적으로 배열화하여 return 하였다.

import java.util.*;  
  
public class Solution {  
    public int[][] merge(int[][] intervals) {  
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0] );  
        for(int[] interval:intervals){  
            pq.add(interval);  
        }  
  
        List<int[]> newArray = new ArrayList<>();  
  
        while(!pq.isEmpty()){  
            int[] cur = pq.poll();  
            while(!pq.isEmpty() && pq.peek()[0] <= cur[1]){  
                int[] next = pq.poll();  
                cur[1] = Math.max(next[1], cur[1]);  
            }  
            newArray.add(cur);  
        }  
  
        int finalSize = newArray.size();  
        int[][] answer = new int[finalSize][2];  
  
        for(int i = 0; i < finalSize; i++){  
            answer[i][0] = newArray.get(i)[0];  
            answer[i][1] = newArray.get(i)[1];  
        }  
  
        return answer;  
    }  
}

https://leetcode.com/problems/jump-game/

0번 인덱스부터 최종 인덱스까지 각 인덱스에서의 nums[i] 수치만큼 이동할 수 있을때 끝까지 도달할 수 있는지에 대한 문제이다.

최종 목표지에 도달하기 위해선 특정 인덱스에서의 점프력(값이) 마지막 인덱스보다 높아야 한다.

그리고 해당 인덱스 까지 도달하기 위해서는 그 이전에서 점프력이 넘어야한다.

이를 반복해서 최초 시작 지점에서 목표 지점까지 뛸 수 있다면 가능하다고 할 수 있다.

배열을 역으로 내려오면 확인하며 풀었다.

public class Solution {  
    public boolean canJump(int[] nums) {  
        int goal = nums.length - 1;  
  
        for(int i = nums.length - 1; i >= 0; i--){  
            int num = nums[i];  
            if(i + num >= goal){  
                goal = i;  
            }  
        }  
  
        return goal == 0;  
    }  
}

https://leetcode.com/problems/climbing-stairs/description/

계단을 1, 2 단씩 오를수 있을때 n계의 계단을 오르는 방법의 개수를 묻는 DP 문제이다.
n번재 계단을 오르기 위해선 n-1 번째에서 한 걸음, n-2 에서 두 걸음 오르는 방법이 있으므로

해당 방식으로 dp 점화식을 만들어 문제를 해결하였다.

public class Solution {  
    public int climbStairs(int n) {  
        int[] dp = new int[46];  
        dp[0] = 0;  
        dp[1] = 1;  
        dp[2] = 2;  
  
        for(int i = 3; i <= n; i++){  
            dp[i] = dp[i - 2] + dp[i - 1];  
        }  
  
        return dp[n];  
    }  
}

https://leetcode.com/problems/network-delay-time/description/

주어진 노드로 부터 최단 경로를 묻는 다익스트라 알고리즘을 사용하는 문제였다.
예전에 공부했었는데 잘 기억이 나지 않아 복습하며 풀었다. 처음에 오래된 기억으로 더듬 거리며 풀다보니 시간 초과가 나왔다. 복습하며 잘못된 부분들을 해결 하며 풀었다.

다익스트라는 주어진 시작점으로 부터 최단 경로를 기준으로 경로를 이어 나가는 그리디 + DP 형식의 그래프 문제이다. 최단경로를 이어나가기 위해 PriorityQueue 사용했으며, 각 경로의 최소 길이를 배열에 저장하여 DP 배열로 활용하였다.

import java.util.*;  
  
public class Solution {  
    public int networkDelayTime(int[][] times, int n, int k) {  
  
        // node 정보를 담을 List 초기화  
        List<Node>[] nodes = new List[n + 1];  
        for(int i = 0; i < nodes.length; i++){  
            nodes[i] = new ArrayList<>();  
        }  
  
        for(int[] time: times){  
            int from = time[0];  
            int to = time[1];  
            int travel = time[2];  
            // node 정보 List에 담기  
            nodes[from].add(new Node(to, travel));  
        }  
  
        // 다익스트라 알고리즘을 사용하기 위한 pq        
        // 최단경로를 저장하기 위한 travels        
        PriorityQueue<Node> pq = new PriorityQueue<>();  
        int[] travels = new int[n + 1];  
  
        // 최단경로 무한대로 초기화  
        for(int i = 1; i < travels.length; i++){  
            travels[i] = Integer.MAX_VALUE;  
        }  
  
        // 시작지점 처리  
        travels[k] = 0;  
        pq.add(new Node(k, 0));  
  
        while(!pq.isEmpty()){  
            Node cur = pq.poll();  
  
            // 현재 지점까지 최단 경로인지 확인, visited 체크 역할  
            if (cur.travel > travels[cur.node]){  
                continue;  
            }  
  
            // 다음 경로 확인  
            for (Node next : nodes[cur.node]) {  
                int newTravel = cur.travel + next.travel;  
                // 다음 경로중 최단경로인 경우 pq 경로 추가  
                if (newTravel < travels[next.node]) {  
                    travels[next.node] = newTravel;  
                    pq.add(new Node(next.node, newTravel));  
                }  
            }  
        }  
  
        int answer = 0;  
        for(int i = 1; i < travels.length; i++){  
            // 가장 오래 걸린 경우 Network Delay를 마친 시간  
            answer = Math.max(travels[i], answer);  
        }  
  
        // 도달하지 못한경우 초기 거리값을 가지고 있으므로 -1, 아니면 answerreturn answer == Integer.MAX_VALUE ? -1 : answer;  
    }  
  
    private static class Node implements Comparable<Node>{  
        int node;  
        int travel;  
  
        Node(int node, int travel){  
            this.node = node;  
            this.travel = travel;  
        }  
  
        @Override  
        public int compareTo(Node o){  
            return Integer.compare(this.travel, o.travel);  
        }  
    }  
}

https://leetcode.com/problems/number-of-islands/description/

주어진 그리드에서 땅으로 연결된 섬이 몇 개인지 체크하는 문제이다.
bfs를 이용하여 땅인 부분 확인하고 섬의 개수를 확인하였으며, 이때 땅을 확인할 때 bfs를 이용하여 연결된 모든 땅을 CHECK_LAND로 변경하여 연결된 땅을 샐 수 있도록 하였다.

import java.util.*;  
  
public class Solution {  
  
    private static final char LAND = '1';  
    private static final char WATER = '0';  
    private static final char CHECK_LAND = '3';  
  
    public int numIslands(char[][] grid) {  
        int cnt = 0;  
  
        for (int i = 0; i < grid.length; i++) {  
            for (int j = 0; j < grid[0].length; j++) {  
                if (bfs(i, j, grid)) {  
                    cnt++;  
                }  
                ;  
            }  
        }  
  
        return cnt;  
    }  
  
    private boolean bfs(int row, int col, char[][] grid) {  
        // 현재 좌표가 땅인지 확인  
        if (grid[row][col] != LAND) {  
            return false;  
        }  
  
        // 땅일 경우 최종적으로 true return, return 이전에 연결된 땅을  
        // bfs로 CHECK_LAND로 바꾸어 둔다. 연결된 땅은 땅으로 확인되지 않으므로  
        // 연결된 땅 전체를 하나로 확인 가능하다.  
        grid[row][col] = CHECK_LAND;  
  
        // 아래, 좌, 위, 우 각 방향 별로 확인하기 위한 방향 배열  
        int[] dr = {-1, 0, 1, 0};  
        int[] dc = {0, -1, 0, 1};  
  
        // que 에 넣기 위해 Pos class를 만들어서 이용, int[] 을 사용해도 무방하다.  
        Queue<Pos> que = new ArrayDeque<>();  
        que.add(new Pos(row, col));  
  
        while (!que.isEmpty()) {  
            Pos cur = que.poll();  
            for (int i = 0; i < 4; i++) {  
                int nextr = cur.r + dr[i];  
                int nextc = cur.c + dc[i];  
  
                // 그리드 범위조건, 땅인 부분의 경우 CHECK로 변환  
                if (nextr >= 0  
                        && nextr < grid.length  
                        && nextc >= 0  
                        && nextc < grid[0].length  
                        && grid[nextr][nextc] == LAND  
                ) {  
                    grid[nextr][nextc] = CHECK_LAND;  
                    que.add(new Pos(nextr, nextc));  
                }  
            }  
        }  
  
        return true;  
    }  
  
    private class Pos {  
        int r;  
        int c;  
  
        Pos(int r, int c) {  
            this.r = r;  
            this.c = c;  
        }  
    }  
}

연결된 땅을 하나씩 샐 수 있도록 bfs 를 이용하여 푼 문제였다, 각 방향으로 bfs 그래프를 탐색하며, 그리드의 범위, 땅인지 아닌지를 체크할 때 조건을 잘 확인해야한다.

https://leetcode.com/problems/kth-largest-element-in-an-array/description/

sort를 쓰지 않고 배열의 K번째로 큰 요소를 찾는 문제이다.
알고리즘을 복습하려고 따라가고 있는 리트코드 로드맵상에선 Heap & Priority Queue로 지정되어있어 Priority Queue를 이용해서 풀었다.

사실 PriorityQueue도 sort를 이용하는게 아닌가 하는 의구심이 들기는 한다.
하지만 Arrays.sort()를 이용하여 문제를 풀 경우 오류를 내뱉었다.

문제에서 PriorityQueue를 사용시 오류가 발생하지 않으며 이는 PriorityQueue를 허용한다는 의미이며

그것이 문제의 의도라고 확인하였다.
문제 풀이에 성공한 코드는 아래와 같다.

import java.util.*;  
  
public class Solution {  
    public int findKthLargest(int[] nums, int k) {  
        PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);  
        // PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());  
        for (int num : nums) {  
            pq.add(num);  
        }  
  
        while (k-- > 1) {  
            pq.poll();  
        }  
  
        return pq.poll();  
    }  
}

PriorityQueue 는 기본적으로 Integer 의 compareTo 메서드에 따라 오름차순으로 정렬하기 때문에 생성시 새로운 compareTo 메서드를 오버라이드 해야한다. Collections.reverseOrder()를 이용해 간단히 역순 정렬을 할 수도 있으며, 직접 수식을 compareTo 메서드에 오버라이드 해주는 것도 방법이다. 이 때 화살표 함수로 손쉽게 메서드를 표기할 수 있다.

PriorityQueue에 nums 배열을 넣은 후에는 간단하다. k번째로 큰수이기 때문에 k번째의 수를 뽑아내주면 된다. k-1 번째까지 뽑은 후 리턴시 k번째 수를 poll하여 반환하였다.