https://leetcode.com/problems/h-index

int [] citations = citations [i]는 인용된 횟수 가 주어졌을 때 H-index를 리턴하라.

우선 H-index가 무엇인지 용어부터 명확히 해야 한다.

H-index란 발표한 논문 n편 중, h번 이상 인용된 논문이 H 편 이상이고 나머지 논문이 H번 이하 인용되었을 때 H의 최댓값을 말한다.

정렬

예제를 보자.

int[ ] citations = [3, 0, 6, 1, 5]

이때 이 연구원은 5편의 논문을 발표했다는 것이다. 그리고 각각의 논문의 인용 횟수를 나타내고 있다.

이 정보를 토대로 이 연구원은 3편의 논문이 3회 이상 인용됐고 나머지 2편이 3회 이하로 인용됐다. 따라서 이 사람의 H-index는 3이 된다.

우선은 이상, 이하의 개수를 세야 하는 것이기 때문에 정렬을 하면 더 효율적이게 될 것이다.

[0, 1, 3, 5, 6]

여기서 idx를 이동시키며 확인을 하면 될 것이다. 이때 idx를 기준으로 개수가 정해지고 그 개수 범위 내의 인용 횟수를 확인하면 될 것이다.

class Solution {
    public int hIndex(int[] citations) {

        Arrays.sort(citations);
        int n = citations.length;

        for (int h = n; h > 0; h--) {
            if (citations[n - h] >= h) {
                return h;
            }
        }

        return 0;
    }
}

최종적으로는 O(nlogn)의 시간복잡도로 문제 풀이가 가능하다.

계수 정렬

이 문제는 인용 값의 범위가 0이상 1000 이하이다.

따라서 계수정렬을 쓰면 그다지 큰 공간을 사용하지 않으면서도 O(N+M)의 빠른 속도로 문제를 풀 수 있다.

class Solution {
    public int hIndex(int[] citations) {
        int n = citations.length;
        int[] count = new int[n + 1];

        for (int c : citations) {
            if (c >= n) {
                count[n]++;
            } else {
                count[c]++;
            }
        }

        int total = 0;
        for (int i = n; i >= 0; i--) {
            total += count[i];
            if (total >= i) {
                return i;
            }
        }

        return 0;
    }
}

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

마지막 인덱스 위치에 도달하기까지 최소 점프 횟수를 구하는 문제이다.

예를 들어 i에 위치해 있다면 0≤j≤nums [i]인 j 만큼 점프할 수 있다.

항상 마지막 인덱스에 도달할 수 있다고 가정한다.

DFS, 브루트포스

예제를 따라서 해보다 보면 먼저 떠오르는 것은 DFS이다.

DFS를 통해서 모든 가능성을 탐색하고 최소 횟수를 계산하는 것이다.

class Solution {

    static final int INF = Integer.MAX_VALUE;

    public int jump(int[] nums) {
        return dfs(0, nums);
    }

    private int dfs(int pos, int[] nums) {
        System.out.println(pos);
        // 종료조건
        if (pos >= nums.length - 1) {
            // 마지막 위치이상이면 더 이상 점프 불필요
            return 0; 
        }
        // 재귀호출
        int minJumps = Integer.MAX_VALUE;
        for (int i = 1; i <= nums[pos]; i++) {
            int jumps = dfs(pos + i, nums);
            if (jumps != INF) {
                minJumps = Math.min(minJumps, jumps + 1);
            }
        }

        return min;
    } 
}

하지만 모든 경로를 확인하기 때문에 비효율적이다. 생각해보면 과정에서 반복적으로 나오는 부분들이 생긴다.

예를 들어 0 → 3 이나 1 → 3이나 결국 3에서의 점프 횟수가 해당 과정들에 더해지게 된다.

그러면 3에서의 점프 횟수를 저장해 놓으면 더 빠른 계산이 가능할 것이다.

즉 메모이제이션 기법을 사용하면 개선이 가능해진다

class Solution {

    static final int INF = Integer.MAX_VALUE;
    static int[] mem;

