9372_상근이의 여행 (Python)

0. 출처

• 유형 : 트리 (silver 3)
• 링크 : 9372_번: 상근이의 여행

1. 기록

• 22/04/18 (월)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
2 (테스트 케이스 수)
3 3 (국가의 수 / 비행기의 종류)
1 2
2 3
1 3
5 4 (국가의 수 / 비행기의 종류)
2 1
2 3
4 3
4 5

- 예제 출력 1 -
2
4

(3) 코드

sample

(4) 정리

문제를 잘 못읽어 예제입력 예제출력이 왜 저렇게되나 한참봤다..
왜 예제출력 결과가 2개나 나오는지 때문에.. (맨 처음에 주어진게 테스트 케이스였음)
문제를 잘 읽자

또한 모든 국가가 연결되어있기 때문에 모든 국가를 방문하려면 국가의 갯수 - 1 이 정답이다.

(5) 참고

참고 풀이

9934_완전 이진 트리 (Python)

0. 출처

• 유형 : 트리 (silver 1)
• 링크 : 9934번: 완전 이진 트리

1. 기록

• 22/04/18 (월)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 문제에서 주어진 방문순서는 중위 순회이다.
>> 레벨과 방문순서가 주어진다.
>> 주어진 것으로 트리의 정보를 구해야 한다.
>> 어떻게 구하지..?

>> 중위순회를 반대로 실행해야 한다.
>> level 활용하기
>> 중위순회 입력된 리스트 가운데가 항상 root 노드임을 활용하기
>> 중위 순회로 입력된 리스트를 왼쪽 부분 트리, 오른쪽 부분 트리로 쪼갤 줄 알아야한다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
2
2 1 3

- 예제 출력 1 -
1
2 3

- 예제 입력 2 -
3
1 6 4 3 5 2 7

- 예제 출력 2 -
3
6 2
1 4 5 7

(3) 코드

k = int(input())
inorder = list(map(int, input().split()))

answer = [[] for _ in range(k)]

