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

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12909 """ # 풀이 과정 def solution(s): count_1 = 0 count_2 = 0 s = list(s) if s[0] == "(" and s[len(s) - 1] == ")": while s: k = s.pop() print(k) if k == ")": count_1 += 1 else: count_2 += 1 if count_2 > count_1: return False return True else: return False

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/214288 """ # 풀이 과정 # 추가 고민 포인트 # 왜 상담사 추가 기준이 완탐으로 구현하는지 여부 확인 # 대기 시간이 긴 순서로 상담사를 구현시 틀린 테케 발생!!! # 완탐 구현시에도 시간 초과 발생x인 이유:상대적으로 적은 수의 상담수의 범위와 유형범위 from collections import deque import heapq def solution(k, n, reqs): # n:멘토 k:상담 유형 # 목표: 기다린 시간 최소 # [a,b,c] a~b분, c 유형 # point:유형별 상담사 수 result = [] # 유형별 상담 대기인원 check = [1 for _ in range(k)] n = n - k # 유형별 멘토 최소 1명이상 # 유형별 종료시간 체크, 상담사 수에 따라 가장 min값으로 최대로 빨리 끝나는 시간 finish = {} # 유형별 대기시간 s = [0 for _ in range(k)] # int로 dic 설정하는 방법 체크! for i in range(k): if not i + 1 in finish: finish[i + 1] = [] for a, b, c in reqs: if len(finish[c]) == 0: finish[c] = [a + b] continue # 상담 끝나는 시간, 시작 시간 비교 if finish[c][0] > a: # 상담사 인원이 남은 경우 if len(finish[c]) < check[c - 1]: heapq.heappush(finish[c], a + b) else: s[c - 1] += abs(finish[c][0] - a) num = finish[c][0] heapq.heappop(finish[c]) heapq.heappush(finish[c], num + b) else: heapq.heappop(finish[c]) heapq.heappush(finish[c], a + b) # 대기 시간이 큰 순서로 하나씩 상담사 배치 남은 상담사가 0명이 될 때까지! while n >= 1: f = s.index(max(s)) g = max(s) # 부족한 생각! # 대기할 시간이 동일한 유형에 대한 처리 생각!!! # 추가할 유형의 상담사 번호:f+1 """ if s.count(g)>1: f=find_bestnum(s,k,reqs,g,check) """ # 매 순간 가장 상담원 추가를 위해 전체 for문 고려 # check[f]+=1 # n-=1 result = float("inf") for f in range(len(check)): check[f] += 1 # 끝나는 시간 초기화 for i in range(k): finish[i + 1] = [] # 유형별 대기시간 초기화 s = [0 for _ in range(k)] # finish[c][0]:가장 빨리 끝나는 시간 finish[c][-1]:가장 늦게 끝나는 시간 # 대기시간 재체크 for a, b, c in reqs: if len(finish[c]) == 0: finish[c] = [a + b] continue # 상담 끝나는 시간, 시작 시간 비교 if finish[c][0] > a: # 상담사 인원이 남은 경우 if len(finish[c]) < check[c - 1]: heapq.heappush(finish[c], a + b) else: s[c - 1] += abs(finish[c][0] - a) num = finish[c][0] heapq.heappop(finish[c]) heapq.heappush(finish[c], num + b) else: heapq.heappop(finish[c]) heapq.heappush(finish[c], a + b) if sum(s) < result: result = sum(s) best = f # 상담사 수 초기화 check[f] -= 1 else: n -= 1 check[best] += 1 if n == 0: return result # print(finish,"finish") # print(check,"상담사 수") # print(s,"유형별 기다린 시간") return sum(s)