""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/12979 """ # 풀이 과정 from collections import deque def solution(n, stations, w): before = set(stations) # 기지국 설치 new = set([]) s = deque(stations) min_network = 0 max_network = 0 result = 0 # 시작부분 범위 내에 없는 경우 if s[0] - w > 1: max_network = 1 + 2 * w new.add(1 + w) result += 1 # 기지국 개설 후 시작 else: max_network = s.popleft() + w while max_network < n: if len(s) > 0: # 이미 설치된 곳의 전파가 드는 권역에 있는 경우(연장하기) if s[0] - w <= max_network <= s[0] + w: max_network = s[0] + w s.popleft() # 전파가 드는 권역이 아닌 경우(최대한 넓은 범위를 커버하게하기) elif s[0] - w >= max_network + 1: result += 1 new.add(max_network + 1 + w) max_network = max_network + 1 + 2 * w # 이미 최대로 설치된 곳의 최대치보다 범위가 현재 넓은 경우 elif s[0] + w < max_network: while True and s: if s[0] + w <= max_network: s.popleft() else: break else: result += 1 new.add(max_network + 1 + w) max_network = max_network + 1 + 2 * w # print(s,max_network) return len(new - before)

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/138476 """ #풀이과정 def solution(k, tangerine): count = {} for x in tangerine: if not str(x) in count: count[str(x)] = 1 else: count[str(x)] += 1 count = sorted(count.items(), key=lambda x: -x[1]) result = [] for y, z in count: if k > 0: result.append(y) k -= z else: break return len(result)

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/challenges?order=recent&levels=3&languages=python3&page=3 """ # 풀이 과정 from collections import deque # 기둥 유지 가능 여부 확인 def check_up(x, y, check): # 그 아래 기둥이 있는 경우 if (x, y - 1, x, y) in check: # check.add((x,y,x,y+1)) return True # 그 아래 보가 있을 경우 elif (x - 1, y, x, y) in check or (x, y, x + 1, y) in check: # check.add((x,y,x,y+1)) return True else: return set([(x, y, x, y + 1)]) # 보 유지 가능 여부 확인 def check_right(x, y, check): # 밑에 기둥이 있거나, 양쪽 보가 존재가 할 경우 if (x, y - 1, x, y) in check or (x + 1, y - 1, x + 1, y) in check: # check.add((x,y,x+1,y)) return True # 양쪽 보가 존재할 경우 elif (x - 1, y, x, y) in check and (x + 1, y, x + 2, y) in check: # check.add((x,y,x+1,y)) return True else: return set([(x, y, x + 1, y)]) def solution(n, build_frame): # 기둥,보 설치 확인 check = set([]) for x, y, a, b in build_frame: # 설치 1 if b == 1: # 기둥 if a == 0: # 바닥인경우 if y == 0: check.add((x, y, x, y + 1)) else: # 그 아래 기둥이 있는 경우 if (x, y - 1, x, y) in check: check.add((x, y, x, y + 1)) # 그 아래 보가 있을 경우 elif (x - 1, y, x, y) in check or (x, y, x + 1, y) in check: check.add((x, y, x, y + 1)) # 보 else: if y != 0: # 밑에 기둥이 있거나, 양쪽 보가 존재가 할 경우 if (x, y - 1, x, y) in check or (x + 1, y - 1, x + 1, y) in check: check.add((x, y, x + 1, y)) # 양쪽 보가 존재할 경우 elif (x - 1, y, x, y) in check and (x + 1, y, x + 2, y) in check: check.add((x, y, x + 1, y)) else: q = deque([]) up = [(0, 1, 0, 2), (-1, 1, 0, 1), (0, 1, 1, 1)] # 기둥 right = [(1, 0, 2, 0), (1, 0, 1, 1), (-1, 0, 0, 0), (0, 0, 0, 1)] # 보 # 기둥 if a == 0: k = set([(x, y, x, y + 1)]) check = check - k # 기둥 제거 # 제거되는지 여부 판단 for a, b, c, d in up: if (x + a, y + b, x + c, y + d) in check: # 기둥 if d - b == 1: flag = check_up(x + a, y + b, check) if flag != True: check = check | k break else: flag = check_right(x + a, y + b, check) if flag != True: check = check | k break else: k = set([(x, y, x, y + 1)]) check = check - k # 기둥 제거 """ for a,b,c,d in up: if (x+a,y+b,x+c,y+d) in check: q.append((x+a,y+b,x+c,y+d)) """ # 보 제거 여부 판단 else: k = set([(x, y, x + 1, y)]) check = check - k # 기둥 제거 # 제거되는지 여부 판단 for a, b, c, d in right: if (x + a, y + b, x + c, y + d) in check: # 기둥 if d - b == 1: flag = check_up(x + a, y + b, check) if flag != True: check = check | k break else: flag = check_right(x + a, y + b, check) if flag != True: check = check | k break else: k = set([(x, y, x + 1, y)]) check = check - k # 기둥 제거 """ for a,b,c,d in right: if (x+a,y+b,x+c,y+d) in check: q.append((x+a,y+b,x+c,y+d)) break else: k=set([(x,y,x+1,y)]) check=check-k # 보 제거 """ """ for a,b,c,d in right: if (x+a,y+b,x+c,y+d) in check: q.append((x+a,y+b,x+c,y+d)) """ # 기둥 또는 보를 제거함으로써 주변 제거할 기둥 보 탐색 """ while q: k=q.popleft() # 기둥 if k[3]-k[1]!=0: shape="기둥" exist=check_up(k[0],k[1],check) # 보 else: shape="보" exist=check_right(k[0],k[1],check) if exist==True: continue else: check=check-exist if shape=="기둥": for a,b,c,d in up: if (k[0]+a,k[1]+b,k[0]+c,k[1]+d) in check: q.append((k[0]+a,k[1]+b,k[0]+c,k[1]+d)) else: for a,b,c,d in right: if (k[0]+a,k[1]+b,k[0]+c,k[1]+d) in check: q.append((k[0]+a,k[1]+b,k[0]+c,k[1]+d)) """ # print(check,"check") # 마무리 단계 재 구조화 result = [] for a, b, c, d in check: if d - b == 1: s = 0 else: s = 1 result.append([a, b, s]) result.sort() return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/42885 """ # 풀이 과정 def solution(people, limit): from collections import deque answer = 0 people.sort(reverse=True) people = deque(people) while people: a = people.popleft() if len(people) > 0: b = people.pop() else: b = 0 if a + b > limit: people.append(b) answer += 1 return answer

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/388353 """ # 풀이과정 """ 겉면에서 출발하는 bfs실시 후 도착 가능한 알파벳 제거 두 번 반복된 경우 적용할 필요 없음 모두 그냥 빼버리는게 가능 해당 알파벳 찾은 후 빈공간으로 bfs 적용하는 방식이 좀 더 효율적일거라 생각된다. """ """ 겉면에서 출발하는 bfs실시 후 도착 가능한 알파벳 제거 두 번 반복된 경우 적용할 필요 없음 모두 그냥 빼버리는게 가능 해당 알파벳 찾은 후 빈공간으로 bfs 적용하는 방식이 좀 더 효율적일거라 생각된다. 모든 화물에 대해 이동 가능 조사 후 bfs에 나중에 반영 중간중간 반영x 몆 가지 케이스가 시간초과 발생 개선 방법 과정 >수정 방안 고민 > global 맵 생성 후 그 자리를 지나면 지게차로 가능하다 판정 여부 확인 > 없는 알파벳 존재 여부 추가 후 확인 정답 과정: visit한 여부를 이동 직후 바로 도착으로 확인해야 시간을 단축할 수 있다. """ from collections import deque, Counter map = [] def bfs(s, i, j): global map m = len(s) n = len(s[0]) dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] q = deque([(i, j)]) flag = False visit = [[False] * n for _ in range(m)] while q: x, y = q.popleft() visit[x][y] = True if map[x][y] == True: return True for nx, ny in zip(dx, dy): if nx + x >= m or nx + x < 0: flag = True break elif ny + y >= n or ny + y < 0: flag = True break else: if s[nx + x][ny + y] == "" and visit[nx + x][ny + y] == False: q.append((nx + x, ny + y)) visit[nx + x][ny + y] = True # 지게차 맵 재갱신 if flag == True: # map[i][j]==True for a in range(m): for b in range(n): if visit[a][b] == True: map[a][b] == True return flag def check_alpha(s, alpha): del_alpha = [] global map map = [[False] * len(s[0]) for _ in range(len(s))] for i in range(len(s)): for j in range(len(s[0])): if s[i][j] == alpha: check = bfs(s, i, j) if check == True: del_alpha.append((i, j)) for x, y in del_alpha: s[x][y] = "" return s, len(del_alpha) def all_alpha(s, alpha): for i in range(len(s)): for j in range(len(s[0])): if s[i][j] == alpha: s[i][j] = "" return s def solution(storage, requests): s = [] all_ = "" for stor in storage: s.append(list(stor)) all_ += stor count_alpha = Counter(all_) for r in requests: if not r[0] in count_alpha: continue if count_alpha[r[0]] == 0: continue if len(r) == 2: alpha = r[0] count_alpha[alpha] = 0 s = all_alpha(s, alpha) else: alpha = r s, num = check_alpha(s, alpha) count_alpha[alpha] -= num count = 0 for i in range(len(s)): for j in range(len(s[0])): if s[i][j] != "": count += 1 return count

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/86053 """ # 풀이 과정 """ 조건: 새 도시를 만들 조건: 금:a 은:b 이해 과정:i번 도시에는 일정 이상의 광물이 있고, 새 도시에 광물을 전달해준다 목표:새로운 도시를 건설하기 위한 최단 시간을 구하시오 """ """ # 필요한 금:a 은:b g[i]:i번 도시에 보유한 금 s[i]:i번 도시에 보유한 은 신도시까지 이동시간: t[i] 옮길 수 있는 최대 양 w[i] """ # 생각 방향: 각 도시에 일정량을 가져오는 경우를 모두 산정 후 그 중 누적 후 시간이 최소인것을 구한다. # 시간 빠른 순으로 트럭을 돌려보내고 받고를 한 후 금과 은 중에 더 많은 광석을 먼저 소비하는 방식으로 한 후 다시 heap 리스트에 추가! # 시간을 1씩 올려서 혹은 내려서 접근하는 방식은 많은 시간을 소요해 시간초과로 이어진다 # 이분탐색(이진탐색)을 바탕으로 접근해야 한다 import heapq def solution(a, b, g, s, w, t): start = 0 end = (10 ** 9) * (10 ** 5) * 4 result = (10 ** 9) * (10 ** 5) * 4 # 도시 개수 city = len(g) while start <= end: gold_max, gold_min = 0, 0 silver_max, silver_min = 0, 0 weight = 0 mid = (start + end) // 2 for k in range(city): # 편도 횟수 count = mid // t[k] # 왕복만 가능 if count % 2 == 0: check = (count // 2) * w[k] if check >= s[k] + g[k]: check = s[k] + g[k] weight += check silver_max += s[k] silver_min += s[k] gold_max += g[k] gold_min += g[k] else: weight += check if check >= s[k]: silver_max += s[k] gold_min += check - s[k] # 실버만 채워야함 else: silver_max += check if check >= g[k]: gold_max += g[k] silver_min += check - g[k] else: gold_max += check # 마지막 편도 한 번까지 가능 else: check = ((count // 2) + 1) * w[k] if check >= s[k] + g[k]: check = s[k] + g[k] weight += check silver_max += s[k] silver_min += s[k] gold_max += g[k] gold_min += g[k] else: weight += check if check >= s[k]: silver_max += s[k] gold_min += check - s[k] # 실버만 채워야함 else: silver_max += check if check >= g[k]: gold_max += g[k] silver_min += check - g[k] else: gold_max += check if weight >= a + b and gold_max >= a and silver_max >= b: result = min(result, mid) end = mid - 1 # num=silver_max # for i in range(gold_min,gold_max+1): # if i >=a and num>=b: # break # else: # num-=1 # else: # start=mid+1 # continue # result=min(result,mid) # end=mid-1 else: start = mid + 1 return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/87377 """ # 풀이 과정 def solution(line): from itertools import combinations # 직선 2개씩 묶음 집합 k = list(combinations(line, 2)) # 교점들의 집합 result = [] line_x, line_y = [], [] for a in k: a = list(a) # ad-bc check 평행 또는 일치 확인 if a[0][0] * a[1][1] - a[0][1] * a[1][0] == 0: continue else: x = (a[0][1] * a[1][2] - a[0][2] * a[1][1]) / (a[0][0] * a[1][1] - a[0][1] * a[1][0]) y = (a[0][2] * a[1][0] - a[0][0] * a[1][2]) / (a[0][0] * a[1][1] - a[0][1] * a[1][0]) if int(x) == x and int(y) == y: result.append([int(x), int(y)]) line_x.append(int(x)) line_y.append(int(y)) ################### 교점까지 완료 ################## # print(result) # print(line_x) line_y.sort() print(line_y) line_x.sort() print(line_y) """ if abs(line_x[0])>=abs(line_x[-1]): max_x=abs(line_x[0]) else: max_x=abs(line_x[-1]) """ check_x = max(line_x) - min(line_x) + 1 # print(check_x,"x") map = [list("." * check_x) for b in range(min(line_y), max(line_y) + 1)] # print(map, "map") result.sort(key=lambda x: (-x[1])) # print(result) for c, d in result: # print(max(line_y)-d,max_x+c,"좌표 확인") map[max(line_y) - d][c - min(line_x)] = "*" for t in range(len(map)): map[t] = "".join(map[t]) # print(map) return map # print(result) # print(int(max_x),int(max_y),"최대값") # result.sort(key=lambda x:(-x[1],x[0])) # result=deque(result) answer = [] check_y = 0 star = "" print(max_x, max_y, "최댓값") print(result) map = [list("." * (max_x * 2 + 1))] * (max_y * 2 + 1) # x,y middle max_x+1: x middle max_y+1: y middle for v, w in result: if v >= 0 and w >= 0: map[max_y - abs(w)][max_x + abs(v)] = "*" elif v >= 0 and w < 0: map[max_y - abs(w)][max_x - abs(v)] = "*" elif v < 0 and w >= 0: map[max_y + abs(w)][max_x + abs(v)] = "*" else: map[max_y + abs(w)][max_x - abs(v)] = "*" for t in range(len(map)): map[t] = "".join(map[t]) # print(map) return answer

