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

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/389478?language=python3 """ """ 2줄마다 나머지*2차이가 나는 사실을 생각하여 좀 더 효율적으로 개선이 될 거 같다 하지만 시간복잡도 효율상 좋진 않으나, 전체 택배 물건들을 리스트 내로 배열한 후 찾고자 하는 택배 위치를 찾은 후 해당 위치를 이동하여 택배 여부를 확인하는 방식으로 1차적으로 답을 구해낼 수 있었다. """ # 풀이과정 def solution(n, w, num): if n%w==0: floor=(n//w) else: floor=(n//w)+1 block=[ [False]*w for _ in range(floor)] for i in range(n): now=i//w where=((i+1)%w)-1 if where==-1: where=w-1 if now%2==0: block[now][where]=i+1 else: block[now][w-where-1]=i+1 for i in range(floor): for j in range(w): if block[i][j]==num: nx,ny=i,j break result=1 while True: if nx+1>floor-1: break else: if block[nx+1][ny]!=False: nx+=1 result+=1 else: break return result

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/42861 """ # 풀이 과정 # 삼각형 변의 길이 조건 생각 크루스칼 알고리즘 from collections import defaultdict def solution(n, costs): c = sorted(costs, key=lambda x: x[2]) island = defaultdict(set) node_cost = defaultdict(int) node_link = defaultdict(list) result = 0 check = [] for x, y, cost in c: island[x].add(x) island[y].add(y) node_cost[(x, y)] = cost node_cost[(y, x)] = cost for x, y, cost in c: if len(island[x] & island[y]) == 0: check.append((x, y, cost)) for i in island[x] | island[y]: island[i] = island[x] | island[y] result += cost if len(check) == n - 1: return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/181188 """ # 풀이 과정 def solution(targets): targets.sort(key=lambda x: x[1]) target = 0 count = 0 for x, y in targets: if target <= x: count += 1 target = y return count

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12920 """ # 풀이 과정 import heapq from collections import deque def solution(n, cores): c = cores first = n if len(c) >= n: return n elif len(c) == 1: return 1 work = [] count = 0 # sol heapq: 정확도 100 효율성 부족 # 주어진 코어 사용 # for w in range(len(cores)): # heapq.heappush(work,(c[w],w+1,c[w])) # count+=1 # 시간 초과 발생 # while count<n: # time,core_num,work_time=heapq.heappop(work) # heapq.heappush(work,(time+(work_time),core_num,work_time)) # count+=1 # sol2 이진탐색(이분탐색) left = 1 right = max(cores) * (n - len(c)) n -= len(c) while left < right: mid = (left + right) // 2 capacity = 0 for d in cores: capacity += mid // d if capacity >= n: right = mid else: left = mid + 1 check = [] for i in range(len(c)): if right % c[i] != 0: n -= right // c[i] else: check.append(i + 1) n -= ((right // c[i]) - 1) # 끝 부분에는 모두 나머지가 0이더라도 먼저 들어가는 순서에 따라 모든 사이클이 돌기전에 끝날 수 있다 return check[n - 1]