You Nicholas

가고 가고 또 가면 알게되고, 행하고 행하고 또 행하게 되면 이루게 된다.

1 분 소요

1. 문제Permalink

A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element that has the same value, except for one element that is left unpaired.

For example, in array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9 the elements at indexes 0 and 2 have value 9, the elements at indexes 1 and 3 have value 3, the elements at indexes 4 and 6 have value 9, the element at index 5 has value 7 and is unpaired. Write a function:

def solution(A)

that, given an array A consisting of N integers fulfilling the above conditions, returns the value of the unpaired element.

For example, given array A such that:

A[0] = 9 A[1] = 3 A[2] = 9 A[3] = 3 A[4] = 9 A[5] = 7 A[6] = 9 the function should return 7, as explained in the example above.

Write an efficient algorithm for the following assumptions:

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. Copyright 2009–2022 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

출처: Codility_, https://app.codility.com/programmers/

2. 해결방법 시간복잡도Permalink

  1. 단순 코딩 O(N) or O(Nlog(N))

3. 문제 해결 및 코드Permalink

def solution(A):
if len(A) == 1: return A[0] # 리스트내 값이 1개밖에 없는 경우
A.sort()
for i in range(0, len(A), 2): # 0부터 짝수임을 확인하기 위해 2칸씩 이동한다.
if i + 1 == len(A): return A[i] # 만약 해당 위치 + 1이 마지막인 경우
if A[i] != A[i + 1]: return A[i] # 해당 위치와 다음 위치값이 다른 경우
# 짝수로 이동하는데 다음 값이 만약 다르다면 해당 값은 짝이 없는 것이 된다.
view raw OddOccurrencesInArray.py hosted with ❤ by GitHub

  • 주석을 참고하면서 이해를 돕습니다.Permalink

4. 알고리즘 및 해설Permalink

  1. 해당 문제의 요점은 리스트내 짝을 이루는 값이 있는 지 확인하는 것이다.
  2. 짝을 이룬다 == 해당 값이 2의 배수이다. 이므로 리스트를 정렬해준다.
  3. 정렬된 리스트를 반복문을 통해 경우에 따라 값을 출력한다.
    • 경우 1. 짝수이므로 해당 위치 + 1이 마지막인 경우에는 홀수이므로 출력
    • 경우 2. 해당 위치값과 다음 값이 다른 경우에는 해당 위치값이 짝이 없는 것이므로 출력

5. 알아두면 좋은 정보Permalink

  1. sort()또는 sorted() 함수의 경우 버블과 같이 느린 방식이 아닌 최적화된 정렬 알고리즘 방식을 사용하기 때문에 시간복잡도가 O(nlogn)이 된다.

정렬 알고리즘 문제 해결에 참고한 블로그 : djm03178

참고