[programmers] 폰켓몬, 전화번호 목록

💡 오늘의 학습 키워드
- 폰켓몬
- 전화번호 목록

 

🥉 폰켓몬

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/1845?language=python3

 

문제 설명

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다.
홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다.
따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다.
예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면
이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다.
이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의
폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다.
따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을
포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때,
N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아,
그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

제한 사항
1. nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
2. nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
3. 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
4. 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬
종류 개수의 최댓값 하나만 return 하면 됩니다.

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

문제가 길지만 결국 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾는 문제입니다.
단, 여기에 붙은 조건이 N/2마리를 선택해야 한다는 점이고 전체적인 문제 해결 과정은 다음과 같습니다.

1. set 집합을 사용하여 중복이 허용되지 않는 값을 선언합니다.
2. 주어진 폰켓몬 리스트를 순회합니다.
3. set 집합에 해당 폰켓몬을 추가합니다. 같은 종류의 폰켓몬이라면 들어갈 수 없습니다. 
4. N/2 마리에 도달한다면 해당 반복문을 나오게 됩니다.
5. set 집합의 원소 길이를 리턴합니다.

정석적인 풀이 순서에서 조금 더 간결하게 풀이하자면, 최대 횟수는 N/2 번이라는 제한 조건이 있으니
해당 N/2 값과 중복을 제거한 set 원소의 개수 중 최소값을 구하여 리턴할 수도 있습니다.

💡 내가 해결한 방식은?

def solution_1(nums):
    max_pick = len(nums) / 2
    pick_list = set()
    
    for num in nums:
        if len(pick_list) == max_pick:
            break
        pick_list.add(num)

    return len(pick_list)

def solution_2(nums):
    return min(len(nums)/2, len(set(nums)))

 

---

🥈 전화번호 목록

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42577?language=python3

 

문제 설명

전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다.
전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다.

구조대 : 119
박준영 : 97 674 223
지영석 : 11 9552 4421

전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때,
어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록
solution 함수를 작성해주세요.

제한사항
1. phone_book의 길이는 1 이상 1,000,000 이하입니다.
2. 각 전화번호의 길이는 1 이상 20 이하입니다.
3. 같은 전화번호가 중복해서 들어있지 않습니다.

 

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

이 문제는 문제 흐름 그대로 풀었을 때 효율성 테스트를 통과하지 못하는 문제가 있었습니다.
여기서 문제에서 사용하길 원하는 자료구조가 존재하는 것을 알 수 있어야 합니다. 문제 해결 과정은 다음과 같습니다.

1. 전화번호 리스트를 순회합니다.
2. 번호 비교를 통해 비교 대상 번호에 해당 번호가 접두어로 포함되는지 확인합니다.
3. 접두어에 들어갈 경우 false를 반환하고 아닐 경우 반복문 이후 True를 리턴합니다.

 

가장 먼저 단순 반복문으로 구현해본 후 시간 초과가 발생하는 것을 확인하고 자료구조를 적용해보았습니다.
해시맵을 사용하게 되면 딕셔너리를 통해 Key-Value 형태로 저장하게 되는데, 삽입 시 O(1) 시간복잡도를 가집니다.

 

단 해시를 얻어내는 과정에서 서로 다른 Key 값이 같은 Hash로 변환되는 해시 충돌을 고려해야 합니다.
파이썬의 딕셔너리에서는 체이닝을 사용합니다. 체이닝은 각 버킷에 연결리스트를 사용하여
충돌된 키들을 저장합니다. 따라서 성능 저하를 최소화하고 효율적으로 키-값 쌍을 관리할 수 있습니다. 

 

이러한 해시 맵의 기본 특성인 빠른 조회와 빠른 삽입을 통해 접두어 관계를 효율적으로 확인할 수 있었습니다.

💡 내가 해결한 방식은?

효율성 테스트 (시간 초과)

def solution(phone_book):
    for i in range(len(pb)):
        for j in range(len(pb)):
            # 전화 번호가 동일 인덱스일 경우 continue
            if pb[i] == pb[j]:      
                continue
            # j 인덱스 값 안에 i 인덱스 값이 존재할 경우
            elif pb[i] in pb[j]:
                pb_length = len(pb[i])
                # 접두사 일 경우
                if pb[i] == pb[j][0:pb_length] :
                    return False
    
    return True

Hash 를 사용한 풀이

def solution(phone_book):
    hash_map = {}
    for p_num in phone_book:
    	hash_map[p_num] = 1
        
    for p_num in phone_book:
    	arr = ""
        for num in p_num:
            arr += num
            if arr in hash_map and arr != num:
            	return False
                
    return True

startswitch 를 사용한 풀이

def solution(phone_book):
    phone_book.sort()
    for p1, p2 in zip(phone_book, phone_book[1:]):
    	if p2.startswitch(p1):
        	return False
          
    return True

 

---

✍️  TIL

파이썬에서 해시는 딕셔너리를 통해 구현하는데 접두어 확인 과정에서 해시 자료구조가 가장 간단하면서
효율적이라는 것을 알았다. 문제를 푸는데 숏코딩하는 재미도 있지만 문제 풀이 흐름을 논리적으로 풀어내고
그 로직에 맞게 코드를 반복문과 조건문을 통해 풀어나가는게 먼저라는 것을 잊지 말아야겠다.
앞으로 숏코딩보다 빠르고 단순하게 구현한 후 시간복잡도나 효율성 문제가 발생했을 때 해결할 수 있는 자료구조를 
떠올리고 수정하는 순서로 문제 풀이를 진행할 것이다. 확실히 문제를 많이 푸는 것보다 중요한 게 있는 것 같다.