    public int jump(int[] nums) {
        mem = new int[nums.length + 1];
        Arrays.fill(mem, INF);

        return dfs(0, nums);
    }

    private int dfs(int pos, int[] nums) {
        // 종료조건
        if (pos >= nums.length - 1) {
            // 마지막 위치이상이면 더 이상 점프 불필요
            return 0; 
        }

        // 이미 확인한 경로면 바로 리턴
        if (mem[pos] != INF) {
            return mem[pos];
        }

        // 재귀호출
        int minJumps = Integer.MAX_VALUE;
        for (int i = 1; i <= nums[pos]; i++) {
            int jumps = dfs(pos + i, nums);
            if (jumps != INF) {
                minJumps = Math.min(minJumps, jumps + 1);
            }
        }

        return mem[pos] = minJumps;
    } 
}

개선은 됐지만 여전히 비효율적이다. 제출 결과를 보니 129ms로 아주 느린 결과를 보였다.

그리디 알고리즘

다시 예제를 분석해보자.

[2, 3, 1, 1, 4]에서 최소 점프 횟수는 2이다. 0 → 1 → 4 인덱스로 점프하는 경로다.

각 위치에서 가장 멀리 갈 수 있는 곳으로 점프하는 것이 유리해 보였으나 이 예제를 보면 항상 최대 거리로 점프하는 것이 최적의 해답이 되는 것은 아니라는 것을 확인할 수 있다.

현재 위치에서 도달할 수 있는 최대 범위와 그 범위 내에서 다음 점프로 갈 수 있는 최대 범위를 관리하면 문제를 해결할 수 있을 것 같다.

그렇다면 관리해야 할 변수는 3가지가 된다.

• 현재 위치
• 현재 도달 가능 최대 위치
• 다음 점프 도달 최대 위치

class Solution {
    public int jump(int[] nums) {
        int jumps = 0;
        int currMax = 0;
        int nextMax = 0;

        // 마지막 위치는 확인이 불필요
        for (int i = 0; i < nums.length - 1; i++) {
            
            // 다음 점프로 도달 가능한 최대 위치
            nextMax = Math.max(nextMax, i + nums[i]);

            // 현재 도달 가능한 최대 위치 도달
            if (i == currMax) {
                jumps++;
                currMax = nextMax;

                // 이미 마지막 인덱스면 종료
                if (currMax >= nums.length - 1) break;
            }
        }

        return jumps;
    }
}

이 풀이는 1ms의 결과를 보이며 아주 빠른 속도로 문제 풀이가 가능헀다.

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

• 입력
  • int [] nums
• 출력
  • 마지막 인덱스에 도달할 수 있는지 여부 boolean

메모이제이션

첫 위치는 0번 인덱스에서 시작된다. 그리고 해당 인덱스의 값인 nums [i]는 최대 점프 길이를 뜻한다.

먼저 문제를 이해하기 이해 하나씩 해보겠다.

[2, 3, 1, 1, 4] 의경우 idx 기준으로 0 → 1→ 4 가 가능하다. 또 0 → 2→ 3 → 4로도 가능하다.

다른 경우를 하나 더 생각해보자. 0 → 1 → 2 → 3 → 4의 경로도 가능하다.

위의 예시에서 보면 알 수 있는 게 있다. 바로 2 → 3 → 4가 반복되고 있다는 것이다.

다시 말해 해당 번호에서 출발하는 경로가 반복돼서 나타나는데 만약 그 경로로부터 도착할 수 없다면 더 이상 탐색할 필요가 없다는 것이다.

필요한 것은 해당 idx에서 도달 가능한 지를 저장하는 테이블이다.

class Solution {
    public boolean canJump(int[] nums) {
	  // false와 true만 있으면 판정이 힘들기 때문에 null이 가능하도록 Boolean 배열로 생성
        Boolean[] isPossible = new Boolean[nums.length];
        return dfs(0, nums, isPossible);
    }