def dfs(inorder, depth):

    # 트리의 root index를 찾아낸다.
    mid = (len(inorder) // 2)

    # 해당 깊이에 해당하는 node를 추가한다.
    answer[depth].append(inorder[mid])

    if len(inorder) == 1:
        return

    dfs(inorder[:mid], depth+1)
    dfs(inorder[mid+1:], depth+1)

dfs(inorder, 0)

for i in answer:
    print(*i)

(4) 정리

(5) 참고

참고 풀이

9934_[문제이름] (Python)

0. 출처

• 유형 : 트리 (silver 1)
• 링크 : 9934_번: 완전 이진 트리

1. 기록

• 22/04/18 (월)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 문제에서 주어진 방문순서는 중위 순회이다.
>> 레벨과 방문순서가 주어진다.
>> 주어진 것으로 트리의 정보를 구해야 한다.
>> 어떻게 구하지..?

>> 중위순회를 반대로 실행해야 한다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
2
2 1 3

- 예제 출력 1 -
1
2 3

- 예제 입력 2 -
3
1 6 4 3 5 2 7

- 예제 출력 2 -
3
6 2
1 4 5 7

(3) 코드

sample

(4) 정리

(5) 참고

참고 풀이

1991_트리 순회 (Python)

0. 출처

• 유형 : 트리 (silver 2)
• 링크 : 1991번: 트리 순회

1. 기록

• 22/04/18 (월)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 각 노드, 왼쪽 노드, 오른쪽 노드가 주어졌을 때
>> 어떻게 tree 에 저장할 것인지?
>> set() 형태로 저장해보자.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

- 예제 출력 1 -
ABDCEFG
DBAECFG
DBEGFCA

(3) 코드

n = int(input())

tree = {}

for _ in range(n):
    node, left, right = map(str, input().split())
    tree[node] = [left, right]

def preorder(root):              # 전위순회
    if root != '.':
        print(root, end='')      # root
        preorder(tree[root][0])  # left
        preorder(tree[root][1])  # right

def inorder(root):               # 중위순회
    if root != '.':
        inorder(tree[root][0])   # left
        print(root, end='')      # root
        inorder(tree[root][1])   # right

def postorder(root):             # 후위순회
    if root != '.':
        postorder(tree[root][0]) # left
        postorder(tree[root][1]) # right
        print(root, end='')      # root

preorder('A')
print()        # 줄바꿈 용도
inorder('A')
print()        # 줄바꿈 용도
postorder('A')

(4) 정리

재귀를 잘 이해해야 이해할 수 있는 풀이이다.

전위 순회, 중위 순회, 후위 순회 개념이 코드에 그대로 적용된 풀이이다.

(5) 참고

참고 풀이

[문제번호]_[문제이름] (Python)

0. 출처

• 유형 : 트리 (silver 2)
• 링크 : 11725번: 트리의 부모 찾기

1. 기록

• 22/04/18 (월)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>> 루트노드가 1인 정보가 주어져있다.
>> 그 외의 나머지는 연결관계만 주어져있다.
>> 이 경우 부모노드를 어떻게 파악하면 좋을까?
>> 우선 연결관계부터 만들어보자.

2. 시간복잡도
>>

3. 자료구조

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
7
1 6
6 3
3 5
4 1
2 4
4 7

- 예제 출력 1 -
4
6
1
3
1
4

- 예제 입력 2 -
12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

- 예제 출력 2 -
1
1
2
3
3
4
4
5
5
6
6

(3) 코드

import sys

sys.setrecursionlimit(10**9)

n = int(input())

# 트리
tree = [[] for _ in range(n+1)]

# 부모 노드 저장
relation = [0 for _ in range(n+1)]

for _ in range(n-1):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

def dfs(start, tree, relation):
    # 연결된 노드들부터 relation[i] 의 부모가 없으면 부모 설정해주고 dfs를 돌린다.
    for node in tree[start]:
        if relation[node] == 0:
            # node에게 너 여기서 출발했다고 표시해주는 느낌
            relation[node] = start
            dfs(node, tree, relation)

dfs(1, tree, relation)

for i in range(2, n+1):
    print(relation[i])

(4) 정리

(5) 참고

참고 풀이

모의고사 (Python)

0. 출처

• 유형 : 완전탐색 (lv 1)
• 링크 : 모의고사

1. 기록

• 22/04/14 (목)

2. 풀이

(1) 아이디어

1. 아이디어
>> 1번 수포자 [1, 2, 3, 4, 5] 반복                    -> 5로 나눈 나머지
>> 2번 수포자 [2, 1, 2, 3, 2, 4, 2, 5] 반복           -> 8로 나눈 나머지
>> 3번 수포자 [3, 3, 1, 1, 2, 2, 4, 4, 5, 5] 반복    -> 10으로 나눈 나머지

2. 시간복잡도
>>

3. 자료구조
>>

(2) 코드

def solution(answers):
    person1 = [1, 2, 3, 4, 5]
    person2 = [2, 1, 2, 3, 2, 4, 2, 5]
    person3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]

    answer_list = {'1':0, '2':0, '3':0}

    for i in range(len(answers)):
        if answers[i] == person1[i%5]:
            answer_list['1'] += 1
        if answers[i] == person2[i%8]:
            answer_list['2'] += 1
        if answers[i] == person3[i%10]:
            answer_list['3'] += 1

    max_value = max(answer_list.values())
    winner = []

    for key, value in answer_list.items():
        if max_value == value:
            winner.append(int(key))
    return winner

(3) 정리

일부러 dict 자료형을 써서 해결하려했고 unpacking 할 때 items() 함수를 써야하는 걸 정확히 알고 있지 않아서 에러가 계속생겼다.
하는 방법을 정확히 익혀두자!

(4) 참고

베스트앨범 (Python)

0. 출처

• 유형 : 해시 (lv 3)
• 링크 : 베스트앨범

1. 기록

• 22/04/14 (목)

2. 풀이

(1) 아이디어

sample

(2) 코드

sample

(3) 정리

(4) 참고

위장 (Python)

0. 출처

• 유형 : 해시 (lv 2)
• 링크 : 위장

1. 기록

• 22/04/13 (수)

2. 풀이

(1) 아이디어

