백준 11047번 바로가기 나의 풀이 import sys n, k = map(int, sys.stdin.readline().split()) coins = set() for _ in range(n): coins.add(int(sys.stdin.readline().rstrip())) count = 0 current = k for c in sorted(coins, reverse=True): if current == 0: break count += (current//(c:=int(c))) current = current%c print(count) CODE REVIEW k원을 만드는데 필요한 동전의 최소 갯수를 구하는 문제. 몫과 나머지를 다루는 문제를 풀어봤다면 쉽게 해결할 수 있었다. set은 sort()메소드를 직접 사용할 수 없기에, sorted()로 감싸고, parameter로 reverse=True를 넣어주면 쉽게 해결 가능하다.
백준 11399번 바로가기 나의 풀이 # 입력 import sys n = int(sys.stdin.readline().rstrip()) time = list(map(int,sys.stdin.readline().split())) atm = 0 # 처리 for i in range(n): atm += sorted(time)[i] * (len(time)-i) print(atm) CODE REVIEW 최선의 방법은 소요시간이 적은 사람부터 ATM을 사용하도록 하는 것이다. 최소 시간인 사람이 len(time)만큼 누적해서 걸리고, 그 다음부터는 -1번 씩 줄어나가며 시간이 걸린다.
백준 11723번 바로가기 첫 번째 풀이 s = set() for _ in range(int(input())): cmd = input().split() if len(cmd) == 1: if cmd == ['all']: s = set([i+1 for i in range(20)]) elif cmd == ['empty']: s = set() else: do=cmd[0] num=cmd[1] if do == 'add': s.add(num) elif do == 'remove': if num in s: s.discard(num) elif do == 'check': if num in s: print(1) else: print(0) elif do == 'toggle': if num in s: s.discard(num) else: s.add(num) 두 번째 풀이 import sys s = 0 for _ in range(int(sys.stdin.readline())): cmd = sys.stdin.readline().split() if cmd == ['all']: s = (1 << 20) - 1 elif cmd == ['empty']: s = 0 else: do=str(cmd[0]) num=int(cmd[1]) - 1 if do == 'add': s |= (1 << num) elif do == 'remove': s &= ~(1 << num) elif do == 'check': print(0 if s & (1 << num) == 0 else 1) elif do == 'toggle': s ^= (1 << num) CODE REVIEW 첫 번째 풀이에서는 set()을 이용하여 문제를 풀었는데, 시간초과 에러가 발생했다… 시간복잡도가 O(1)인 set도 이렇다니… 문제의 제목인 ‘집합’과 다르게 집합과 다른 걸 사용해야하나?? -> pypy3으로 제출해도 여전히 시간 초과… 에휴! 도저히 답을 못찾겠어서 구글링을 하다가 비트마스킹(bitmasking)기법에 대해 알게 되었다. 0과 1로 이루어진 이진법 숫자를 이용하여 위치와 숫자를 1:1대응해서 풀어내는 방식이었다. 두 번째 풀이에서는 시간을 줄이기 위해 input()대신 sys.stdin.readline()을 사용했고, bitmasking 이용해서 문제를 풀어내었다. bitmasking에 대한 자료는 아래 REFERENCE를 참조! 전에 HEAD FIRST JAVA 책을 읽다가 부록에서 OR XOR AND 비트 밀어내기에서 봤던 내용들인데 간만에 보니까 반가웠다. 다시 풀어보니 set()을 이용하는 경우에도 sys.stdin.readline()을 이용하면 시간 초과 없이 풀리긴 하더라…ㅂㅇㅂ REFERENCE 비트 마스킹 정리(python) 비트 마스킹 알고리즘(C++)
백준 11724번 바로가기 나의 풀이 from collections import deque import sys # 입력 n, m = map(int,sys.stdin.readline().split()) graph = dict() visited = [False] * (n+1) count = 0 for _ in range(m): u, v = map(int,sys.stdin.readline().split()) if u in graph: graph[u].append(v) else: graph[u] = [v] if v in graph: graph[v].append(u) else: graph[v] = [u] # 처리 def dfs(graph, queue): while queue: c = int(queue.pop()) if visited[c] == False: visited[c] = True if c in graph: queue += deque(graph[c]) for i in range(1, n+1): if visited[i] == False: dfs(graph, deque([i])) count += 1 print(count) CODE REVIEW dfs 또는 bfs를 이용해서 풀어낼 수 있는 문제. 시간을 단축시키기 위해 시간복잡도가 O(1)인 dict()로 graph를 저장했다. 다만, 이 경우 graph에서 요소를 뽑아올 때에 없는 index를 가져오려 하면 KeyError가 발생하므로 예외 처리를 해주어야 한다. 위 코드에서 if c in graph: 부분이 없다면, KeyError가 발생하는데 아마도 edge없이 홀로 남아있는 vertex의 경우 에러가 발생하는 듯 하다.
백준 1620번 바로가기 나의 풀이 import sys n, m = map(int, sys.stdin.readline().split()) dogam = {} dogam2 = {} for i in range(n): temp = sys.stdin.readline().rstrip() dogam[i+1] = temp dogam2[temp] = i+1 for _ in range(m): cur = sys.stdin.readline().rstrip() try: cur = int(cur) print(dogam[cur]) except: name = str(cur) print(dogam2[name]) CODE REVIEW hash를 이용한 자료 구조 문제. (이름-숫자) (숫자-이름) 모두 구할 수 있어야하므로 dogam을 두 개 생성하는게 편리하다.