문제

https://app.codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/

• 비어있지 않은 정수 배열 A가 주어짐
• A 의 요소는 홀수 개
• 배열의 각 요소는 같은 값을 가진 다른 인덱스의 요소와 쌍을 이루기도 하고 혼자 남는 솔로 도 있음

세 개의 조건이 있음

⚠️

1. 배열의 크기인 N은 1~1,000,000 범위의 홀수 정수
2. A 의 각 요소는 1~1,000,000,000 범위 내 정수
3. A의 값 중 솔로 하나를 빼면 같은 값이 짝수 번 나타남

풀이

처음 풀이는 답은 맞았는데 점수가 반토막 났음

시간 복잡도는 O(N^2) …

🐕효율은 아루나 줘버린 코드

def solution(A):
    q = deque(A)
    for i in range(len(A)):
        value = q[i]
        del q[i]
        if value not in q:
            return value
        q.insert(i, value)

어떻게던 쉽게 풀려고 발악한 것이 보임 . . .

• A를 deque 로 만든 q를 정의하고
• A크기만큼 반복문 돌림
  • value에 i번째 원소를 넣고 원소 q[i] 는 제거함
  • q에 value 가 없다면 value를 return
  • value 랑 같은 값이 q에 있다면 다시 그 자리에 넣어줌

역시 노력 없이 쟁취할 수 있는 성공은 로또밖에 없다 . . .

수정한 코드

def solution(A):
    check = 0
    for i in A:
        check ^= i
    return check

XOR연산을 시키면 같은 값 일 때는 0, 다를 때는 1을 출력한다.

커플이 아닌 솔로 원소는 1개만 있다는 조건이 있으니

모든 원소들을 반복해서 시키면 결국 외로운 녀석 혼자 남게 된다.

비트 연산을 쓸 생각을 못했는데

역시 머리가 좋아야 손가락이 안 힘드나 보다.