[Python / 프로그래머스] KAKAO 불량사용자 문제풀이

[Python / 프로그래머스] KAKAO 불량사용자 문제풀이 입니다. 이 글에는 정답 코드가 포함 되어 있습니다.

해당 문제는 프로그래머스에서 풀어볼 수 있기에 문제 설명은 생략하겠습니다.

문제 해결 방법

문제는 꽤나 직관적으로 풀이가 가능할 것으로 보였습니다. 불량사용자로 판단되는 가려진 아이디와 유저들의 아이디를 매칭시키고 경우의 수를 구해보면 풀이가 가능할 것 같았습니다.

시간복잡도

사실상 시간복잡도가 관건이었는데, 모든 유저가 불량유저아이디에 포함가능할 경우 발생하는 최악의 경우의 수는
8^8 = 16,777,216(유저수: 8, 불량유저아이디: 8) 이다.

8개 주머니에서 구슬 하나씩 꺼내서 경우의 수를 따져보는 경우와 같다 (각 주머니엔 구슬이 8개씩 들어있음)

사실 여기까지만 해도 1600만번의 연산량은 파이썬에서 1초내외로 연산이 가능한 수치이므로 10초가 주어지는 프로그래머스 특성상 시간초과가 발생하지 않는다.

하지만..

내가 간과한 사실이 하나있었다. 바로 불량 유저로 판단되는 아이디를 하나씩 꺼내봤을때 중복이 되는 케이스를 확인하는 과정이다. 이 때의 연산량이 리스트의 길이로 최대 8번의 연산이 곱해진다.

따라서 최종적인 시간복잡도는 O(8 * 8^8) = 134,217,728 번의 연산량이 구해진다.

약 7초정도 걸리는 셈인데, 부가적인 계산 코드들과 정확히 시간 계산을 할 수 없기에 이정도면 충분히 오버될 수도 있다고 생각한다.

따라서 combination 을 돌릴때 유저아이디가 내가 고른 유저리스트 안에 들어있다면 해당 구슬은 건너 뛰는 코드를 추가하였다.

이로서 최대 시간복잡도는 O(8*8!) + O(8^8) = 322,560 + 16,777,216 번 (약 1초)으로 통과가 가능해진다.

combination

문제 풀이에 앞서 python 에서 hashable type case 를 아래에서 공부한 내용을 작성 하였습니다.

문제 자체는 (1) combination 를 구축할 데이터를 전처리하는 과정 / (2) combination 을 구현 하는 과정

(1) + (2) 의 구현으로 처리된다.

이 과정에서 나는 중복값 처리를 위해서 set 을 사용하였는데, python 의 경우 set(집합) 객체 내부에는 hashable type 만 처리가 가능하다. 간단히 이해를 돕기위해 다음과 같이 unhashable type 은 set(집합) 객체 안에 넣을 수 없다. 정도로만 이해하고 넘어가겠습니다.

## example
a = set()
a.add({1,2,3})

# TypeError: unhashable type: 'set'

a = set()
a.add([1,2,3])

# TypeError: unhashable type: 'list'

그렇기에 문제를 풀며 combination 으로 나온 결과값 자체들을 다시 한번 중복 제거해야하는 필요성이 있었는데, 이 때 unhashable type 인 frozenset 을 이용해 set에 넣어주어 처리하였다.

문제 풀이

문제 풀이 자체는 문제 해결 방식에서 언급한대로 (1) combination 를 구축할 데이터를 전처리하는 과정 / (2) combination 을 구현 하는 과정으로 진행하였다.

(1) combination 를 구축할 데이터를 전처리하는 과정

    n = len(banned_id)
    ban_list = [[] for _ in range(n)]

    for i in range(n):
        for user in user_id:
            # 길이 체크
            if len(banned_id[i]) == len(user):
                # 알파벳 체크
                for j in range(len(user)):
                    if banned_id[i][j] == "*" or banned_id[i][j] == user[j]:
                        pass
                    else:
                        break
                else:
                    ban_list[i].append(user)
                    
# ban_list : [['frodo', 'crodo'], ['frodo', 'crodo'], ['abc123', 'frodoc']]

위 과정처럼 combination 에 넣기 위해 ban_list 를 만드는 과정부터 시작하였다.

(2) combination 을 구현 하는 과정으로 진행하였다.

def comb(lst, s):
    global n, temp, answer
    
    if len(temp) == n:
        val = frozenset(temp[:])
        if len(val) == n:
            answer.add(val)
        return
    
    for i in range(s, len(lst)):
        for j in range(len(lst[i])):
            if lst[i][j] not in temp:
                temp.append(lst[i][j])
                comb(lst, i+1)
                temp.pop()

각각의 ban_list 안에 리스트들은 하나의 주머니로 생각하고 주머니에서 하나씩 꺼내며 경우의수를 계산하되, 중복되는 값은 카운트하지 않는 방식을 채택하였다.