""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/72414 """ # 풀이 과정 """ 주어진 변수: play_time: 재생시간, adv_time:재생시간 길이 logs:시청자들이 시청한 구간정보 목표: 누적 재생시간이 나오는 곳에 공익광고 삽입 시작시간 구하기(여러 개라면 제일 빠른 시간) 생각방향: 주어진 광고시간을 초당으로 누적인원을 집계했을 때 가장 많이 본 시간의 시작점 구하기 모두 초로 바꿔서 구하기 """ def solution(play_time, adv_time, logs): play = play_time.split(":") play = list(map(int, play)) # 플레이타임을 모두 초로 변경 p = play[0] * 60 * 60 + play[1] * 60 + play[2] # 초당 뷰 체크 목록 view_check = [0] * (p + 1) adver = adv_time.split(":") adver = list(map(int, adver)) # 광고 시간을 모두 초로 변경 adver = adver[0] * 60 * 60 + adver[1] * 60 + adver[2] l = [] for i in logs: # - 제거 viewer = i.split("-") v_start = viewer[0] v_end = viewer[1] # : 제거 v_start = v_start.split(":") v_start = list(map(int, v_start)) v_end = v_end.split(":") v_end = list(map(int, v_end)) v_start = v_start[0] * 60 * 60 + v_start[1] * 60 + v_start[2] v_end = v_end[0] * 60 * 60 + v_end[1] * 60 + v_end[2] l.append((v_start, v_end)) # 각 초별 시청자 집계 for start, end in l: view_check[start] += 1 view_check[end] -= 1 # 시간별 집계 for i in range(len(view_check)): view_check[i] += view_check[i - 1] # 합 집계 prefix_sum = [0] * len(view_check) prefix_sum[0] = view_check[0] for i in range(1, len(view_check)): prefix_sum[i] = prefix_sum[i - 1] + view_check[i] # 최고점 기록 best_view = prefix_sum[adver - 1] best_time = 0 for i in range(adver, len(view_check)): if prefix_sum[i] - prefix_sum[i - adver] > best_view: best_view = prefix_sum[i] - prefix_sum[i - adver] best_time = (i - adver + 1) result = "" # best_time 변환 hour = best_time // 3600 if len(str(hour)) == 1: h = str(0) + str(hour) else: h = str(hour) result = result + h + ":" minute = (best_time - 3600 * hour) // 60 if len(str(minute)) == 1: m = str(0) + str(minute) else: m = str(minute) result = result + m + ":" second = best_time - 3600 * hour - 60 * minute if len(str(second)) == 1: s = str(0) + str(second) else: s = str(second) result = result + s return result

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/172927 """ # 풀이 과정 def solution(picks, minerals): from collections import deque answer = 0 tired = [[1, 1, 1], [5, 1, 1], [25, 5, 1]] connection = {"diamond": 0, "iron": 1, "stone": 2 } info = [] minerals = minerals[:5 * sum(picks)] # 곡쾡이 개수까지 슬라이싱 q = deque(minerals) # deque의 형태로 변형! while q: # 리스트 내부가 존재하는한! dig = 0 di_, ir_, st_ = 0, 0, 0 while dig < 5: dig += 1 minerals = q.popleft() di_ += tired[0][connection[minerals]] ir_ += tired[1][connection[minerals]] st_ += tired[2][connection[minerals]] if not q: break info.append([di_, ir_, st_]) info.sort(key=lambda x: [x[2], x[1], x[0]]) # 돌,철,다이아 순으로 피로도가 클수록 다이아 곡쾡이로 캤을때 이득이 많이 발생한다! for idx, p in enumerate(picks): # enumerate의 경우 순서를 알려줌! for _ in range(p): if info: # info 리스트가 존재하는 한 answer += info.pop()[idx] else: return answer return answer # 풀이 과정2 def solution(picks, minerals): from collections import deque minerals = minerals[:5 * sum(picks)] count = 0 # 광물카운트 c_d = 0 c_i = 0 c_s = 0 check = [] # 각 종류별 곡쾡이 피로도 for x in range(len(minerals)): if minerals[x] == "diamond": count += 1 c_d += 1 c_i += 5 c_s += 25 elif minerals[x] == "iron": count += 1 c_d += 1 c_i += 1 c_s += 5 elif minerals[x] == "stone": count += 1 c_d += 1 c_i += 1 c_s += 1 if count == 5 or x == len(minerals) - 1: check.append([c_d, c_i, c_s]) count = 0 c_d = 0 c_i = 0 c_s = 0 check.sort(key=lambda x: (-x[2], -x[1], -x[0])) result = 0 check = deque(check) for y in range(len(picks)): count_p = 0 while count_p < picks[y] and check: result += check[0][y] check.popleft() count_p += 1 return result

""" 프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/87391 """ # 풀이 과정 start_x, end_x = x, x start_y, end_y = y, y for i in range(len(queries) - 1, -1, -1): command, dx = queries[i] if command == 0: end_y = min(end_y + dx, m - 1) if start_y == 0: start_y = 0 else: start_y = start_y + dx if start_y > m - 1: return 0 elif command == 1: if end_y == m - 1: end_y = m - 1 else: end_y = end_y - dx if end_y < 0: return 0 start_y = max(start_y - dx, 0) elif command == 2: end_x = min(end_x + dx, n - 1) if start_x == 0: start_x = 0 else: start_x = start_x + dx if start_x > n - 1: return 0 elif command == 3: if end_x == n - 1: end_x = n - 1 else: end_x = end_x - dx if end_x < 0: return 0 start_x = max(start_x - dx, 0) return (end_x - start_x + 1) * (end_y - start_y + 1)