리트코드 - 80. Remove Duplicates from Sorted Array II

리트코드 - 80. Remove Duplicates from Sorted Array II

출처 - https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

주어진 정수 배열 nums가 비내림차순으로 정렬되어 있을 때, 각 고유한 요소가 최대 두 번씩 나타나도록 중복을 제거하세요. 요소의 상대적인 순서는 유지되어야 합니다.

어떤 언어에서는 배열의 길이를 변경할 수 없으므로, 대신 결과를 배열 nums의 첫 부분에 배치해야 합니다. 더 정확히 말하면, 중복이 제거된 후에 k개의 요소가 남는다면, 배열 nums의 첫 k개 요소가 최종 결과를 담아야 합니다. 첫 k개 요소 이후의 값은 중요하지 않습니다.

출력을 위해 다른 배열에 추가로 공간을 할당하지 말고, 추가 메모리 공간을 O(1)로 사용하여 입력 배열을 변경하여 이 작업을 수행해야 합니다.

첫 k개 슬롯에 최종 결과를 배치한 후에 k를 반환하세요.

의사코드

k 값을 1로 지정 중복을 나타내는 값을 false로 지정 반복문 시작 (두번째 요소부터 시작)     만약 현재 배열 요소가 이전 배열 요소와 같지 않으면         중복여부 false로 지정         k번째 요소에 값을 추가         k에 +1 추가     만약 같으면서 중복여부가 false라면         중복여부를 true로 변경         k번째 요소에 값을 추가         k에 +1 추가 반복문 종료 k값 리턴

풀이코드

class Solution {
    public int removeDuplicates(int[] nums) {
        int k = 1;
        boolean isDuplicated = false;

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i - 1]) {
                isDuplicated = false;
                nums[k] = nums[i];
                k++;
            } else if (nums[i] == nums[i - 1] && !isDuplicated) {
                isDuplicated = true;
                nums[k] = nums[i];
                k++;
            }
        }

        return k;
    }
}

코드설명

이는 이전 포스팅(링크) - 다른 풀이 에서 아이디어를 참고하였는데, 중복값을 두 개 넣을 수 있기 때문에 분기를 나누었다.

 

nums 배열을 순회하며 i와 i-1번째 배열 값을 비교하여 만족하는 값을 k번째에 추가한다.

k가 1인 까닭은 첫번째 요소는 중복이 존재하든 존재하지 않든 입력이 보장되는 값이기 때문이다.

따라서 for문도 i=1부터 시작하여 비교한다.

 

값이 중복되지 않으면 i번째 값을 k번째에 추가하고, 중복되는 수라면 else if 분기로 들어가서 한 번만 추가된다.

한 번만 추가되어야 하기 때문에 isDuplicated를 true 조건을 걸어주었다.

 

isDuplicated 가 true 이다가 다시 중복되지 않은 값을 만나면 false 가 되어야 하기에 if분기에서 처리되었다.

 

시간복잡도 - O(n)

공간복잡도 - O(1)

문제를 풀며 생각한 흐름과 배운 점

코드 설명과 같다. 이전 포스팅에서 아이디어를 차용해서 생각보다 쉽게 풀었다.

그리고 런타임도 0ms 로 괜찮은 코드인 것 같다.

 

다른코드

class Solution {
    public int removeDuplicates(int[] nums) {
        int j=1;
        for(int i=2;i<nums.length;i++)
            if(nums[i]!=nums[j-1])
                nums[++j]=nums[i];
        return j+1;
    }
}

아...이걸 또 이렇게 줄일수도 있다니 놀랍다..1번째와 2번째 요소는 모두 입력이 보장되는 값이다.

따라서 배열의 세번째 요소부터 값을 비교 하는데 첫번째와 비교를 하여 다르면 추가한다.

네번째는 두번째와 비교, 다섯번째는 세번째와 비교하는 식이다.

 

중복을 두 번까지 허용했으니 이런 방법으로도 코드를 짤 수가 있겠다.

 

정리

이번 문제는 관련된 바로 전 문제를 풀고 봐서 그런지 생각하기가 쉬운 편이었다.

이 방법이 가장 좋은 코드인지는 모르겠지만 어떤 로직을 알고 있다면 생각해내기 편한 것 같다.