[코테]코딜리티 - OddOccurrencesInArray

문제

문제 요약

• int[] A가 매개변수로 주어짐.
• A에는 짝으로 지어진 요소들이 포함되어 있으며, 이 중 단 한 요소만 짝이 없음.
• 배열에서 짝이 없는 숫자를 찾아서 반환해야함.
• 1 <= A.length <= 1,000,000
• 1 <= 각 요소 <= 1,000,000,000

문제 분석

나는 다음 단계에 따라 문제를 분석하였다. 이번 문제의 핵심은 시간 복잡도이다.

• 배열의 각 요소를 순회하며, 요소를 Map에 저장
• 저장된 Map에 동일한 요소가 있을 경우 삭제
• 최종적으로 Map에 남은 요소의 key를 획득하여 value를 반환

로직은 간단하지만 시간복잡도를 고려하다보니 Map이 제일 간단하다고 느꼈다. 우선 A의 길이가 1,000,000이다. 여기서 1개의 요소를 다른 요소와 비교하려면 적어도 O(n2)의 시간이 들어간다. 1,000,000^2 = 1,000,000,000,000이다. 말하지 않아도 심각하다는 것을 알 수 있다. 물론 배열을 삭제해 나가면서 처리하면 조금은 줄어들지도 모르지만 그것보다는 Map을 이용해 O(n)의 시간으로 한번의 반복을 통해 결과를 도출해낼 수 있었다.

슈도코드

요소를 담을 맵 생성

for(A의 길이만큼){
	if(Map에 A[index]가 없다면){
    	Map에 A[index] 저장
    } else{
    	Map에서 A[index] 삭제
    }
    
}

정답을 담을 변수 선언
for(맵의 키만큼 반복(1로 고정)){
	정답변수에 Map에서 보유한 key로 value 대입
}

정답반환

구현코드

import java.util.Map;
import java.util.HashMap;

class Solution {
    public int solution(int[] A) {
        Map<Integer, Integer> map = new HashMap<>();

        //배열의 각 요소를 map에 저장한다.
        for (int i = 0; i < A.length; i++){
            if(!map.containsKey(A[i])){
                map.put(A[i], A[i]);
            } else{
                //이때 map에 기존에 저장된 요소와 동일한 값이 있다면 삭제한다.
                map.remove(A[i]);
            }
        }

        //최종적으로 map에 남은 요소를 반환한다.
        int answer = 0;
        for(Integer key : map.keySet()){
            answer = map.get(key);
        }

        return answer;
    }
}

마무리

여기서 한가지 아쉬운 점은 마지막에 map.keySet()이 아닌 다른 방법으로 반환 할 수 있지 않을까? 라는 생각이 들었지만 시간에 영향을 미치지도 않으며 테스트 특성 상 key는 언제나 1개만 남기 때문에 저렇게 진행하였다. 배열을 같이 삭제해 나가는 방법도 있겠지만 그 부분은 다음에 시도해보려 한다.