[Programmers, Lv.2] 코딩테스트 고득점 Kit - 해시 (2) (Python)

1. 전화번호 목록 (Level 2)

---

(문제 설명, 제한사항, 입출력 예)

전화번호부에 적힌 전화번호를 담은 배열 phone_book이 주어질 때,
어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를, 그렇지 않으면 true를 반환하라는 문제이다.

각 전화번호의 길이는 1 이상 20 이하이며, 같은 전화번호가 중복해서 들어있지는 않다고 한다.

 

(내가 생각한 풀이 과정)

phone_book 리스트에 담겨있는 전화번호를 하나씩 반복한다.
반복되는 요소와 바로 다음 요소를 비교할 건데, 접두어를 비교해야 하므로 해당 반복 요소 인덱스 i의 길이만큼 슬라이싱 후 비교한다.
만약, 두 글자가 같다면 접두어가 같다고 판단할 수 있다. -> False 반환
반복을 끝까지 해도 조건에 걸리지 않는다면, 같은 접두어가 없다고 판단할 수 있다. -> True 반환

반복하는 요소와 그 다음 요소를 직관적으로 비교하는 코드인 만큼, 반복을 돌리기 전에 phone_book 리스트를 정렬해줘야 하는 것이 문제의 핵심이다.

 

(코드)

💡 내 코드

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)-1):
        if phone_book[i] == phone_book[i+1][:len(phone_book[i])]:
            return False
    return True

 

---

2. 의상 (Level 2)

---

(문제 설명, 제한사항, 입출력 예)

의상들이 담긴 2차원 배열 clothes가 주어진다.
이 2차원 배열의 각 행은 "[의상의 이름, 의상의 종류]" 형태로 이루어져 있다고 할 때, (예, ["청바지", "하의"]) 서로 다른 옷의 조합의 수를 구하라는 문제이다.
세부 문제 조건은 아래와 같이 따른다.

• 각 종류별로 최대 1가지 의상만 착용할 수 있으며, 총 합해서 최소 한 개의 의상은 입어야 한다.
• 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용할 것으로 계산한다.
• 같은 이름을 가진 의상은 존재하지 않는다.

 

(내가 생각한 풀이 과정)

두 경우를 나눠서 풀었다. 
내가 원하는 형태로 꺼내쓰기 위해 딕셔너리를 만들어주는 파트 하나, 그리고 그 딕셔너리를 문제에서 요구하는 대로 꺼내는 파트 하나.

우선, 내가 원한 딕셔너리의 형태는 "옷 종류(Key): [종류에 속하는 옷 List] (Value)"이다.
그럼 딕셔너리의 길이와 옷 종류를 가지고 옷 조합을 쉽게 찾을 수 있을것이라 생각했다.
clothes 리스트를 하나씩 반복하면서, 인덱스 1에 해당하는 옷 종류는 Key로, 옷 이름은 Value로 넣어줬다.
이때, 옷 종류가 여러개 들어올 수 있기 때문에 처음 들어오는 옷 종류의 경우에는 처음부터 리스트를 만들어줬고, 이미 있는 경우에는 내부 리스트에 append를 하는 방식을 생각했다.

리스트가 만들어줬으면, 옷 종류가 한 개일 때와 한 개 이상일 때를 구분해서 최종 카운트를 구해준다.
옷 종류가 하나라면, 무조건 한 개씩 있는 경우밖에 존재할 수 없으니 첫 번째 인덱스의 길이가 최종 반환값이 된다.
하지만 옷 종류가 한 개 이상이라면, 하나씩 입는 경우와 안 입는 경우 두 가지가 모두 생길 수 있으니 기존 길이들을 모두 합하되, +1을 시킨 상태로 합해줘야 한다.
그리고 마지막에는 아무것도 안 입는 경우는 존재할 수 없기에 -1을 취해주면 알맞은 값을 반환할 수 있을 것이다.

 

(코드)

💡 문제 풀이 코드

def solution(clothes):
    hash_dict = {}
    answer = 1
    
    # 딕셔너리 값에 추가하기
    for cloth in clothes:
        if cloth[1] in hash_dict:
            hash_dict[cloth[1]].append(cloth[0])
        else:
            hash_dict[cloth[1]] = [cloth[0]]

    # 조합 찾기
    for dic in hash_dict:
        if len(hash_dict)==1:   # 조합 종류가 하나인 경우 -> 이 안에서 return
            return len(hash_dict[dic])
        else:                   # 조합 종류가 여러개인 경우
            answer *= len(hash_dict[dic])+1
    return answer-1             # 조합 종류가 여러개인 경우 -> 곱셈 연산 이후 값을 return