[리트코드] 26.Remove Duplicates from Sorted Array / 169.Majority Element / 80.Remove Duplicates from Sorted Array II

[zzu-yaaa]

79ec551

26. Remove Duplicates from Sorted Array

성공(3m 15s)

카테고리

배열

접근

1. 주어진 배열을 돌면서 cur(마지막으로 삽입한 값)과 현재 배열의 값이 일치하지 않으면 삽입

분석

O(N)

• 입력 배열의 크기가 최대 3 * 10^4 이므로 처리하기 충분한 시간

회고

시간복잡도 참고

시간 복잡도	안전한 N의 최대 크기 (1초 기준)	설명
O(1)	제한 없음	상수 시간
O(log N)	10⁹ 이상도 가능	아주 빠름
O(N)	~10⁷ (천만)	일반적으로 1초 안에 처리 가능
O(N log N)	~10⁶ (백만)	log N ≈ 20이라면 2천만 연산 정도
O(N²)	~10³ ~ 10⁴	백만 번 연산 → 1초 위험선
O(N³)	~100 이하	100³ = 100만 → 위험함
O(2^N)	~20 이하	2²⁰ ≈ 100만
O(N!)	~10 이하	10! = 362만, 그 이상은 불가능

80. Remove Duplicates from Sorted Array II

성공 (13m 54s)

카테고리

배열

접근

1. 주어진 배열을 돌면서 cur(마지막으로 삽입한 값)과 현재 배열의 값이 일치하지 않으면 삽입
2. 1에서 cnt(cur 사용 횟수)를 0으로 초기화
3. cur과 현재 배열의 값이 일치하더라도 cnt가 0이면 삽입 후 cnt 증가

분석

O(N)

회고

직전(i-1)이 아닌 그 전의 값(i-2)와 비교하면 변수 사용 개수를 줄일 수 있음

class Solution {
    public int removeDuplicates(int[] nums) {
        int k = 2;

        for(int i=2; i<nums.length; i++){
            if(nums[i] != nums[k-2]){
                nums[k++] = nums[i];
            }
        }

        return k;
    }
}

1. k (결과 배열의 인덱스) 정의
2. 주어진 배열을 돌면서 k-2번째 값과 현재 값이 일치하지 않으면 값 삽입 & 인덱스 증가

169. Majority Element

성공(6m 9s)

카테고리

배열

접근

1. 주어진 배열을 돌면서 맵에 해당 원소가 나온 개수를 저장
2. 저장된 맵을 돌면서 값이 n/2 보다 큰 것을 반환

분석

O(N)

회고

공간복잡도 O(1)로 개선 가능

Boyer-Moore Voting Algorithm (보이어-무어 보팅 알고리즘)

• 하나의 후보를 정해 같은 값이면 cnt + 1, 다른 값이면 cnt -1 하는 과정을 반복하고 cnt가 0이 되면 새로운 후보를 지정하는 방식을 반복하여 과반수 이상의 값을 찾는 알고리즘
• 조건 : 과반수 원소가 무조건 존재해야함

class Solution {
    public int majorityElement(int[] nums) {
        int val = nums[0];
        int cnt = 1;

        for(int i=1; i<nums.length; i++){
            if(val == nums[i]){
                cnt += 1;
            }
            else if(cnt > 0){
                cnt -= 1;
            }
            else{
                val = nums[i];
                cnt += 1;
            }
        }

        return val;

    }
}

공간복잡도 O(N) → O(1) 로 개선
정답 제출시 13ms → 1ms 속도 개선