1. 아이디어
>>
2. 시간복잡도
>>
3. 자료구조
>>

(2) 코드

def solution(clothes):
    # 1. 옷을 종류별로 구분하기
    hash_map = {}
    for clothe, type in clothes:
        hash_map[type] = hash_map.get(type, 0) + 1

    # 2. 입지 않는 경우를 추가하여 모든 조합 계산하기
    answer = 1
    for type in hash_map:
        answer *= (hash_map[type] + 1)

    # 3. 아무종류의 옷도 입지 않는 경우 제외하기
    return answer - 1

(3) 정리

처음에 {type : [옷1, 옷2, 옷3]} 등으로 만들어야 하나 고민했으나
문제에서는 조건에 맞는 결과 값만 원하기 때문에 그럴 필요가 없음을 알게되었습니다.

위 코드처럼 list의 값 여러개를 여러변수에 동시에 할당하는 것을 unpacking이라 하는데 유용하게 쓸 수 있도록 연습해야할 것 같습니다.
또한 get() 함수 사용법 또한 익혀놔야겠습니다.

(4) 참고

참고 자료

[문제이름] (Python)

0. 출처

• 유형 : 해시 (lv 2)
• 링크 : 전화번호 목록

1. 기록

• 22/04/13 (수)

2. 풀이

(1) 아이디어

1. 아이디어
>> 반복문 돌면서 기준이되는 폰넘버를 다른 폰넘버가 앞자리부터 가지고 있는지 확인해본다.
>> slicing 활용!

2. 시간복잡도
>>

3. 자료구조
>>

(2) 코드

# 효율성 테스트 3,4 실패

def solution(phone_book):
    phone_book.sort()
    for num in range(0, len(phone_book)):
        for target in range(num+1, len(phone_book)):
            target_num = phone_book[target]
            if phone_book[num] == target_num[0:len(phone_book[num])]:
                return False
    return True

# startswith() 를 활용하면 이중for문없이 해결할 수 있다.

def solution(phone_book):
    phone_book.sort()

    for num in range(0, len(phone_book)-1):
        if phone_book[num+1].startswith(phone_book[num]):
            return False
    return True

# startswith() 와 zip() 을 활용한 풀이

def solution(phoneBook):
    phoneBook.sort()

    print(phoneBook)
    print(phoneBook[1:])
    print(list(zip(phoneBook, phoneBook[1:])))

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

(3) 정리

(4) 참고

효율성 참고1
효율성 참고2
참고 풀이

완주하지 못한 선수 (Python)

0. 출처

• 유형 : 해시 (lv 1)
• 링크 : 완주하지 못한 선수

1. 기록

• 22/04/13 (수)

2. 풀이

(1) 아이디어

1. 아이디어
>> 정렬 후 비교해서
>> 다른 경우가 생기는 경우를 return 한다.

2. 시간복잡도
>>

3. 자료구조
>>

(2) 코드

# 풀이1 : 리스트 정렬

def solution(participant, completion):
    p = sorted(participant)
    c = sorted(completion)

    for i in range(0, len(completion)):
        if p[i] != c[i]:
            return p[i]

    return p[-1]

# 풀이2 : hash 이용

def solution(participant, completion):
    hashDict = {}
    sumHash = 0
    # 1. Hash : Participant의 dictionary 만들기
    # 2. Participant의 sum(hash) 구하기
    for part in participant:
        hashDict[hash(part)] = part
        print(hashDict)
        sumHash += hash(part)

    # 3. completion의 sum(hash) 빼기
    for comp in completion:
        sumHash -= hash(comp)

    # 4. 남은 값이 완주하지 못한 선수의 hash 값이 된다
    return hashDict[sumHash]

# 풀이3 : counter 이용

import collections

def solution(participant, completion):
    # 1. participant의 Counter를 구한다
    # 2. completion의 Counter를 구한다
    # 3. 둘의 차를 구하면 정답만 남아있는 counter를 반환한다
    answer = collections.Counter(participant) - collections.Counter(completion)

    # 4. counter의 key값을 반환한다
    return list(answer.keys())[0]

(3) 정리

(4) 참고

참고 풀이
참고 영상