    private boolean dfs(int v, int[] nums, Boolean[] isPossible) {
        if (v >= nums.length - 1) {
            return true;
        }

        if (isPossible[v] != null) {
            return isPossible[v];
        }

        for (int u = v + 1; u <= v + nums[v]; u++) {
            if (dfs(u, nums, isPossible)) {
	            // 재귀를 모두 통과했다는 것은 방문이 가능하다는 것.
                return isPossible[v] = true;
            }
            if (u >= nums.length - 1) {
            // 범위를 벗어난 것은 볼 필요 없다.
                break;
            }
        }
				// 모든 지점을 확인했는데도 true를 리턴하지 못했다는 것은 방문하지 못한다는 것
        return isPossible[v] = false; 
    }
}

하지만 이 알고리즘은 최악의 경우 O(N^2)의 시간복잡도를 가진다. 실제로는 메모이제이션으로 인해 더 적은 시간이 소요되겠지만 여전히 비효율적이다.

그리디 알고리즘

각 위치에서 최대한 멀리 갈 수 있는지를 판단하면 전체적인 도달 가능성을 확인할 수 있다.

즉 현재 최대로 도달 할 수 있는 위치를 기록하고 현재 인덱스가 그보다 크면 도달할 수 없다는 뜻이므로 false를 반환한다.

도달할 수 있다면 최대 도달 위치를 갱신해 준다.

class Solution {
    public boolean canJump(int[] nums) {
        int max = 0; // 도달할 수 있는 최대 위치

        for (int i = 0; i < nums.length; i++) {
            // 최대 이동 위치보다 먼 곳 = 도달할 수 없는 곳
            if (i > max) {
                return false;
            }
            // 만약 현재 위치에서 더 멀리 갈 수 있다면 그 위치로 최대 위치를 갱신
            max = Math.max(max, i + nums[i]);
        }

        return true;
    }
}

이 방법이면 O(N)의 시간복잡도로 해결이 가능하다.

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii

•  입력
  • int [] prices i 일의 가격이 들어있는 배열
• 출력
  • 여러 번 사고팔 수 있을 때의 최대 이익
  • 단 한 번에 하나의 주식만 보유할 수 있다.

구매와 판매를 여러 번 할 수 있는 상황이다. 대신 주식은 한 번에 한 개만 보유할 수 있다.

이익이 나는 동안은 가지고 있다가 가격이 내려가기 직전에 판매해야 최대 이익을 볼 수 있다.

이는 곧 이전의 기록과 비교하는 동작이다.

Deque를 이용한 풀이

가장 최근 기록과 비교하는 것은 stack을 사용하면 될 것 같다.

그런데 이익을 계산할 때 가장 아래에 쌓여 있는 데이터와 가장 위에 쌓여 있는 데이터의 차이를 계산해야 한다.

차라리 그럴거면 deque를 사용해 양 쪽 접근이 쉽게 처리하겠다.

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;
        
        Deque<Integer> deque = new ArrayDeque<>();
        deque.addLast(prices[0]);

        for (int i = 1; i < prices.length; i++) {
            if (deque.peekLast() > prices[i]) {
                int max = deque.peekLast();
                int min = deque.peekFirst();

                profit += max - min;

                while (!deque.isEmpty()) {
                    deque.poll();
                }
            }
            deque.addLast(prices[i]);              
        }

        if (!deque.isEmpty()) {
            int max = deque.peekLast();
            int min = deque.peekFirst();

            profit += max - min;
        }

        return profit;
    }
}

deque에 데이터를 넣는다.

만약 가격이 peekLast보다 작다는 것은 가격이 떨어지는 순간이니 먼저 팔아야 한다.

쌓여있는 가격들에서 가장 위의 가격에서 가장 아래 가격을 뺀 것이 이익이 된다.

만약 데이터가 1개만 들어있다 해도 어차피 이익이 0으로 계산되니 문제없다.

그 후 deque를 비워준 뒤 새로운 가격을 넣어주면 된다.

마지막으로 순회가 끝났을 때 즉 마지막날에 판매가 됐을 때 이익이 발생하는 경우를 고려해줘야 하기 때문에 deque가 비어있지 않다면 이익 계산을 한 번 더 수행해 준 뒤 최종 이익을 반환해 준다.

그리디 알고리즘

