Algorithms

[Codility] OddOccurrencesInArray

유자맛바나나 2022. 2. 26. 21:58

 

제약사항

  • N is an odd integer within the range [1..1,000,000];
  • each element of array A is an integer within the range [1..1,000,000,000];
  • all but one of the values in A occur an even number of times.

 

간단한 문제다. A에 들어가는 값이 1~10억이므로 배열의 인덱스와 동일하게 처리하기엔 사이즈가 너무 큼

그래서 Hash를 이용해서 발생한 숫자를 Key로, 발생한 횟수를 Value로 사용함

그리고 2로 나눈 나머지가 0이 안되는 것이 홀수번 발생한 것이므로 해당 숫자를 답으로 리턴

 

Code

class Solution {
    public int solution(int[] A) {
        int res = -1;
        Map<Integer, Integer> count = new ConcurrentHashMap<>();

        for (int i = 0; i < A.length; i++) {
            if (count.containsKey(A[i])) {
                count.put(A[i], count.get(A[i]) + 1);
            } else {
                count.put(A[i], 1);
            }
        }

        for (int no : count.keySet()) {
            if (count.get(no) % 2 != 0) {
                res = no;
            }
        }

        return res;
    }
}

'Algorithms' 카테고리의 다른 글

[프로그래머스] KAKAO RECRUITMENT 2022 신고결과받기  (0) 2022.03.04
[Codility] PermMissingElem  (0) 2022.02.28
[Codility] CyclicRotation  (0) 2022.02.24
[Codility] BinaryGap  (0) 2022.02.22
[프로그래머스] 모의고사  (0) 2022.02.20