""" 출처: 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/72415 """ # 풀이 과정 """ 조작횟수: enter+방향키 목표:남은 카드를 모두 제거하는데 필요한 키 조작 횟수의 최솟값 생각방향: 카드를 하나 고르면 무조건 그 짝을 무조건 찾아야한다 그 다음 카드를 선택하는 기준은? 배열 자체가 작기 때문에 크기가 중요하진 않다 모든 경우의 수 고려가능 칸 16개이기 떄문에 카드 종류 최대 8개 뽑을 순서의 카드를 미리 정한 후 그 순서에 맞춰서 뽑은 후 순서 정하기 # 시간적으로 코드가 문제가 없으므로 논리의 틀린 부분이 없기에 수정 후 풀이가능 만약, 해당 방향에 카드가 하나도 없다면 그 방향의 가장 마지막 칸으로 이동합니다. < 중요한 생각의 포인트 기점 """ import copy from itertools import combinations from itertools import permutations from collections import defaultdict from collections import deque # 두 점 사이의 이동 (현재 위치, 이동할 위치, 이동 횟수, 해당 게임판) def start(now_x, now_y, nex_x, nex_y, fir): """ if now_x==nex_x and now_y==nex_y: return 0 queue, visit = deque([[now_x, now_y, 0]]), {(now_x,now_y)} while queue: # BFS x, y, c = queue.popleft() for dx, dy in [(0,1),(0,-1),(1,0),(-1,0)]: nx, ny = x+dx, y+dy # Normal move cx, cy = x, y while True: # Ctrl + move cx, cy = cx+dx, cy+dy if not (0 <= cx <= 3 and 0 <= cy <= 3): cx, cy = cx-dx, cy-dy break elif fir[cx][cy] != 0: break if (nx, ny) == (nex_x,nex_y) or (cx, cy) == (nex_x,nex_y): # 도착 최단 경로 return c+1 if (0 <= nx <= 3 and 0 <= ny <= 3) and (nx, ny) not in visit: queue.append((nx, ny, c+1)) visit.add((nx, ny)) if (cx, cy) not in visit: queue.append((cx, cy, c+1)) visit.add((cx, cy)) """ q = deque([[now_x, now_y, count]]) num = float("inf") dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] visit = set([]) q = deque([(now_x, now_y, 0)]) while q: i, j, c = q.popleft() # 방문 기록 visit = visit | set([(i, j)]) if i == nex_x and j == nex_y: return c for nx, ny in zip(dx, dy): x, y = i, j if 0 <= x + nx < 4 and 0 <= y + ny < 4: if not (x + nx, y + ny) in visit: q.append((x + nx, y + ny, c + 1)) visit = visit | set([(x + nx, y + ny)]) ctrlx, ctrly = i, j while True: ctrlx += nx ctrly += ny if not 0 < ctrlx < 4 or not 0 < ctrly < 4: if nx == 1: if not (3, ctrly) in visit: q.append((3, ctrly, c + 1)) visit = visit | set([(3, ctrly)]) elif nx == -1: if not (0, ctrly) in visit: q.append((0, ctrly, c + 1)) visit = visit | set([(0, ctrly)]) elif ny == 1: if not (ctrlx, 3) in visit: q.append((ctrlx, 3, c + 1)) visit = visit | set([(ctrlx, 3)]) elif ny == -1: if not (ctrlx, 0) in visit: q.append((ctrlx, 0, c + 1)) visit = visit | set([(ctrlx, 0)]) break elif fir[ctrlx][ctrly] == 1: if not (ctrlx, ctrly) in visit: q.append((ctrlx, ctrly, c + 1)) visit = visit | set([(ctrlx, ctrly)]) break return 0 # k:카드 뽑는 순서, 게임판, 현 위치, 총 움직인 순서 def count(k, distance): order, game, location, count = k[0], k[1], k[2], k[3] x, y = location[0], location[1] result = float("inf") q = deque([[order, game, [x, y], count]]) while q: new_order, new_game, new_location, new_count = q.popleft() new_x, new_y = new_location[0], new_location[1] new_order = deque(new_order) if len(new_order) == 0: # print(new_count,result) result = min(result, new_count) continue # print(new_order,"before") num = new_order.popleft() # print(new_order,"after") # one > two count_one = new_count # two > one count_two = new_count # 같은 카드는 2개이므로 어느쪽으로 갈지 택해야한다 fir = copy.deepcopy(new_game) # 새로운 게임판1 fir_x, fir_y = distance[num][0] # one 위치 sec = copy.deepcopy(new_game) # 새로운 게임판2 sec_x, sec_y = distance[num][1] # two 위치 # location > one > two one = start(new_x, new_y, fir_x, fir_y, fir) count_one += (one + 1) one = start(fir_x, fir_y, sec_x, sec_y, fir) count_one += (one + 1) # fir 변형 fir[fir_x][fir_y] = 0 fir[sec_x][sec_y] = 0 order_one = copy.deepcopy(new_order) q.append([order_one, fir, [sec_x, sec_y], count_one]) # location > two > one two = start(new_x, new_y, sec_x, sec_y, sec) count_two += (two + 1) two = start(sec_x, sec_y, fir_x, fir_y, sec) count_two += (two + 1) # sec 변형 sec[fir_x][fir_y] = 0 sec[sec_x][sec_y] = 0 order_two = copy.deepcopy(new_order) q.append([order_two, sec, [fir_x, fir_y], count_two]) # if count_one>=count_two: # q.append([order_one,fir,[sec_x,sec_y],count_one]) # else: # q.append([order_two,sec,[fir_x,fir_y],count_two]) return result def solution(board, r, c): result = float("inf") # 카드 위치 distance = defaultdict(list) # 현재 위치 d = [r, c] # 카드 종류 card = [] for i in range(4): for j in range(4): if board[i][j] != 0: card.append(board[i][j]) card = list(set(card)) for i in card: for v in range(4): for w in range(4): if board[v][w] == i: distance[i].append([v, w]) turn = list(permutations(card, len(card))) turn = list(map(list, turn)) # print("turn",turn) q = [] # 카드 뽑는 순서,게임판,현 위치, 총 움직인순서 for i in turn: new = copy.deepcopy(board) q.append([i, new, [r, c], 0]) while q: k = q.pop() check = count(k, distance) result = min(check, result) return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12945 """ # 풀이 과정 def solution(n): count = 2 func_1 = 1 func_0 = 0 while count <= n: count += 1 func_2 = func_1 + func_0 result = func_2 func_1, func_0 = func_2, func_1 return result % 1234567

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/17676 """ # 풀이 과정 # 누적합 from collections import defaultdict Data = [0] * 24 * 60 * 60 * 1000 # for s in range(24*60*60): # Data[s]=0 def time_to_sec(x, y): global Data t = x.split(":") hour, minu, sec = int(t[0]), int(t[1]), float(t[2]) end_time = (int(hour) * 60 * 60 + int(minu) * 60 + sec) * 1000 blank = list(y) blank.pop() y = "".join(blank) # 시작 시간, 끝 시간 start = end_time - float(y) * 1000 + 1 start = max(0, start) end_time = min(24 * 60 * 60 * 1000 - 1, end_time + 999) start, end = int(start), int(end_time) for tra in range(start, end + 1): Data[tra] += 1 return 0 def solution(lines): global Data for l in lines: d = l.split(" ") time = time_to_sec(d[1], d[2]) result = 0 count = 0 result = max(Data) return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/87946 """ # 플이 과정 def solution(k, dungeons): # 목표: 최대 던전 수 """ 일단 k가 던전 최소 피로도, 소모피로도 보다 클 시 클리어를 전제로 한 후 만약 그보다 좋은 조건의 던전이 나올 시 그것부터 클리어 한 후 다시 최종 추가는 나중에?! """ from collections import deque from itertools import permutations t = deque(list(permutations(dungeons, len(dungeons)))) result = [] dungeons.sort(key=lambda x: (x[1], -x[0])) for a in t: count = 0 p = k a = deque(list(a)) while a: c = a.popleft() if p >= c[0]: if p >= c[1]: p -= c[1] count += 1 result.append(count) return max(result)

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/59405 """ """ SELECT NAME from ANIMAL_INS order by DATETIME asc limit 1 """

""" 출처 프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/12942 """ # 풀이 과정 def solution(matrix_sizes): m = matrix_sizes dp = [[0] * len(m) for _ in range(len(m))] l = len(m) # 자기자신은 연산값 0 for start in range(l): dp[start][0] = 0 for gap in range(1, l): for start in range(l - gap): end = start + gap result = float("inf") for go in range(start, end): result = min(dp[start][go] + dp[go + 1][end] + m[start][0] * m[go][1] * m[end][1], result) dp[start][end] = result return dp[0][l - 1]

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42587 """ # 풀이 과정 # 숫자가 클수록 우선순위가 높다! from collections import deque def solution(priorities, location): result = 0 # 실행 순서 p = deque(priorities) l = location finish_num = p[l] p[l] = 0 while True: q = p.popleft() if q == 0: if len(p) == 0: return result + 1 else: if finish_num >= max(p): return result + 1 else: p.append(q) else: if q >= max(p) and q >= finish_num: result += 1 else: p.append(q)

