[ Codility ] Distinct - python

개념

Lesson 6. Sorting 첫 번째 문제

 

문제요약

N개의 정수를 원소로 갖는 배열A가 입력으로 주어질 때, 원소들의 중복을 제외한 총 개수를 리턴하라

 

첫 번째 접근 (효율성 고려X, 통과는 O)

파이썬 내장함수를 이용한 풀이(set로 중복 제거한뒤 그 개수만 리턴하는 코드)

# 방법 1
def solution(A):
    return len(list(set(A)))
    
    
# 방법 2 - 굳이 list를 안해도 돼 ㅎㅁㅎ
def solution(A):
    return len(set(A))

생각보다 너무 빨리 대충 푼 것 같은 느낌에 set 쓰지 않고 푸는 다양한 방식을 찾아보기로 했다

 

두 번째 접근 (효율성X)

처음 파이썬을 배웠다면 썼을 것 같은 코드로 문제에 충실하게 짠 코드.

A를 쭉 돌다가 지금까지 나온 적이 없는 숫자인지 확인한 뒤에 없다면 새로운 리스트(tmp)에 넣어주고 아니면 지나가는 코드. 마지막에 tmp의 길이를 리턴하는 코드. 반복문을 두번 돌고 비교하는 작업이 있어서 O(N**2)의 시간복잡도가 나온다.

def solution(A):
    tmp = []
    for num in A:
        if num not in tmp:
            tmp.append(num)
    return len(tmp)

 

세 번째 접근 (딕셔너리 활용)

시간복잡도를 고려해서 딕셔너리를 활용해봐야겠다고 생각. 

파이썬 리스트의 경우 len조회, append는 O(1)이지만 in, not in 확인은 O(N)의 시간복잡도를 가진다. 반면 딕셔너리의 경우 키로 값을 조회하거나, 값을 지정하거나, 길이 조회 및 삭제 모두 O(1)의 시간복잡도를 갖기 때문에 저 위 코드의 in, not in에서 걸리는 시간을 개선할 수 있을 것 같았다.

def solution(A):
    tmp = {}
    for num in A:
        tmp[num] = 1
    return len(tmp)

이렇게 코드를 아주 살짝 딕셔너리로만 바꿔도 효율성 바로 통과 :)

 

출제 의도를 고려한 풀이

물론 위 방법으로도 통과가 되지만, 이 문제는 Sorting 단원의 예제 문제다. 즉 정렬을 활용해서 풀어보라는 의도로 출제된 문제인 것이다. 그렇다면, 배열을 정렬한 뒤 중복을 확인하는 방법은?

• 중복이 있다면, 그 앞 또는 뒤의 값이 현재값과 같음을 이용하면 된다
• 다만 비교를 하기 전에 문제의 조건을 잘 살펴서 빈 배열이 들어올수도 있음을 인지하고 코드를 짜면 된다

def solution(A):
    if len(A) == 0:
        return 0
    A.sort()
    cnt = 1 #두 번째 원소부터 비교할 것
    for i in range(1, len(A)):
        if A[i] != A[i-1]: #직전 값과 동일하지 않을 경우에만
            cnt += 1 #카운트하겠다
    return cnt