하지만 위의 방식은 쓸데없는 공간을 사용하고 복잡도를 증가시키고 있다.

이 문제는 그냥 그리디 알고리즘으로 가격이 상승하는 구간마다 이익을 취하면 된다.

팔자마자 다시 살 수 있다는 점 때문에 굳이 구간 이익이 최대일 때 팔 필요가 없다.

1. 배열을 한 번 순회한다.
2. 현재 가격이 이전 가격보다 높다면 그 차이를 이익에 더한다.

class Solution {
    public int maxProfit(int[] prices) {
        int profit = 0;

        for (int day = 1; day < prices.length; day++) {
            if (prices[day - 1] < prices[day]) {
                profit += prices[day] - prices[day - 1];
            }
        }

        return profit;
    }
}

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

정수 배열 nums를 k번 오른쪽으로 회전시키는 문제이다.

• 입력
  • int[]int [] nums
  • int k
• 출력
  • void → nums 자체를 변경해야 한다.

문제 조건에서 nums와 k의 최대 값이 10^5로 상당히 크다

임시 배열을 만들어서 해결

int[] nums와 같은 크기의 임시 배열(int [] tmp)을 만들고 거기에 회전한 배열을 저장한다.

그 후 tmp의 값들로 nums를 덮어 씌우면 끝난다.

k만큼 오른쪽으로 회전한다는 것은 시작점이 이동되는 것과 마찬가지이다.

class Solution {
    public void rotate(int[] nums, int k) {
        int[] tmp = new int[nums.length];
        int size = nums.length;
        int start = size - k % size;

        for (int i = 0; i < size; i++) {
            tmp[i] = nums[(start + i) % size];
        }

        for (int i = 0; i < size; i++) {
            nums[i] = tmp[i];
        }
    }
}

오른쪽으로 회전하고 있기 때문에 시작점 계산을 size - k % size로 처리한다.

이 시작점의 값이 새로운 tmp 배열의 첫 위치에 들어갈 값이 된다.

이제 배열의 크기만큼 순회하면서 채워 넣어주면 된다. 나머지 연산을 통해서 범위를 벗어나지 않도록 처리해 줬다.

하지만 이 풀이에는 문제가 있다. 별도의 추가 공간을 사용하고 있다는 점이다.

결국 nums 배열 자체를 수정해야 하는데 추가 공간을 사용하지 않고 수정할 수는 없을까?

배열의 반전

배열의 회전이란 것은 기준점을 두고 두 부분으로 나뉘고 그 두 부분의 위치가 바뀌는 것이다.

그런데 이 두 부분의 위치를 직접 바꾸면 시간복잡도가 증가하거나 추가 공간이 필요하게 된다.

이때 필요한 게 반전이다.

전체를 반전하게 되면 두 부분의 위치가 교환이 된다.

그러고 나서 각 부분을 다시 반전시키면 정상 순서로 위치만 바뀐 결과가 리턴된다.

즉 여기서 작성해야 할 코드는 특정 범위를 반전시키는 코드이다.

class Solution {
    public void rotate(int[] nums, int k) {
        int size = nums.length;
        k = k % size;

        reverse(nums, 0, size - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, size - 1);
    }

    private void reverse(int[] arr, int l, int r) {
        while (l < r) {
            // 교환
            int tmp = arr[l];
            arr[l] = arr[r];
            arr[r] = tmp;
            // 포인터 이동
            l++;
            r--;
        }
    }
}

반전은 해당 범위의 요소를 swap 해가며 반복하면 된다.

이를 통해서 추가 공간을 사용하지 않고 동시에 O(N)의 시간복잡도로 문제를 해결할 수 있었다.

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii

오름차순으로 정렬된 nums가 주어졌을 때 중복된 요소를 제거해야 한다.

단 각각의 중복된 요소들은 최대 2개까지 유지된다. 요소들의 상대적 위치는 유지돼야 한다.

배열의 길이를 수정하는 것이 불가능하기 때문에 제거되지 않은 요소들을 앞에 위치시키고 제거된 요소들은 뒤에 위치시켜야 한다.

