꿀잠

https://leetcode.com/problems/search-in-rotated-sorted-array/description/

배열에서 타겟의 값을 찾는 문제이다. 특이점으로는 배열이 정렬되어있으나 해당 정렬은 왼쪽으로 회전 되어있을 수 있다는 점이다.

사실 문제 요구 사항으로 O(log n) 시간 복잡도를 요구하나 단순 for문(시간 복자도 O(n))으로 찾아도 문제가 통과된다. 하지만 알고리즘 연습을 위해 푸는 문제이니 정석적인 방법으로 풀었다.
O(log n)의 시간 복잡도를 요구한다는 것은 이진 탐색 알고리즘을 사용하라는 것으로 이해하면 된다.

단 조건이 회전된 배열일 수 있으므로 조건을 더 세분화 하여야 한다.
우선 이진탐색을 위해 left, right, mid 를 선정한 이후 조건을 세분화하여 left, right 의 값을 변화시키며 이진 탐색을 하여 해결하였다. 조건 선정에 자꾸 실패하여 꽤나 고생했다. 아래는 최종적으로 통과한 코드이다.

mid를 중심으로 왼쪽 또는 오른쪽은 신뢰할 수 있게 정렬 되어있다는 점을 이용하여 조건을 나누었다.

public class Solution {  
    public int search(int[] nums, int target) {  
        int left = 0;  
        int right = nums.length - 1;  
        while(left <= right){  
            int mid = (left + right) / 2;  
            int s = nums[left];  
            int e = nums[right];  
            int cur = nums[mid];  
  
            if(target == cur){  
                return mid;  
            }  
  
            if(cur >= s){  
                // 왼쪽이 정렬되어있을 경우  
                if(target > cur){  
                    left = mid + 1;  
                }else if(target >= s){  
                    right = mid - 1;  
                }else{  
                    left = mid + 1;  
                }  
            }else{  
                // 오른쪽이 정렬되어있을 경우  
                if(target < cur){  
                    right = mid - 1;  
                }else if(target <= e){  
                    left = mid + 1;  
                }else{  
                    right = mid - 1;  
                }  
            }  
        }  
  
        return -1;  
    }  
}

https://leetcode.com/problems/min-stack/description/

최소 값이 min 값을 원할 때 얻을 수 있는 Stack을 구현하는 문제이다. 클래스 안에 내부 배열을 선언하여 해결하였다. 문제를 풀고 찾아보니 Stack 클래스를 직접 이용해도 되는 문제였다. Java에서 제공하는 Stack과 PriorityQueue를 이용하는 방식이 더 쉽게 해결할 수 있을 것으로 예상한다.

우선 본인이 해결한 방식은 배열을 이용했으며, 문제 제약 조건에서 제공한 최대 명령 횟수를 이용하여 배열의 크기를 초기화 해주었다. 배열 크기가 그보다 작다면 push를 해당 횟수만큼 실행할 경우 배열을 넘어서게 될 것이기 때문이다.

0번 index부터 차례대로 넣어주었으며, 현재의 크기 curSize를 이용하여 스택의 최상단 위치를 체크하도록 하였다. 문제에서 요구하는 스택은 최소 값을 확인할 수 있어야 하며 O(n)의 시간 복잡도가 필요하다.

따라서 최소 값을 저장하는 배열도 하나 생성해주었다. push 또는 pop을 할 때 값을 찾고 인덱스를 순차적으로 밀어주거나, 땡겨 주어서 최소 값을 순서대로 정렬해서 저장하였다. 이 때 값을 찾는 index까지의 검색과 해당 index부터 마지막까지의 검색은 for 문을 한 번 순회하기 때문에 O(n)의 시간복잡도 제한 사항을 해결하였다. 순서대로 저장하였기 때문에 min[0]의 값은 현재 스택에 있는 최소 값을 확인할 수 있도록 하였다.

import java.util.*;  
  
class MinStack {  
  
    int[] arr;  
    int[] min;  
    int curSize;  
  
    public MinStack() {  
        arr = new int[3 * (int)Math.pow(10, 4)];  
        min = new int[3 * (int)Math.pow(10, 4)];  
        Arrays.fill(min, Integer.MAX_VALUE);  
        curSize = 0;  
    }  
  
    public void push(int value) {  
        arr[curSize] = value;  
        int minIdx = curSize;  
        for(int i = 0; i < curSize; i++){  
            if(value < min[i]){  
                minIdx = i;  
                break;  
            }  
        }  
  
        for(int i = curSize; i >= minIdx + 1; i--){  
            min[i] = min[i - 1];  
        }  
  
        min[minIdx] = value;  
  
        curSize++;  
    }  
  
