[Leetcode Top Interview 150] 26. Remove Duplicates from Sorted Array

난이도 : easy 

문제링크

• 오름차순인 nums를 오직 한번만 나타나는 유일한 값만 남겨라 (in-place)
  • 중복 지우기
  • nums 는 오름차순일 것
• 남아있는 요소의 갯수를 리턴하라
• int[] nums
  • 1 <= nums.length <= 3 * 10^4
  • -100 <= nums[i] <= 100

 

1. 접근법

• 보여주려는 원소는 앞으로 당겨야 함
  • 원소가 달라지면 달라졌던 횟수만큼 앞으로 당기기
  • 달라진 횟수가 해당 원소가 있어야 할 자리임
• 유일한 원소만 보고싶으니까
  • 원소가 다르면 보여주려는 범위를 하나씩 늘리기

 

2. 의사코드

for (i 첫번째...마지막) {
	if (nums[i]가 nums[i+1]과 달라지면) {
       nums[i+1]을 현재까지 탐색하면서 달라졌던 횟수에 맞는 자리에 두기
    }
}

return 달라진 횟수 + 1

 

3. 구현 코드

class Solution {
    public int removeDuplicates(int[] nums) {
        int count = 0;      

        for (int i = 0; i < nums.length-1; i++) {
            if (nums[i] != nums[i+1]) {
                nums[++count] = nums[i+1];
            }
        }
        
        return count+1;
    }
}

• 보여주고 싶은 원소 범위는 첫번째 인덱스도 포함해야 함
• 그러므로 count+1 을 리턴함

 

4. 시간복잡도, 공간복잡도 예상

• 시간복잡도 : O(n) - n개 원소까지 반복하므로
• 공간복잡도 : O(1) - n개 원소를 돌아도 반복문 안에서 선언되는 변수는 없으므로 상수값만 메모리에 잡힘

 

5. 개선점

잘 모르겠다

 

6. 회고

다른 블로그를 검색해도 나랑 거의 똑같이 풀었다.

 

class Solution {
    public int removeDuplicates(int[] nums) {
        int index = 1;

        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] != nums[i + 1]) {
                nums[index++] = nums[i + 1];
            }
        }

        return index;
    }
}

(출처 : https://bcp0109.tistory.com/260)

 

위의 코드가 더 나은것 같다 

왜냐하면 

1. 맨 앞의 값은 당연히 포함되므로 index를 1로 설정함으로써 for문의 가독성과 응집성이 올라간다

2. index값만 리턴하므로 왜 1을 더했는지 생각하지 않아도 된다

 

처음부터 무식하게 반복문을 돌리다가 잘 안풀렸다.

그러다 '아니 내가 보여주고 싶은 값은 유일한 값인데 그렇다면 유일하게 변한 카운트를 세서 카운트 수만큼 앞에 배치하고

카운트 값 리턴하면 되는거 아니야?' 이런생각이 들었다

 

그래서 막 다 해보면서 왜안되지 생각하다 작성된 코드 베이스로 짜다보니 의도가 확실히 전달되지 않았다

좀더 침착하게 짰으면 어땠을까 생각이 든다

물론 저런 생각을 한것도 문제 의도에 일치한다 생각한다

자꾸 빨리 푸려는게 있어서.. 잘 풀더라도 작은 것들 때문에 말릴 수 있다. 

침착하게 생각을 정리하고 코드를 작성해야겠다