최종적으로 nums를 수정한 다음 유효한 숫자들의 개수를 반환해야 한다.

추가 공간을 사용해서는 안된다.

https://leetcode.com/problems/remove-duplicates-from-sorted-array

이 문제와 유사한 문제이지만 공간 조건이 추가됐고 중복 요소가 2개까지 유효하다는 조건이 추가됐다.

문제를 분석하고 구상해 보자.

1. 정렬이 된 상태이다. 즉 중복된 요소들은 인접해 있다.
2. 추가 공간을 사용할 수 없으므로 int [] nums 배열 내에서 조작을 해야 한다.
3. 중복 허용 횟수 조건이 생겼다. 최대 두 번까지 허용된다. → 관리가 필요하다.

어떤 방식들이 있을까

1. 카운터 현재 숫자의 출현 횟수를 세는 카운터를 두고 중복 횟수를 관리한다. → 이동이나 삭제는 어떻게 처리하지. 이 과정에서 비효율적일 수 있겠다.
2. 해시맵 혹은 해시 셋 추가 공간 사용이 불가능하다.
3. 투 포인터 배열을 순회하며 중복되지 않은 요소들을 배열의 앞부분에 모은다. 중복 허용 횟수 관리가 필요하다 → 이전 요소와 비교

따라서 투 포인터 방식을 채택한다.

두 개의 포인터를 둔다. s는 조건을 만족하는 유효한 숫자를 저장할 위치, p는 배열을 순회하는 포인터이다.

class Solution {
    public int removeDuplicates(int[] nums) {
        int s = 0;
        
        for (int p = 0; p < nums.length; p++) {
            if (s < 2 || nums[p] != nums[s - 2]) {
                nums[s] = nums[p];
                s++;
            } 
        }

        return s;
    }
}

큰 틀은 이전 문제와 유사하다. 이제 중요한 것은 중복 허용 횟수를 관리하는 방법이다.

우선 s가 2보다 작은 경우 즉 첫 두 개의 경우 무조건 조건을 만족하는 요소가 된다.

그 이후의 요소들을 검사해야 한다.

현재 위치(p)에서 앞의 두 요소와 현재 요소를 비교한다.

이때 nums [p]가 nums [s-2]와 다르다면 중복 횟수가 허용 범위 내라는 소리이다. 왜냐하면 nums[s-2]와 nums [s-1]이 이미 동일하다면 현재 요소까지 포함하면 중복이 3번이 되기 때문이다.

https://leetcode.com/problems/remove-duplicates-from-sorted-array

중복되는 숫자를 제거하는 문제이다. int[] nums 배열 자체를 수정해야 한다.

nums는 오름차순으로 정렬 돼 있는 상태로 주어진다.

각 원소들의 상대적 위치는 유지 돼야 한다. 이때 nums 배열의 유니크한 원소의 개수(k)를 리턴하면 된다.

예시를 보자. int[] nums = [1, 1, 2] 일 경우 1 이 중복된다. 따라서 nums = [1, 2, _ ]로 변경되고 k는 2가 된다.

int[] nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4] → [0, 1, 2, 3, 4, _, _, _, _, _ ] 이렇게 되고 k는 5가 된다. 기존의 상대적인 순서를 유지한다는 특징이 있다.

구상을 해보자.

1. 정렬이 돼 있다는 것은 중복이 존재하는 경우 연속으로 나온다는 뜻이다.
2. 배열 자체를 수정하기 때문에 요소를 제거하는 것이 아니라 유효한 요소들을 앞으로 모으는 작업이 필요하다.
3. 추가적인 자료구조는 사용할 수 없다. 주어진 int[] nums를 사용해야 한다.

가장 먼저 떠오르는 방법은 중복 요소가 발견되면 가장 뒤로 밀어내는 것이다. 하지만 이 방식은 O(N^2)의 시간복잡도로 매우 비효율적인 알고리즘이 된다.

배열을 순회하면서 교환이 필요하다. 이를 위해 두 개의 포인터를 사용하기로 했다. 즉 투포인터이다.

