""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/136797 """ # 풀이 과정 # 목표: 최소한의 시간으로 타이핑을 하는 경우의 가중치 # 이동하지 않고 제자리 누르기:1 상하좌우 이동 후 누르기:2 대각선:3 # 왼손 오른손 중 가중치가 제일 적은 경우의 수들의 합 # 같은 번호에 두 손가락 놓는거 불가 # 상하좌우 두 번 가는것보다 대각선 한 번이 더 이득 # 최솟값+최솟값 = 최솟값 명제는 항상 성립 # 번호판을 dp로 생각 후 마지막 번호의 dp값이 가중치 최솟값으로 생각접근해보기 # 다시 정리하는 dic.items(): key,value 둘다 # dic.keys(): key 값 # dic.values(): values 모두 키값에 관계없이 모두 from collections import deque # 왼손 가중치 계산 def left_hand(new_x, new_y): l = 0 while True: if new_x > 0 and new_y > 0: l += 3 new_x -= 1 new_y -= 1 elif new_x > 0 and new_y == 0: l += 2 new_x -= 1 elif new_x == 0 and new_y > 0: l += 2 new_y -= 1 elif new_x == 0 and new_y == 0: l += 1 break if new_x == 0 and new_y == 0: break return l # 오른손 가중치 계산 def right_hand(new_x, new_y): r = 0 while True: if new_x > 0 and new_y > 0: r += 3 new_x -= 1 new_y -= 1 elif new_x > 0 and new_y == 0: r += 2 new_x -= 1 elif new_x == 0 and new_y > 0: r += 2 new_y -= 1 elif new_x == 0 and new_y == 0: r += 1 break if new_x == 0 and new_y == 0: break return r # 숫자 위치 def point(k, i): # i의 번호 찾기 for a in range(4): for b in range(3): if k[a][b] == i: x = a y = b break return x, y from collections import deque def solution(numbers): k = [["1", "2", "3"], ["4", "5", "6"], ["7", "8", "9"], ["*", "0", "#"]] num = list("123456789*0#") n = list(numbers) last = n[-1] # 이전 가중치 # 이전에 해당번호에 도달했을때 가중치가 가장 적은 경우를 저장한 후 after의 최솟값으로 재갱신 # before={"1":0, "2":0,"3":0,"4":0,"5":0,"6":0,"7":0,"8":0,"9":0,"*":0,"#":7} # m 각 그래프 위치에 따른 가중치 m = [[0] * 12 for _ in range(12)] # i>j for i in range(12): x, y = point(k, num[i]) for j in range(12): dx, dy = point(k, num[j]) new_x = abs(x - dx) new_y = abs(y - dy) m[i][j] = right_hand(new_x, new_y) w = 0 left = "4" right = "6" # 현재 들어있는 손 가중치 now = {} hand = (left, right) now[hand] = w # p: numbers num:위치 인덱스 담은 배열 for c in n: after = {} # 다음 손 가중치 c_num = num.index(c) # c: 누를 번호 # h:손 n_w:손 가중치 (이전 손 위치로부터 온 가중치) # 이전 위치에서 온 가중치들을 저장함과 동시에 도착할 위치중 중복 위치시 최솟값으로 매 번 갱신 그 뿐만 아니라 # 중복된 위치는 dic으로 제거하기에 최대 갯수는 12**2로 유지된다 그 이상으로 늘어나지 않는다 for h, n_w in now.items(): l, r = h # 왼손, 오른손 l_num = num.index(l) r_num = num.index(r) if r == c: if not (l, c) in after.keys() or now[(l, c)] > n_w + 1: # 이해 과정: or 뒤의 두 번째 조건은 최소값일 경우 재갱신을 위해서이다! after[(l, c)] = n_w + 1 elif l == c: if not (c, r) in after.keys() or now[(c, r)] > n_w + 1: after[(c, r)] = n_w + 1 else: if not (l, c) in after.keys() or after[(l, c)] > n_w + m[r_num][c_num]: after[(l, c)] = n_w + m[r_num][c_num] if not (c, r) in after.keys() or after[(c, r)] > n_w + m[l_num][c_num]: after[(c, r)] = n_w + m[l_num][c_num] now = after return min(list(now.values()))

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/86971 """ # 풀이 과정 # 네트워크 2개로 분활 (나누어진 송전탑 개수 거의 비슷하게!) # 목표 나누어진 송전탑들의 차이를 return from collections import deque def bfs(graph, d): visited = [] queue = deque([d]) while queue: n = queue.popleft() if n not in visited: visited.append(n) queue += graph[n] return visited def solution(n, wires): # 탑의 개수 top = [(a + 1) for a in range(n)] result = n - 2 # 송전탑 개수 차이 최대(한 쪽 n-1, 한 쪽 1) for b in range(len(wires)): k = wires.copy() k.pop(b) # 간선을 하나씩 제거 graph = {} for c, d in k: if c not in graph: graph[c] = [d] else: graph[c] += [d] if d not in graph: graph[d] = [c] else: graph[d] += [c] check = bfs(graph, d) num = abs(n - len(check) - len(check)) if num < result: result = num return result

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/12987 """ # 풀이 과정 """ permutations > 시간초과 A의 가장 작은값 순으로 나열시 B가 이기는 경우가 최대이다 A의 큰 값에 한해선 져주는게 이득이다(승을 가장 많이 챙기기 위해) A의 순서는 함정이다 어짜피 B는 그에 맞춰 대응할 수 있어 의미가 없다 그러므로 A의 순서는 자유롭게 바꾸고 그에 맞춰 최대 승수만 구하면 된다! """ from collections import deque def solution(A, B): A.sort() B.sort() A = deque(A) B = deque(B) result = 0 while A: a = A.popleft() while B: b = B.popleft() if b > a: result += 1 break if len(B) == 0: break return result

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/70129 """ # 풀이 과정 def solution(s): count = 0 count_0 = 0 while True: count += 1 count_0 += s.count("0") s = s.replace("0", "") s = len(s) s = str(bin(s))[2:] if s == "1": return [count, count_0] return 0

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/49191 """ # 풀이 과정 from collections import defaultdict from collections import deque def solution(n, results): rank_win = defaultdict(set) rank_lose = defaultdict(set) for win, lose in results: rank_win[win].add(lose) rank_lose[lose].add(win) # 이긴 플레이 경로 재구성 for player in range(1, n + 1): visit = [False] * (n + 1) visit[0] = True visit[player] = True q = deque([player]) while q: opponent = q.popleft() visit[opponent] = True for i in rank_win[opponent]: if visit[i] == False: q.append(i) rank_win[player].add(i) # 진 플레이들 재구성 for player in range(1, n + 1): visit = [False] * (n + 1) visit[0] = True visit[player] = True q = deque([player]) while q: opponent = q.popleft() visit[opponent] = True for i in rank_lose[opponent]: if visit[i] == False: q.append(i) rank_lose[player].add(i) # 결과를 알 수 있는 플레이를 검색 answer = 0 for player in range(1, n + 1): if len(rank_win[player] | rank_lose[player]) == n - 1: answer += 1 return answer

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/150368 """ # 풀이 과정 discounts = [10, 20, 30, 40] answer = [-1, -1] def solution(users, emoticons): n, m = len(users), len(emoticons) discount_list = [0] * m def search(idx): global answer if idx == m: sale_num, cost_num = 0, 0 for i in range(n): tmp = 0 for j in range(m): if users[i][0] <= discount_list[j]: tmp += emoticons[j] * (100 - discount_list[j]) // 100 if tmp >= users[i][1]: sale_num += 1 else: cost_num += tmp if sale_num > answer[0] or sale_num == answer[0] and cost_num > answer[1]: answer = [sale_num, cost_num] return for i in range(4): discount_list[idx] = discounts[i] search(idx + 1) search(0) return answer

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/250134 """ # 풀이 과정 from collections import deque # bfs # 두 수레를 동시에 사방위로 이동시킨 후의 위치를 조합하여 그 위치를 동시에 다시 bfs를 실행하여 최솟값을 구하기 def solution(maze): m = len(maze) # 세로 n = len(maze[0]) # 가로 v_r = [[False for _ in range(n)] for _ in range(m)] v_b = [[False for _ in range(n)] for _ in range(m)] dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] result = 0 # 장애물 및 현 위치 및 도착지점 확인 for i in range(m): for j in range(n): if maze[i][j] == 5: v_r[i][j] = True v_b[i][j] = True elif maze[i][j] == 1: r_s = [i, j] v_r[i][j] = True elif maze[i][j] == 2: b_s = [i, j] v_b[i][j] = True q = deque([[[r_s, [r_s]], [b_s, [b_s]]]]) new = [] # q가 끝났을 때 더해줄 큐 count = 0 while q: r, b = q.popleft() # r[1]: 각각의 red가 지나온 길 b[1]: 각각의 blue가 지나온 길 new_r = [] new_b = [] if maze[r[0][0]][r[0][1]] == 3: new_r = [r[0]] if maze[b[0][0]][b[0][1]] == 4: new_b = [b[0]] r_x, r_y = r[0][0], r[0][1] b_x, b_y = b[0][0], b[0][1] if maze[r_x][r_y] == 3 and maze[b_x][b_y] == 4: return result for x, y in zip(dx, dy): if 0 <= r_x + x < m and 0 <= r_y + y < n and maze[r_x][r_y] != 3 and maze[r_x + x][r_y + y] != 5 and not [ r_x + x, r_y + y] in \ r[ 1]: new_r.append([r_x + x, r_y + y]) if 0 <= b_x + x < m and 0 <= b_y + y < n and maze[b_x][b_y] != 4 and maze[b_x + x][b_y + y] != 5 and not [ b_x + x, b_y + y] in \ b[ 1]: new_b.append([b_x + x, b_y + y]) # 새로운 큐 제한 조건에 따른 분류 for i in new_r: for j in new_b: road_r = [] road_b = [] if i != j: # 같은 위치 불가 if j == r[0] and i == b[0]: # 자리만 바꾼 경우 continue else: road_r += r[1] road_r += [i] road_b += b[1] road_b += [j] new.append([[i, road_r], [j, road_b]]) if len(q) == 0: result += 1 q = list(q) q += new q = deque(q) new = [] return 0

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42578 """ # 풀이 과정 # 선택하지 않는 경우의 수 추가 후 그걸 제외!! def solution(clothes): from itertools import combinations from collections import deque result = 1 check = {} n = [] # 옷 종류 분류 # dic 내의 종류별 옷 분류 for c in clothes: if c[-1] not in check: check[c[-1]] = 1 n.append(c[-1]) else: check[c[-1]] += 1 final = [] # 확인 할 조합 수 for t in check: result *= (check[t] + 1) return result - 1

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/17678 """ # 풀이 과정 """ 셔틀 운행 횟수 n 셔틀 운행 간격 t 한 셔틀에 탈 수 있는 최대 크루 수 m 크루가 대기열에 도착하는 시각을 모은 배열 timetable """ from collections import deque def change_time(x): H = x // 60 M = x % 60 if len(str(H)) == 1: H = "0" + str(H) else: H = str(H) if len(str(M)) == 1: M = "0" + str(M) else: M = str(M) return H + ":" + M def change_hour(k): x = k.split(":") hour = int(x[0]) * 60 + int(x[1]) return hour def solution(n, t, m, timetable): bus_table = [] gap = 0 bus = 9 * 60 for b in range(n): bus_table.append(bus + gap) gap += t person = [] for t in timetable: p = change_hour(t) person.append(p) while person: p = person.pop() if p > bus_table[-1]: continue else: person.append(p) break if len(person) == 0: return change_time(bus_table[-1]) person.sort() person = deque(person) # 최종시간을 알아보는 기준 지표 now = 0 # 최종탑승자 시간 last_person = -1 for b in bus_table: # 한 버스당 타는 인원 count = 0 while person: cru = person.popleft() if cru <= b and count < m: count += 1 last_person = cru else: person.appendleft(cru) break now = b if len(person) == 0 and count < m: return change_time(bus_table[-1]) return change_time(last_person - 1)

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/134239 """ # 풀이 과정 def solution(k, ranges): count = 0 fun = [[0, k]] while True: if k == 1: break count += 1 if k % 2 == 0: k = k / 2 fun.append([count, k]) else: k = k * 3 + 1 fun.append([count, k]) result = [] for a, b in ranges: s = 0 if count + b < a: result.append(-1) continue for c in range(a, count + b): if a > count + b: result.append(-1) break if c >= len(fun) - 1 or c < 0: result.append(-1) break elif c <= len(fun) - 2: if c < 0: s = -1 result.append(-1) break k = ((abs(fun[c + 1][1] + fun[c][1])) / 2) s += k if s != -1: result.append(s) return result