""" 출처: 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/59407 """ """ 풀이 과정 SELECT ANIMAL_ID from ANIMAL_INS where NAME is not null order by ANIMAL_ID asc """

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/12938 """ # 풀이 과정 from collections import deque, defaultdict def solution(n, s): if n > s: return [-1] if s % n == 0: return [s // n] * n else: k = s % n one = [s // n + 1] * k two = [s // n] * (n - k) result = two + one return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/17679 """ # 풀이 과정 # idea: 첫번쨰로 지워지는 블록 제거 후 재배열 후 다시 블록 제거 반복! def solution(m, n, board): from collections import deque b = [] for k in range(m): b.append(list(board[k])) result = 0 dx = [1, 0, 1] dy = [0, 1, 1] while True: count = 0 # 지워지는 블록 체크 check = deque([]) # 지워지는 블록 목록 # i,j를 중심으로 팔방위 탐색 for i in range(m): for j in range(n): if b[i][j] == 0: continue if j - 1 >= 0 and i - 1 >= 0: if b[i][j] == b[i - 1][j - 1] == b[i][j - 1] == b[i - 1][j]: check.append([i, j]) continue if j + 1 < n and i - 1 >= 0: if b[i][j] == b[i][j + 1] == b[i - 1][j + 1] == b[i - 1][j]: check.append([i, j]) continue if j - 1 >= 0 and i + 1 < m: if b[i][j] == b[i][j - 1] == b[i + 1][j - 1] == b[i + 1][j]: check.append([i, j]) continue if j + 1 < n and i + 1 < m: if b[i][j] == b[i + 1][j] == b[i + 1][j + 1] == b[i][j + 1]: check.append([i, j]) continue while check: one, two = check.popleft() b[one][two] = 0 count += 1 if count == 0: # 지워지는 블록이 없을 경우 답 return result # 블록 재배치 위에 있는걸로 대체 # 0이 아닌 부분을 내리는 방법? for i in range(m - 1, -1, -1): for j in range(n): if b[i][j] == 0: start = i - 1 while start >= 0: if b[start][j] != 0: b[i][j] = b[start][j] b[start][j] = 0 break else: start -= 1 result += count answer = result return answer