""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/67259 """ # 풀이 과정 """ 0:비어있음 1:벽이 있음 start:(0,0) destination:(n-1,n-1) 목표: 최소 비용으로 건설하기 생각 방향: 게임 보드를 활용 > bfs or dfs """ from collections import deque import copy import heapq # 수직 확인 def check(direction, direc): # 수직 여부 P = False if direction == "up" or direction == "down": one = True else: one = False if direc == "up" or direc == "down": two = True else: two = False if one == two: return P else: return True def solution(board): result = float("inf") b = board # 행,열 m = len(board) n = len(board[0]) # [[0, 1], [1, 0], [-1, 0], [0, -1]]; # 방향성 확인 dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] d = ["right", "left", "down", "up"] # {"right":float("inf"),"left":float("inf"),"down":float("inf"),"up":float("inf")} cost_table = [[0] * len(board[0]) for i in range(len(board))] for i in range(len(b)): for j in range(len(b)): cost_table[i][j] = {"right": float("inf"), "left": float("inf"), "down": float("inf"), "up": float("inf")} # 현 위치(x,y), 방향,비용 q = [(0, (0, 0), "stop")] while q: cost, location, direction = heapq.heappop(q) # 위치 x, y = location[0], location[1] if x == m - 1 and y == n - 1: cost_table[x][y][direction] = min(cost, cost_table[x][y][direction]) continue # # 방문처리 # if cost_table[x][y]<cost-600: # continue # else: # cost_table[x][y]=cost for nx, ny, direc in zip(dx, dy, d): # 해당판 내부 확인 if 0 <= x + nx < m and 0 <= y + ny < n: if board[x + nx][y + ny] == 0: # 방향성 체크 if direction == "stop": heapq.heappush(q, (cost + 100, (x + nx, y + ny), direc)) cost_table[x + nx][y + ny][direc] = cost + 100 else: p = check(direction, direc) if p == True: if cost_table[x + nx][y + ny][direc] < cost + 600: continue # 수직 + 직선 거리도 이동 heapq.heappush(q, (cost + 600, (x + nx, y + ny), direc)) cost_table[x + nx][y + ny][direc] = cost + 600 else: if cost_table[x + nx][y + ny][direc] < cost + 100: continue heapq.heappush(q, (cost + 100, (x + nx, y + ny), direc)) cost_table[x + nx][y + ny][direc] = cost + 100 result = float("inf") for i in cost_table[len(b) - 1][len(b) - 1].values(): result = min(result, i) return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/176962 """ # 풀이 과정 def solution(plans): result = [] # 결과 check = [] # 현재 진행중인 과제 remain = [] # 남겨둔 과제 time = 0 # 현재 시간 plans.sort(key=lambda x: (x[1].split(":")[0], x[1].split(":")[1])) # 시작 시간에 따른 정렬 print(plans) for x in plans: if len(check) < 1: check.append(x) work_start = check[0][1].split(":") work_minute = int(work_start[0]) * 60 + int(work_start[1]) time = work_minute work_check = int(work_start[0]) * 60 + int(work_start[1]) + int(check[0][2]) else: new_work = x[1].split(":") new_work_time = int(new_work[0]) * 60 + int(new_work[1]) if new_work_time < work_check: remain_work_time = work_check - new_work_time remain.insert(0, [check[0][0], remain_work_time]) check.pop() check.append(x) work_start = check[0][1].split(":") work_minute = int(work_start[0]) * 60 + int(work_start[1]) time = work_minute work_check = int(work_start[0]) * 60 + int(work_start[1]) + int(check[0][2]) else: result.append(check[0][0]) check.pop() time = work_check while True: # 공백 시간 과제 가능한지 체크 if len(remain) == 0: break elif time + remain[0][1] <= new_work_time: time = time + remain[0][1] result.append(remain[0][0]) remain.pop(0) elif time + remain[0][1] > new_work_time: remain[0][1] = abs(new_work_time - (time + remain[0][1])) time = new_work_time break check.append(x) work_start = check[0][1].split(":") work_minute = int(work_start[0]) * 60 + int(work_start[1]) work_check = int(work_start[0]) * 60 + int(work_start[1]) + int(check[0][2]) result.append(check[0][0]) final = [v for v, w in remain] result = result + final return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12907 """ def solution(n, money): dp = [0] * (n + 1) dp[0] = 1 for m in money: for now in range(m, n + 1): if now >= m: dp[now] += dp[now - m] return dp[n] % 1000000007

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/1844 """ #풀이과정 from collections import deque def solution(maps): q = deque([[0, 0, 1]]) visit = [[False] * len(maps[0]) for _ in range(len(maps))] dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] while q: x, y, z = q.popleft() visit[x][y] = True for new_x, new_y in zip(dx, dy): if 0 <= x + new_x < len(maps) and 0 <= y + new_y < len(maps[0]) and visit[x + new_x][y + new_y] == False and \ maps[x + new_x][y + new_y] != 0: q.append([x + new_x, y + new_y, z + 1]) visit[x + new_x][y + new_y] = True if visit[len(maps) - 1][len(maps[0]) - 1] == True: return z + 1 return -1

""" 출처: 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/49189 """ # 풀이 과정 """ 다익스트라 알고리즘 """ from collections import defaultdict from collections import deque def solution(n, edge): m = defaultdict(list) distance = [float("inf")] * (n + 1) distance[0], distance[1] = 0, 0 for x, y in edge: m[x].append(y) m[y].append(x) q = deque([(1, 0)]) while q: # 목적지, 거리 end, k = q.popleft() for i in m[end]: if distance[i] > (k + 1): q.append((i, k + 1)) distance[i] = (k + 1) r = max(distance) return distance.count(r)

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/81302?language=python3 """ # 풀이 과정 def solution(places): result = [] # bfs from collections import deque flag = False for a in places: q = [] dx = [-2, -1, 1, 2, 0, 0, 0, 0, -1, -1, 1, 1] dy = [0, 0, 0, 0, -2, -1, 1, 2, 1, -1, 1, -1] for c in range(5): for d in range(5): if a[c][d] == "P": q.append([c, d]) q = deque(q) if len(q) == 0: result.append(1) continue while q: e, f = q.popleft() flag = False for x, y in zip(dx, dy): if 0 <= e + x < 5 and 0 <= f + y < 5: if a[e + x][f + y] == "P": # case1 ## 중요 케이스 if abs(x) == 2 or abs(y) == 2: if abs(x) == 2 and abs(y) == 0: if x > 0 and a[e + x - 1][f + y] == "X": continue elif x < 0 and a[e + x + 1][f + y] == "X": continue else: print(1) flag = True break elif abs(y) == 2 and abs(x) == 0: if y > 0 and a[e + x][f + y - 1] == "X": continue elif y < 0 and a[e + x][f + y + 1] == "X": continue else: print(2) flag = True break # case2 ## 중요 케이스 elif abs(x) == 1 and abs(y) == 1: if x == 1 and y == 1: if a[e + x][f] == "X" and a[e][f + y] == "X": continue else: flag = True print(3) break elif x == 1 and y == -1: if a[e + x][f] == "X" and a[e][f + y] == "X": continue else: flag = True print(4) break elif x == -1 and y == 1: if a[e + x][f] == "X" and a[e][f + y] == "X": continue else: flag = True print(5) break elif x == -1 and y == -1: if a[e + x][f] == "X" and a[e][f + y] == "X": continue else: flag = True print(6) break # case3 elif abs(x) == 1 and abs(y) == 0: flag = True print(7) break # case4 elif abs(x) == 0 and abs(y) == 1: flag = True print(8) break else: continue if flag == True: break if flag == False: result.append(1) else: result.append(0) return result

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/42895 """ # 풀이 과정 from collections import defaultdict def solution(N, number): if N == number: return 1 num = defaultdict(set) num[1].add(N) for i in range(2, 9): num[i].add(int(str(N) * i)) for j in range(i): for a in num[j]: for b in num[i - j]: num[i].add(a + b) num[i].add(a - b) num[i].add(a * b) if b != 0: num[i].add(a // b) if number in num[i]: return i return -1 #-------------------------------------------- 개선 전 오답 과정 ----------------------------------------------------# from itertools import product from collections import deque def solution(N, number): cal = ["", "+", "//", "*", "-"] if N == number: return 1 count = 2 while True: start = str(N) * count start = list(start) cal_set = deque(list(product(cal, repeat=count - 1))) min_check = [] while cal_set: num = str(N) check = cal_set.popleft() for c in range(len(check)): num += check[c] num += start[c] # num=deque(list(num)) # while num[0]=="0" or num[0]=="+" or num[0]=="/" or num[0]=="*": # num.popleft() # num=str(eval("".join(num))) num = eval(num) if int(num) == number: return count count += 1 if count > 8: return -1 return -1

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/17687 """ # 풀이과정 def solution(n, t, m, p): from collections import deque check = m * t all_num = deque([0]) count = 1 while True: start = count num = deque([]) while True: start, j = divmod(start, n) # i 몫 j 나머지 if start == 0: if j != 0: if j == 10: num.appendleft("A") elif j == 11: num.appendleft("B") elif j == 12: num.appendleft("C") elif j == 13: num.appendleft("D") elif j == 14: num.appendleft("E") elif j == 15: num.appendleft("F") else: num.appendleft(j) break else: if j == 10: num.appendleft("A") elif j == 11: num.appendleft("B") elif j == 12: num.appendleft("C") elif j == 13: num.appendleft("D") elif j == 14: num.appendleft("E") elif j == 15: num.appendleft("F") else: num.appendleft(j) all_num += num if len(all_num) >= check: break count += 1 all_num = "".join(list(map(str, list(all_num)[p - 1::m][0:t]))) return all_num

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/258707 """ # 풀이 과정 # 최대 라운드의 수 # 미래에 카드가 있을 수도 있지만 그걸 위해 당장의 라운드를 넘겨야한다! # 당장의 라운드를 넘기는거!! # 코인을 안쓰고 손 안의 숫자 뭉치부터 써야한다! from collections import deque def solution(coin, cards): n = max(cards) + 1 cards = deque(cards) hand = [] # 첫 카드 뭉치 r = 1 # 라운드 # 손에 든 뭉치 슬라이싱 두 번 사용의 경우 효율 떨어짐! for i in range(len(cards) // 3): k = cards.popleft() hand.append(k) check = [] # game start while cards and coin >= 0 and True: flag = False # 라운드 넘긴여부 for j in range(2): new = cards.popleft() # # 라운드를 넘기는 수 하나가 손 안에 있는 경우 # if (n-new) in hand and coin>0: # hand.append(new) # coin-=1 # # 임시로 넣어두기! # else: check.append(new) # 라운드 통과 여부 for i in range(1, ((n - 1) // 2) + 1): # 1순위 코인 안쓰고 손 안의 수로만! if i in hand and (n - i) in hand: one = hand.index(i) del hand[one] two = hand.index(n - i) del hand[two] flag = True r += 1 break if flag == True: continue # 2순위 코인 한 개 쓰고 손 안의 수 소모 for i in range(1, ((n - 1) // 2) + 1): if i in hand and (n - i) in check and coin > 0: one = hand.index(i) del hand[one] two = check.index(n - i) del check[two] flag = True r += 1 coin -= 1 break elif i in check and (n - i) in hand and coin > 0: one = check.index(i) del check[one] two = hand.index(n - i) del hand[two] flag = True r += 1 coin -= 1 break if flag == True: continue for i in range(1, ((n - 1) // 2) + 1): # 새로 뽑은 수를 다 가져오기 if i in check and (n - i) in check and coin >= 2: one = check.index(i) del check[one] two = check.index(n - i) del check[two] r += 1 coin -= 2 flag = True break if flag == False: break return r

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12953 """ # 풀이 과정 def solution(arr): result = 2 for a in arr: if result != 1 and result % a == 0: continue else: count = min(a, result) while count > 1: if result % count == 0 and a % count == 0: break else: count -= 1 result = (a * result) // count return result