    public void pop() {  
        curSize--;  
  
        int value = arr[curSize];  
        int minIdx = curSize;  
        for(int i = 0; i <= curSize; i++){  
            if(value == min[i]){  
                minIdx = i;  
                break;  
            }  
        }  
  
        for(int i = minIdx; i < curSize; i++){  
            min[i] = min[i + 1];  
        }  
  
    }  
  
    public int top() {  
        return arr[curSize - 1];  
    }  
  
    public int getMin() {  
        return min[0];  
    }  
}  
  
/**  
 * Your MinStack object will be instantiated and called as such: * MinStack obj = new MinStack(); * obj.push(value); * obj.pop(); * int param_3 = obj.top(); * int param_4 = obj.getMin(); */

https://leetcode.com/problems/3sum/description/

배열의 3 요소를 합쳤을 때 값이 0이 되는 조합을 찾는 문제이다. 이 때 같은 숫자의 조합은 중복되어 처리하지 않는다.

우선 처리한 일은 배열의 정렬이다. 인덱스를 순화하며 값의 변화를 예측하기 위해 정렬해주었다.
정렬이 후에는 조합의 합계를 늘리기 위해선 특정 요소의 인덱스를 올리면 되고 낮추기 위해선 인덱스를 낮추면 된다.

요소를 찾기 위해서는 결국 각 인덱스를 순환해야 한다. 이 때 첫 인덱스를 고정적으로 증가시키며 지정해두고, 합계의 값을 비교하여 두 인덱스를 조절하며 조합을 찾아내었다. 중복 요소를 제거하기 위하여, 인덱스를 조절할 때 이전과 같은 경우 인덱스를 추가로 증감하여 같은 값을 제외시켰다.

import java.util.*;  
  
public class Solution {  
    public List<List<Integer>> threeSum(int[] nums) {  
        int n = nums.length;  
  
        List<List<Integer>> answer = new ArrayList<>();  
        Arrays.sort(nums);  
  
        for(int i = 0; i < n - 2; i++){  
            if(i > 0 && nums[i - 1] == nums[i]) continue;  
  
            int j = i + 1;  
            int k = n - 1;  
            while(j < k){  
                int num1 = nums[i];  
                int num2 = nums[j];  
                int num3 = nums[k];  
                if(num1 + num2 + num3 == 0){  
                    List<Integer> triple = new ArrayList<>();  
                    triple.add(num1);  
                    triple.add(num2);  
                    triple.add(num3);  
                    answer.add(triple);  
                }  
  
                if(num1 + num2 + num3 <= 0){  
                    j++;  
                    while(nums[j] == nums[j - 1] && j < k){  
                        j++;  
                    }  
                }else if(num1 + num2 + num3 > 0){  
                    k--;  
                    while(nums[k] == nums[k + 1] && j < k){  
                        k--;  
                    }  
                }  
            }  
        }  
  
  
        return answer;  
    }

https://leetcode.com/problems/rotate-image/description/

매개변수로 주어진 matrix를 90도 돌리는 문제이다. 이 때 별도의 2차원 배열을 사용하는 것이 아니라. 바로 주어진 matrix 배열을 변화시켜야 한다. void 속성의 메서드로 내부적으로 결과를 해결하는 것 같다.

별도의 배열을 사용할 수 없어서 처음에는 당황했으나 위에서 부터 한 row 씩 돌린다고 생각하며
해결했다. 2차원 배열은 일종의 사각형 형태이므로 상우하좌 순으로 돌아간다는 것을 생각하여
돌려주었다. 이때 각 4개의 방향을 임시 변수로 설정해주었다. 문제를 해결하고 나서 생각하니 temp 를 하나만 사용해도 될 수 있다는 것을 깨달았으나.

블로그에 올리기 위해서는 아래의 초기 코드가 이해를 쉽게 할 수 있다고 생각하여
최초에 풀었던 방식으로 코드를 가져왔다.

public class Solution {  
    public void rotate(int[][] matrix) {  
        int n = matrix.length - 1;  
        for(int i = 0; i <= n; i++){  
            // 4분면을 한번에 돌리므로 i row를 돌렸다는 것은 i, n-i 의 row와 col 을 해결한 것이므로  
            // j = i, j < n -i 조건으로 반복 처리하지 않게한다.  
            for(int j = i; j < n - i ; j++){  
                int temp1 = matrix[i][j];        // 상  
                int temp2 = matrix[j][n - i];    // 우  
                int temp3 = matrix[n - i][n - j];// 하  
                int temp4 = matrix[n - j][i];    // 좌  
  
                // 회전  
                matrix[i][j] = temp4;  
                matrix[j][n - i] = temp1;  
                matrix[n - i][n - j] = temp2;  
                matrix[n - j][i] = temp3;  
            }  
        }  
    }  
}

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;  
    }  
}