""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/60058 """ # 풀이과정 # 균형잡힌 괄호 문자열인지 체크하는 함수 def isbalanced(s): chk=0 for c in s: if c=='(': chk+=1 elif c==')': chk-=1 if chk==0: return True else: return False # 올바른 괄호 문자열인지 체크하는 함수 def iscorrect(s): stack=[] stack.append(s[0]) for i in range(1,len(s)): if len(stack)==0 or stack[-1]==')' or (stack[-1]=='(' and s[i]=='('): stack.append(s[i]) else: stack.pop() if len(stack)==0: return True else: return False def solution(p): answer = '' u="" v="" #빈 문자열이나 올바른 괄호 문자열은 그대로 반환 if len(p)==0 or iscorrect(p): return p #u가 균형잡힌 괄호 문자열이 될 때까지 2개씩 추가해서 u,v 나누기 for i in range(2,len(p)+1,2): if isbalanced(p[0:i]): u=p[0:i] v=p[i:len(p)] break if iscorrect(u): #u가 올바른 괄호 문자열일 때 answer+=u+solution(v) else: #u가 올바른 괄호 문자열이 아닐 때 answer+='('+solution(v)+')' for c in u[1:-1]: if c=='(': answer+=')' else: answer+='(' return answer

""" 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/131702 """ # 풀이과정 # 조건: 시계 방향으로만 돌리는거 가능, 한 번당 90도 단 상하좌우도 같이 돌아간다 # 모서리 3개만 돌아감 꼭짓점:2개 돌아감 # 시계 0:12 1:3 2:6 3:9 # 해결 가능한 퍼즐만 주어집니다. # 행과 열의 길이는 동일 # 목표: 최소한의 횟수로 퍼즐 해결 # 생각의 흐흠 및 방향성 변화 # 생각방향: 각각의 모든 수는 3번을 초과하지 않는다(제자리로 돌아가기 때문이다) # 주어진 조건을 봤을 때 완탐으로해도 시간초과 발생 가능성 적음 # for문을 바탕으로 전체를 둘러본 후 주변이 해당 시계를 포함하여 주변이 전부 0이 아닐경우 실행 # 그리고 만약 해당 시계를 바꿨음에도 주변이 모두 0 아닐경우 하나라도 0일 경우 stop # 완탐의 경우 모든 시계 내 원소가 0 1 2 3 중 하나라는 생각접근 # 각 칸의 돌려지는 횟수가 총합으로 각 칸이 돌려져야 될 횟수를 4로 나눴을때 나머지 횟수랑 동일해야한다. # 최대 경우의 수를 만든 후 직접 계산 시 시간 초과 4**64가지이기 떄문이다. 중복 순열 # 줄일 방법을 고민하기 or 새로운 접근 방향 고민 # 포인트 사고: 하나의 줄을 고정! 고정된 줄을 중심으로 나머지 줄의 돌릴 수도 정해진다 # 하나씩 고정시키면 자연스럽게 위에 맞춰서 아래가 정해진다!! 경우의 수도 첫줄 경우의 수이다 4**8가 최대가 된다 # 원순열 기본 원리랑 비슷 고정시킨 후 원형으로 만든 후 경우의 수 표현하는 방식 # 시계 돌리기 import copy from itertools import product from collections import deque def clock(new, a, b, t, l): dx = [1, -1, 0, 0, 0] dy = [0, 0, 1, -1, 0] for i, j in zip(dx, dy): if 0 <= a + i < l and 0 <= b + j < l: # t: 돌릴 횟수 new[a + i][b + j] = (new[a + i][b + j] + t) % 4 return new def solution(clockHands): result = [] c = clockHands l = len(c) # 목표 모양 target = [[0] * l for _ in range(l)] # 맨 윗줄 고정 시킬 회전 수 경우의 수 중복 순열 check = deque(list(product(range(4), repeat=l))) while check: # 회전 시킬판 deepcopy 대신 시간복잡도가 덜 드는 슬라이싱 활용! new=copy.deepcopy(c) #new = [i[:] for i in c] # 기준점이 돌아가는 횟수 count = 0 # 고정 시킬 첫줄 회전 횟수 체크 k = check.popleft() # k[i]: 첫 줄 i번째 회전시킬 횟수 for i in range(l): # 해당 지점 돌리기 # new[0][i]=change[(new[0][i]+k[i])%4] count += k[i] # 동서남북 바꾸기 new = clock(new, 0, i, k[i], l) for v in range(1, l): for w in range(l): if new[v - 1][w] != 0: # 위를 0으로 만들기 위한 돌릴 횟수 지정 x = 4 - new[v - 1][w] # 해당 지점 돌리기 # new[v][w]=(new[v][w]+x)%4 count += x # 동서남북 바꾸기 new = clock(new, v, w, x, l) else: continue # 목표한 모양과 같은 경우 기록 (맨 아래가 다를 수 있기 떄문이다) if sum(new[l - 1]) == 0: result.append(count) # print(new) return min(result) if len(result) > 0 else 0

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/76502 """ # 풀이 과정 def solution(s): from collections import deque result = 0 count = 0 k = deque(list(s)) check = [] open_ = ["[", "(", "{"] close_ = ["]", ")", "}"] if len(s) == 1: return 0 while count < len(s): if k[-1] in open_ or k[0] in close_: a = k.popleft() k.append(a) count += 1 else: check = [] flag = False for b in k: if b in open_: check.append(b) elif b in close_: if len(check) == 0: flag = True break else: c = close_.index(b) d = open_.index(check[-1]) if c == d: check.pop() else: break if len(check) == 0: if flag == False: result += 1 a = k.popleft() k.append(a) count += 1 else: a = k.popleft() k.append(a) count += 1 return result

""" 출처:프로그래머스 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