[Codility] OddOccurrencesInArray

https://app.codility.com/c/run/trainingQ4R62N-U5Z/

Codility

 

 

접근 방식

같은 값이 두 번 등장하면 짝이 맞으니까 사라지고, 홀수 번 등장하는 값만 마지막에 남기는 방식으로 풀이

List나 HashSet을 이용하여 해결! 

1. 배열을 왼쪽부터 오른쪽까지 순회하면서 원소를 하나씩 확인
2. 어떤 값 x를 처음 만났을 때는 아직 짝이 없다는 의미이므로 저장
3. 같은 값 x를 두 번째로 만나면 짝이 맞았다는 의미이므로 저장했던 것을 제거

이렇게 계속 반복하면,

짝이 두 번, 네 번, 여섯 번… 등장한 값은 모두 사라지고, 홀수 번(보통 1번) 등장한 값만 마지막에 남게 됨

나의 풀이 코드

내 풀이의 문제점

• list.contains(value) → 리스트 전체를 훑어야 하므로 O(N)
• list.remove(Integer.valueOf(value)) → 위치 찾기 + 뒤 요소 밀어주기까지 O(N)

이 연산들이 배열 길이 N번 반복되기 때문에 전체 시간 복잡도는 O(N²) 가 된다.

public int solution(int[] A) {
        List<Integer> list = new ArrayList<>(); 

        for (int i = 0; i < A.length; i++) {
            int value = A[i];

            if (list.contains(value)) {
                list.remove(Integer.valueOf(value));
            } else {
                list.add(value);
            } 
            
        }

        return (list.size() > 0) ? list.get(0) : 0; 
    }

 

HashSet을 사용한 리팩토링 코드

List → HashSet으로 바꾸면서 contains, add, remove가 평균 O(1) 이 되어 전체 시간 복잡도가 O(N) 으로 내려감

 

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int solution(int[] A) {
        Set<Integer> set = new HashSet<>();

        for (int v : A) {
            if (set.contains(v)) {
                // 이미 한 번 등장했던 숫자 → 짝이 생겼으니 제거
                set.remove(v);
            } else {
                // 처음 등장한 숫자 → 나중에 짝이 나올 수 있으니 추가
                set.add(v);
            }
        }

        // 문제 조건상 짝이 없는 원소는 정확히 하나 존재
        // 따라서 set에는 그 숫자 하나만 남게 된다.
        return set.iterator().next();
    }
}

 

List와 Set 성능 비교

연산	ArrayList	HashSet	이유
contains(value)	❌ O(N)	✔ O(1)	List는 전체 탐색, Set은 해시로 바로 찾음
remove(value)	❌ O(N)	✔ O(1)	List는 찾고, 뒤 요소들까지 당겨야 함
add(value)	✔ O(1) amortized	✔ O(1)	거의 동일하지만 remove, contains에서 차이 극대화

 

👎 List(ArrayList)의 문제점 — O(N)

contains(value) = O(N)

List는 내부 구조가 순차 배열로 이루어져 있기 때문에 값이 있는지 확인하려면 처음부터 끝까지 하나씩 비교해야 한다.

: 최악의 경우 N번 비교 → O(N)

list.contains(x)
→ list[0] == x ?
→ list[1] == x ?
→ list[2] == x ?
…
→ list[N-1] == x ?

 remove(value) = O(N)

remove(value) 실행 단계 

1. 값을 찾기 위해 전체 탐색 → O(N)
2. 찾은 뒤 뒤 요소들을 한 칸씩 당김 → O(N)

remove ≒ O(N) + O(N) = O(N)

 

👍 Set(HashSet)의 강점

HashSet은 내부 구조가 해시 테이블루 구성 

• 값 → hashCode()로 버킷 위치가 바로 계산됨
• 전체를 뒤지지 않고 해당 위치만 확인
  • contains(value) = O(1)
  • add(value) = O(1)
  • remove(value) = O(1)
    
• O(N) × O(1) = O(N)

 

 

정리

List → 값 찾으려면 전체를 순회해야 한다 (선형 구조)
Set  → 값의 위치를 해시로 바로 계산한다 (해시 테이블)