하나의 포인터는 중복되지 않은 요소의 위치를 가리키고 다른 하나는 배열을 순회하면서 중복을 검사한다.

정렬이 돼 있다 즉 인접한 요소만 보면 중복 검사가 가능하다.

class Solution {
    public int removeDuplicates(int[] nums) {
        int p1 = 0;
        
        for (int p2 = 1; p2 < nums.length; p2++) {
            if (nums[p1] != nums[p2]) {
                p1++;
                nums[p1] = nums[p2];
            }
        }

        return p1 + 1;
    }
}

p1은 유효한 숫자들이 자리 잡을 포인터이다.

p2는 이제 중복이 나오는 지를 확인하고 해당 값의 위치를 이동 시키기 위한 포인터이다.

이 알고리즘은 중복된 숫자가 나오면 마지막 중복 위치를 찾고 지금까지 유효한 위치 다음 위치에 해당 값을 대입하는 동작을 수행한다.

이를 통해 O(N)의 시간복잡도로 문제를 해결할 수 있었다.

https://leetcode.com/problems/remove-element

int[] nums 배열에서 int val과 같은 값을 제거하는 문제이다.

특이한 점은 removeElement의 리턴 타입이 int인데 정답 처리가 리턴 값만 맞으면 되는 것이 아니라는 점이다.

추가로 val과 같은 값이 제거된 nums 배열이 in-place 형태로 즉 추가 공간 사용 없이 내부에서 수정돼야 한다.

예를 들어보자.

nums = {0, 1, 2, 2, 3, 0, 4, 2} 이고 val = 2 일 때이다.

nums에서 2를 제거하게 되면 {0, 1, _, _, 3, 0, 4, _}가 되고 이게 최종적으로 {0, 1, 4, 0, 3, _, _, _} 이 돼야 한다. 그리고 리턴 값은 제거되지 않은 유효 숫자인 0, 1, 4, 0, 3의 개수인 5가 된다.

또한 nums의 정렬 순서는 중요하지 않다. 어차피 정답 판정 시에 유효 범위에서 정렬 작업이 수행된다. 위의 예시에서는 {0, 1, 3, 0, 4}가 나오던 {0, 1, 4, 0, 3}가 나오던 문제없다는 것이다.

대신 int[] nums를 조작하는 것이기 때문에 ‘_’라는 부분은 임의의 숫자가 들어가도 괜찮고 정렬이 0, k (k는 유효한 숫자의 개수)에서 동작해서 정답 판정이 들어가기 때문에 유효한 숫자들이 앞에서부터 자리를 차지하고 있어야 한다는 점을 주의해야 한다.

그냥 시키는 대로 풀기

그냥 시키는 대로 풀어보자. nums에서 val을 제거하고 정렬하면 된다.

우선 문제의 조건을 보니 nums의 원소는 최대값이 50이다. 제거되지 않은 요소들을 앞에 두기 위해 제거되는 요소들의 값을 51로 바꾼 다음 정렬하면 자연스럽게 제거되지 않은 요소들만 앞으로 가게 된다.

class Solution {
    static final int MAX = 51;
    public int removeElement(int[] nums, int val) {
        int k = nums.length; // 유효값 카운트
        for (int i = 0; i < nums.length; i++) { // 여기서 i < k를 쓰면 안된다. k값은 계속 변한다.
            if (nums[i] == val) {
                nums[i] = MAX;
                k--; // 전체 갯수에서 하나가 제거됐다.
            }
        }
        Arrays.sort(nums); // 제거되지 않은 값들이 자연스럽게 0~k 범위 내로 몰린다.
        return k;
    }
}

문제없이 정답이지만 이게 좋은 풀이일까? 문제의 설명을 보면 정답을 판정하는 과정에서 (0, k) 사이의 정렬이 한번 일어난다.

이 말은 nums가 정렬되지 않은 상태로 반환 돼도 괜찮다는 것이다.

그런데 위의 풀이에서는 쓸데없이 정렬 작업이 한 번 들어가고 있다. 결국 시간복잡도는 O(NlogN)이 된다.