1. 첫 번째 리스트에서 'frodo'를 뽑고 두 번째 리스트에서 'frodo'를 또 뽑으면 카운트 자체가 되지 않는다.
2. 첫 번째 리스트에서 'frodo'를 뽑고 두 번째 리스트에서 'crodo'를 뽑았을 경우를 frozenset 으로 만들어 set 함수에 저장하였기에, 첫 번째 리스트에서 'crodo'를 뽑고 두 번째 리스트에서 'frodo'를 뽑았을 경우는 자동으로 set 내부 규칙에 의거해 중복값 제거가 된다.

이렇게 모든 경우의 수를 탐색하되 중복값은 카운트 하지 않는 방식으로 처리하였다.

최종 코드

def comb(lst, s):
    global n, temp, answer
    
    if len(temp) == n:
        val = frozenset(temp[:])
        if len(val) == n:
            answer.add(val)
        return
    
    for i in range(s, len(lst)):
        for j in range(len(lst[i])):
            if lst[i][j] not in temp:
                temp.append(lst[i][j])
                comb(lst, i+1)
                temp.pop()
    

def solution(user_id, banned_id):
    global n, temp, answer
    
    answer = set()
    n = len(banned_id)
    ban_list = [[] for _ in range(n)]
    
    for i in range(n):
        for user in user_id:
            # 길이 체크
            if len(banned_id[i]) == len(user):
                # 알파벳 체크
                for j in range(len(user)):
                    if banned_id[i][j] == "*" or banned_id[i][j] == user[j]:
                        pass
                    else:
                        break
                else:
                    ban_list[i].append(user)

    temp = []
    comb(ban_list, 0)
    
    return len(answer)

새로 배운 내용 & 느낀점

Python : hashable type

① Hashing은 hash table이라는 자료구조를 이용해서 요소들을 빠르게 찾을 수 있게 하는 방법이다.

Hash table은 모든 요소들에 대해서 key를 가진다.
이 key를 통해서 요소들을 찾는데 constant time (O(1)) (= 시간 복잡도 상수 시간)을 가져
요소들의 개수와 상관 없이 원하는 값을 빠르게 찾아낼 수 있다.

그렇다면 hashable하다는 것의 의미는 무엇일까?
Hashable은 객체가 만들어진 이후에 hash table의 value가 바뀌지 않음을 의미한다.

② Mutability는 이 변수가 바뀔 수 있는지 없는지에 대한 개념이다.

파이썬의 자료형에서는
Immutable type: Tuple, int, String, Frozenset
Mutable type: List, Dictionary, Set

Frozenset 의 경우 값이 변경되지 않는다는 전제로 만들어진 set 함수로 Tuple-List 관계의 set 버전이라고 생각하면 쉽다.

③ Hashable과 Mutability의 관계

Hash key로 사용되는 객체는 immutable해야 한다는 점에서 이 두가지 개념은 연관이 있다.
→ hash value가 바뀌면 안되기 때문에
unhashable type 오류는 mutable한 객체를 hash key로 사용하려고 할때 발생한다.
파이썬에서 set은 immutable한 객체만을 가질 수 있다.

>>> sample_set = set()
>>> sample_set.add('A')
>>> sample_set
# {'A'}
>>> sample_set.add(['B', 'C'])
# TypeError: unhashabletype: 'list'

하지만 두 개념이 완전히 같지 않기 때문에, immutable하지만 hashable하지 않은 객체도 있다.
예를 들어, mutable한 객체(예를 들어, 리스트)를 갖고 있는 tuple이 있다.

# Immutable and hashable
my_tuple_1 = (1,2,3)
print(type(my_tuple_1))
print(hash(my_tuple_1))
# <class 'tuple'>
# -378539185

# Immutable but not hashable
my_tuple_2 = (1,2,3, [1,2])
print(type(my_tuple_2))
print(hash(my_tuple_2))
# <class 'tuple'>
# TypeError: unhashable type: 'list'

a = (1, 2, [1,2,3])
a[2].append(4)
print(a)
# (1, 2, [1, 2, 3, 4])
# Immutable 안에 Mutable 이어도 List 내부적으로는 Mutable 타입이기에 값 변화가 가능하다.

→ tuple(Immutable)이 리스트(Mutable)를 요소로 가지고 있기 때문에 unhashable type 으로 분류된다.

느낀점

아직도 python 언어 특성에 대해서 모르는게 많다는 걸 깨달았고, 더 깊이 deep dive 할 수 있도록 더욱 공부해야겠다고 느껴졌다.

출처 : https://jiwonkoh.tistory.com/40
출처 : https://medium.com/@himankbh/hashable-vs-immutable-objects-in-python-23382560ba0f