-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12985 """ # 풀이 과정 def solution(n, a, b): from collections import deque k = deque([a for a in range(1, n + 1)]) answer = 1 # 라운드 if a > b: b, a = a, b next_ = [] count = 0 while True: blue = k.popleft() red = k.popleft() if blue == a and red == b: return answer else: if blue == a or blue == b: k.append(blue) else: k.append(red) if blue == a or blue == b or red == a or red == b: count += 1 if count == 2: answer += 1 count = 0 return answer
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/258705 """ # 풀이 과정 # 일정 규칙성을 지닌 것으로 판단되어 점화식>dp 생각 접근 # 점화식 찾기 # 위에 삼각형이 있나 없나 여부에 따른 점화식의 변화 # 직전한을 수가 아닌 모양으로 표현해서 규칙성 찾아보기! def solution(n, tops): reuslt = 0 dp = [0] * (n + 1) # 0~n # case 분류 # \\ 실행 여부로 구분! i = [0] * (n + 1) # 실행 j = [0] * (n + 1) # 비실행 i[0] = 0 j[0] = 1 # 두번 째 항 if tops[0] == 1: i[1] = 1 j[1] = 3 else: i[1] = 1 j[1] = 2 for k in range(1, n): if tops[k] == 1: i[k + 1] = (i[k] + j[k]) % 10007 j[k + 1] = (i[k] * 2 + j[k] * 3) % 10007 else: i[k + 1] = (i[k] + j[k]) % 10007 j[k + 1] = (i[k] + j[k] * 2) % 10007 return (i[n] + j[n]) % 10007
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12981 """ # 풀이 과정 def solution(n, words): count = 1 all_count = 1 check = [] for k in range(len(words)): if k == 0: check.append(words[k]) count += 1 continue if check[-1][-1] == words[k][0] and not words[k] in check: check.append(words[k]) if count < n: count += 1 all_count += 1 else: count = 1 all_count += 1 else: return [count, int(all_count / n) + 1] return [0, 0]
-
""" 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/92345 """ # 풀이 과정 # 조건 # 발판 있는 곳 없는 곳 존재 # 밟던 발판 다른 곳으로 이동 시 사라짐 # 양 플레이어 상하좌우로 움직임 # 움직일 발판이 없는 경우 or 밖으로 넘어가는거 포함 패배 # 같은 발판에 존재 가능 # 같은 발판에 있다 둘중 한 플레이어가 이동하여 해당 발판이 사라지면 다른 플레이어 패배 # 시작: 플레이어 a 시작 # 항상 이길 수 있는 플레이어 패배하는 플레이어가 정해져 있음 # 항상 이기는 플레이어는 실수하지 않고 항상 지는 플레이어는 최대한 버티는 방향으로 했을 때 최적값 구하기 # 목표: 양플레이어가 최적으로 움직였을 때 횟수의 합 # 생각 방향: 보드 게임 bfs or dfs 접근 # 각 플레이어가 최적으로 움직이는 부분을 구현 핵심 누가 항상 이기는 플레이어인지 확인하기 # 최적이란? 이기는 플레이는 이길 수 있는 방향으로 지는 플레이어는 무조건 버티도록 하는 방향성 고민 # 항상 이기는 플레이어의 조건 # min,max 알고리즘 및 dfs 활용 # board: 보드 상태 aloc:a의 위치 bloc:b의 위치 dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] game = [] # 게임판 진행 상황 def start(ax, ay, bx, by, board, m, n): global game if game[ax][ay] == 1: return 0 count = 0 for x, y in zip(dx, dy): new_x = ax + x new_y = ay + y # 범위 밖 또는 해당판 존재x if not 0 <= new_x < m or not 0 <= new_y < n or board[new_x][new_y] == 0 or game[new_x][new_y] == 1: continue # 해당 말 움직였으므로 해당판 존재사라짐 game[ax][ay] = 1 # dfs 구현 # a의 말이 움직인 후에 같은 방식으로 b의 말이 움직임 enemy = start(bx, by, new_x, new_y, board, m, n) + 1 # 그 다음 for문을 위해 원복 game[ax][ay] = 0 if count % 2 == 0 and enemy % 2 == 1: count = enemy elif count % 2 == 0 and enemy % 2 == 0: count = max(count, enemy) elif count % 2 == 1 and enemy % 2 == 1: count = min(count, enemy) return count def solution(board, aloc, bloc): global game m = len(board) # 열 n = len(board[0]) # 행 ax, ay = aloc[0], aloc[1] bx, by = bloc[0], bloc[1] # 게임판 진행 상황 체크 game = [[0] * n for _ in range(m)] result = start(ax, ay, bx, by, board, m, n) return result
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/178870 """ # 풀이 과정 def solution(sequence, k): a = 0 b = 0 c = 0 result = [] while True: if a == 0 and b == 0 and c == 0: c += sequence[a] if c == k: result.append([a, b]) else: if c < k: b += 1 if b > len(sequence) - 1: break c += sequence[b] else: c -= sequence[a] if a > len(sequence) - 1: break a += 1 if c == k: result.append([a, b]) result.sort(key=lambda x: ([x[1] - x[0], x[0]])) return result[0]
-
""" 프로그래머스 출처:https://school.programmers.co.kr/learn/courses/30/lessons/60063 """ # 풀이 과정 """ bfs """ from collections import deque def arround(x, y, check_x, check_y): check = [[(x + 1, y), (x - 1, y)], [(x, y + 1), (x, y - 1)]] for i in check: if (check_x, check_y) in i: continue else: d = i k = [] for nx, ny in d: if nx != x: k.append((nx, ny, nx, check_y)) elif ny != y: k.append((nx, ny, check_x, ny)) return k def solution(board): m = len(board) n = len(board[0]) # 이동 dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] # 회전8,이동4 robot = ((0, 0), (0, 1)) q = deque([((0, 0), (0, 1), 0)]) visit = set([]) result = float("inf") while q: z = q.popleft() if (m - 1, n - 1) in z: result = min(result, z[2]) continue x1, x2 = z[0][0], z[0][1] y1, y2 = z[1][0], z[1][1] count = z[2] if not ((z[0]), (z[1])) in visit or not ((z[1]), (z[0])) in visit: visit.add(((z[0]), (z[1]))) visit.add(((z[1]), (z[0]))) else: continue # 이동 for nx, ny in zip(dx, dy): if 0 <= nx + x1 < m and 0 <= ny + x2 < n and 0 <= nx + y1 < m and 0 <= ny + y2 < n: if board[nx + x1][ny + x2] == 0 and board[nx + y1][ny + y2] == 0 and not ((nx + x1, ny + x2), ( nx + y1, ny + y2)) in visit and not ((nx + y1, ny + y2), (nx + x1, ny + x2)) in visit: q.append(((nx + x1, ny + x2), (nx + y1, ny + y2), count + 1)) # visit.add(((nx+x1,ny+x2),(nx+y1,ny+y2))) # visit.add(((nx+y1,ny+y2),(nx+x1,ny+x2))) check = arround(x1, x2, y1, y2) for nx, ny, mx, my in check: if 0 <= nx < m and 0 <= ny < n: if board[nx][ny] == 0 and board[mx][my] == 0 and not ((nx, ny), (x1, x2)) in visit and not ((nx, ny), ( x1, x2)) in visit: q.append(((x1, x2), (nx, ny), count + 1)) # visit.add(((x1,x2),(nx,ny))) # visit.add(((nx,ny),(x1,x2))) check = arround(y1, y2, x1, x2) for nx, ny, mx, my in check: if 0 <= nx < m and 0 <= ny < n: if board[nx][ny] == 0 and board[mx][my] == 0 and not ((nx, ny), (y1, y2)) in visit and not ((nx, ny), ( y1, y2)) in visit: q.append(((y1, y2), (nx, ny), count + 1)) # visit.add(((y1,y2),(nx,ny))) # visit.add(((nx,ny),(y1,y2))) return result
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/72411 """ # 풀이 과정 def solution(orders, course): from collections import Counter from itertools import combinations # menu=list("ABCDEFGHIJKLMNOPQRSTUVWXYZ") result = [] k = {} for a in orders: b = list(a) for c in course: d = list(combinations(b, c)) for e in d: e = sorted(list(e)) e = "".join(e) if e in k: k[e] += 1 else: k[e] = 1 set_menu = {} for f in k: if k[f] < 2: continue else: set_menu[f] = k[f] course_menu = [] for g in course: t = [] for h in set_menu: if len(h) == g: if len(t) == 0: t.append(h) else: if set_menu[h] > set_menu[t[-1]]: t.clear() t.append(h) elif set_menu[h] == set_menu[t[-1]]: t.append(h) course_menu = course_menu + t # course_menu=sorted(course_menu, key=len,reverse=True) course_menu.sort() for i in orders: last_check = [] for j in course_menu: if set(i) | set(j) == set(i) and j not in result: last_check.append(j) # print(last_check) result = result + last_check result.sort() return result
-
""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/64064 """ # 풀이 과정 from collections import deque def solution(user_id, banned_id): # 불량사용자 아이디 항목별 종류 check = [[] for _ in range(len(banned_id))] if len(banned_id) == 0: return 0 for num in range(len(banned_id)): for j in user_id: ban = banned_id[num] if len(ban) == len(j): for i in range(len(ban)): if ban[i] != "*" and ban[i] != j[i]: break elif ban[i] == "*": continue else: check[num].append(j) else: continue if len(banned_id) == 1: return len(set(check[0])) result = [] q = deque([]) # 기본 큐 만들기 for k in check[0]: q.append([k]) for ban in range(1, len(banned_id)): add_mem = [] for new in check[ban]: for before in q: add_mem.append(before + [new]) q = deque([]) q += add_mem count = len(q) while count > 0: t = q.popleft() count -= 1 if len(t) != len(set(t)): continue else: q.append(t) result = [] for r in add_mem: k = set(r) if len(r) == len(k): if len(result) == 0: result.append(k) else: for n in result: if len(n - k) == 0: break else: result.append(k) return len(result)
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/62048 """ # 풀이 과정 def solution(w, h): result = 0 if w == 1 or h == 1: return 0 if h < w: for k in range(h): result += int((k * w / h)) elif h == w: for k in range(w): return w * h - w else: for k in range(w): result += int(k * h / w) return result * 2
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/132266 """ # lv3 부대 복귀 # 내 풀이 # 조건 # 각 부대 지역 고유번호 지정 # 임무 완료 후 최단 시간으로 부대 복귀 # 적군의 방해로 지역이 막혀 부대 복귀 불가능한 대원 발생 가능 # 접근 사고 방향 # 최단 거리를 구하는 조건이라 다익스트라 알고리즘 떠올려야 하나 익숙하지 않아 dfs로 1차 접근 # dfs 방문 여부로 인한 최단거리 구성의 어려움으로 인한 bfs로 선회 후 재구성: # >1차: 시간초과 발생 # 2차 생각 전환 # 방향전환: 꼭 출발점에서 목적지를 찾아가야하나? 목적지에서 시작점까지를 돌면 source마다 할 필요 없이 반복 필요 없음 # 도착점에서 갈 수 없는 곳 모두 -1로 생각! # 목표:최단 시간을 담은 값을 리턴 # 총 지역수: n , 길 정보 roads , 부대원 위치: sources 강철부대 지역:destination from collections import deque from collections import defaultdict import sys sys.setrecursionlimit(10 ** 6) # 최대 깊이 설정 m = defaultdict(list) def solution(n, roads, sources, destination): check = [-1 for _ in range(n + 1)] # 각 부대별 최단 거리 정리 # 도착점으로부터 시작으로 사고 전환! 도착 못하면 -1 result = [] r = roads s = sources d = destination # 위치별 정리 for i, j in r: m[i].append(j) m[j].append(i) v = [False for _ in range(n + 1)] # 방문 여부 q = deque([[d, 0]]) new = [] # 거리에 따라 추가할 부분 while q: x, t = q.popleft() v[x] = True # 방문 check[x] = t new += m[x] if len(q) == 0: new = list(set(new)) # 중복 제거 if len(new) == 0: break for u in [y for y in new if v[y] == False]: q.append([u, t + 1]) if len(q) == 0: break new = [] # 그 다음 순서를 담기 위해서 초기화!! for z in s: result.append(check[z]) return result