심지어 nums[i] 를 MAX로 바꾸는 것은 편법에 가깝다는 생각이 든다.

앞에만 몰아 넣으면 된다.

생각해 보자. 유효한 숫자는 앞에 순서에 상관없이 몰아넣으면 된다.

유효하지 않은 숫자는 변경할 필요 없이 뒤로 몰아 넣으면 된다.

이 두 작업을 투 포인터를 이용해서 할 수 있다.

class Solution {
    static final int MAX = 51;
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;

        while (left <= right) {
            if (nums[left] == val) {
                // val을 right 위치의 값으로 덮어 씌운다.
                nums[left] = nums[right];
                right--;
            } else {
                left++;
            }
        }

        return left;
    }
}

코드를 보면 두 개의 포인터가 이동하고 있다. 목표는 앞의 위치의 val을 제거하는 것이다. 따라서 nums [left]의 값이 val과 일치한다면 nums [right]의 값으로 덮어 씌운다.

여기서 nums[right]가 val과 동일하더라도 상관없다. left의 위치가 그대로 이므로 다음번 검사 때 감소된 right의 위치와 비교를 통해 새롭게 덮어 씌워질 것이다.

이 방법을 통해 시간복잡도를 O(N)으로 줄일 수 있었다.

https://leetcode.com/problems/merge-sorted-array

LeetCode 기준 Easy 난이도의 문제입니다. 두 배열을 정렬된 상태로 변환하는 문제인데 특이하게 입력받은 nums1 배열을 정렬하는 문제입니다. nums1을 반환하는 것이 아니라 nums1 자체를 정렬하면 된다는 점을 주의해야 합니다.

또 다른 특이한 점이 있습니다. 병합 후 정렬해야 하는 문제이기 때문에 배열의 특성상 사이즈에 여유가 있어야 합니다. 따라서 nums1에 nums2가 들어갈 공간만큼 0으로 차 있는 상태입니다.

문제를 보자마자 떠오른 풀이법은 그냥 nums1의 0을 앞에서부터 nums2로 채우고 정렬하면 되는 거 아닌가? 였습니다.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) return; // n == 0이라는 것은 병합할 nums2가 없다는 것

        int idx = 0; // nums2의 첫 위치
        for (int i = m; i < m + n; i++) {
            nums1[i] = nums2[idx++]; // nums1의 0을 앞에서부터 nums2로 채운다
        }

        Arrays.sort(nums1); //nums1 정렬
    }
}

정답 처리에는 문제가 없었습니다. 하지만 이 풀이는 시간복잡도가 O((m+n)log(m+n))으로 효율적이지도 않고 문제의 의도와도 다르다는 생각이 들었습니다.

문제에서 제대로 사용하지 않은 조건이 하나 있습니다. 바로 nums1, nums2 두 배열 모두 정렬이 돼 있는 상태라는 것입니다. 이 조건을 활용해야 합니다.

이미 정렬이 된 두 배열을 합치는 작업? merge sort에서 병합하는 과정과 유사하다는 생각이 들었습니다.

보통 병합하는 과정에서는 두 정렬된 배열에서 앞에서부터 비교하며 새로운 배열을 생성하는 과정을 반복합니다. 하지만 이 문제에서는 nums1에 합쳐야 합니다. 따라서 가장 큰 값부터 찾아 뒤에서부터 채우는 방식으로 구현하였습니다.

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (n == 0) return; // 병합할 것이 없다.
        int p1 = m - 1; // nums1의 유효숫자의 마지막 위치
        int p2 = n - 1; // nums2의 유효숫자의 마지막 위치
        int p = n + m - 1; // 빈 공간의 마지막 위치

        while (p2 >= 0) {
            // p2가 음수가 되는 순간 모든 배열을 병합한 것
            if (p1 >= 0 && nums1[p1] > nums2[p2]) {
                nums1[p--] = nums1[p1--];
            } else {
                // nums2[p2] >= nums1[p1]
                nums1[p--] = nums2[p2--];
            }
        }
    }
}

이 풀이를 통해 O(m+n)의 시간복잡도로 효율적으로 풀 수 있었습니다.