[코딩테스트 합격자 되기 7주차 과제] 집합 과제

사실 문제의 난이도는 쉬웠는데 집합의 find, union 을 경로압축과 Rank 기반 Union 으로 최적화하는 것을 구현하는데 너무 많은 시간을 쏟은것 같다.

---

✔️ 집합 find, union 구현

해당 문제는 특정원소가 속한 집합의 Root Node 를 찾는 find_v1 함수와 find_v1 함수를 이용하여 특정 집합을 다른 집합으로 합치는(Union) 역할을 수행하는 union_v1 함수를 구현하여 풀었다.

사실 답은 맞았지만 find_v1 함수는 경로압축으로 최적화할 수 있고, union_v1 함수는 Rank 기반 Union 으로 최적화할 수 있다고한다. 사실 일부구현하긴했지만.. 확실하지 않기 때문에 저자님한테 여쭤보아야 한다.

"""  
최적화 (전) 집합 find 와 union  
"""  

def find_v1(parents, target):  
    """ 경로 압축 사용 X """  
    parent = parents[target]  
    if parent == target:  
        return parent  
    return find_v1(parents, parent)  


def union_v1(parents, x, y):  
    """ Rank 기반 Union 사용 X """  
    root1 = find_v1(parents, x)  
    root2 = find_v1(parents, y)  
    parents[root1] = root2  
    return parents  


print("======== V1 ========")  
parents = [-1, 1, 2, 1, -1, 1, -1, 2, -1, 2]  
print(union_v1(parents, 5, 7))  
parents = [-1, 1, 1, 1, 2, 5, 5, 5]  
print(union_v1(parents, 4, 7))  
print()  

---

✔️ 폰켓몬

def solution(nums):  
    kinds = set(nums)  
    choice = len(nums) // 2  
    return min(choice, len(kinds))  

print(solution([3, 1, 2, 3]))  
print(solution([3, 3, 3, 2, 2, 4]))  
print(solution([3, 3, 3, 2, 2, 2])) 

---

✔️ 영어 끝말잇기

해당 문제는 딱히 손볼게 없었다. words 의 첫번쨰값을 previous_word 로 초기화함과 동시에, duplicate 라는 set 에 넣어준다음, 이후 words 의 두번째 값부터 순회를 돌면서 현재 단어의 첫번쨰 글자와 앞서 초기화한 previous_word 의 마지막단어가 일치하는지 비교하는 방법을 사용하였다.

def solution(k, words):  
    previous_word = words[0]  
    duplicate = {previous_word}  
    for idx, current_word in enumerate(words[1:], start=1):  
        if (current_word[0] != previous_word[-1]) or (current_word in duplicate):  
            return [(idx % k) + 1, (idx // k) + 1]  
        duplicate.add(current_word)  
        previous_word = current_word  
    return [0, 0]  

print(solution(3, ["tank", "kick", "know", "wheel", "land", "dream", "mother", "robot", "tank"]))  
print(solution(5, ["hello", "observe", "effect", "take", "either", "recognize", "encourage", "ensure", "establish", "hang", "gather", "refer", "reference", "estimate", "executive"]))  
print(solution(2, ["hello", "one", "even", "never", "now", "world", "draw"]))  

---

✔️ 전화번호 목록

📍 개선 전

set 를 사용하긴 했는데 입력크기가 20 만이라 위태위태하게 푼것같다. (근데 채점은 굉장히 빨리된듯?) 하여튼 전화번호들을 set 에 담아두고, 전화번호들을 순회하며 현재 전화번호의 각 숫자를 더해, set 에 존재하는지 체크하는 방법을 사용하였다.

def solution(phone_book):  
    answer = True  
    table = set(phone_book)  
    for phone in phone_book:  
        tmp = ''  
        for integer in phone:  
            tmp += integer  
            if tmp in table and tmp != phone:  
                answer = False  
                break  
    return answer  

print(solution(["119", "97674223", "1195524421"]))  
print(solution(["123","456","789"]))  
print(solution(["12","123","1235","567","88"]))  

📍 개선 후

Type 이 String 인 숫자를 sort 하면, 119, 1195524421 순으로 정렬되는것은 처음 알았다. 이건 기억해두면 굉장히 꿀팁일 것 같다.

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

print(solution(["119", "97674223", "1195524421"]))  
print(solution(["123","456","789"]))  
print(solution(["12","123","1235","567","88"]))  

---

✔️ 섬 연결하기

(... 이거 전에 풀어야한다고 써놓고 까먹었습니다. 풀고 채워두겠습니다.)