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

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/60058 """ # 풀이과정 # 균형잡힌 괄호 문자열인지 체크하는 함수 def isbalanced(s): chk=0 for c in s: if c=='(': chk+=1 elif c==')': chk-=1 if chk==0: return True else: return False # 올바른 괄호 문자열인지 체크하는 함수 def iscorrect(s): stack=[] stack.append(s[0]) for i in range(1,len(s)): if len(stack)==0 or stack[-1]==')' or (stack[-1]=='(' and s[i]=='('): stack.append(s[i]) else: stack.pop() if len(stack)==0: return True else: return False def solution(p): answer = '' u="" v="" #빈 문자열이나 올바른 괄호 문자열은 그대로 반환 if len(p)==0 or iscorrect(p): return p #u가 균형잡힌 괄호 문자열이 될 때까지 2개씩 추가해서 u,v 나누기 for i in range(2,len(p)+1,2): if isbalanced(p[0:i]): u=p[0:i] v=p[i:len(p)] break if iscorrect(u): #u가 올바른 괄호 문자열일 때 answer+=u+solution(v) else: #u가 올바른 괄호 문자열이 아닐 때 answer+='('+solution(v)+')' for c in u[1:-1]: if c=='(': answer+=')' else: answer+='(' return answer

""" 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/131702 """ # 풀이과정 # 조건: 시계 방향으로만 돌리는거 가능, 한 번당 90도 단 상하좌우도 같이 돌아간다 # 모서리 3개만 돌아감 꼭짓점:2개 돌아감 # 시계 0:12 1:3 2:6 3:9 # 해결 가능한 퍼즐만 주어집니다. # 행과 열의 길이는 동일 # 목표: 최소한의 횟수로 퍼즐 해결 # 생각의 흐흠 및 방향성 변화 # 생각방향: 각각의 모든 수는 3번을 초과하지 않는다(제자리로 돌아가기 때문이다) # 주어진 조건을 봤을 때 완탐으로해도 시간초과 발생 가능성 적음 # for문을 바탕으로 전체를 둘러본 후 주변이 해당 시계를 포함하여 주변이 전부 0이 아닐경우 실행 # 그리고 만약 해당 시계를 바꿨음에도 주변이 모두 0 아닐경우 하나라도 0일 경우 stop # 완탐의 경우 모든 시계 내 원소가 0 1 2 3 중 하나라는 생각접근 # 각 칸의 돌려지는 횟수가 총합으로 각 칸이 돌려져야 될 횟수를 4로 나눴을때 나머지 횟수랑 동일해야한다. # 최대 경우의 수를 만든 후 직접 계산 시 시간 초과 4**64가지이기 떄문이다. 중복 순열 # 줄일 방법을 고민하기 or 새로운 접근 방향 고민 # 포인트 사고: 하나의 줄을 고정! 고정된 줄을 중심으로 나머지 줄의 돌릴 수도 정해진다 # 하나씩 고정시키면 자연스럽게 위에 맞춰서 아래가 정해진다!! 경우의 수도 첫줄 경우의 수이다 4**8가 최대가 된다 # 원순열 기본 원리랑 비슷 고정시킨 후 원형으로 만든 후 경우의 수 표현하는 방식 # 시계 돌리기 import copy from itertools import product from collections import deque def clock(new, a, b, t, l): dx = [1, -1, 0, 0, 0] dy = [0, 0, 1, -1, 0] for i, j in zip(dx, dy): if 0 <= a + i < l and 0 <= b + j < l: # t: 돌릴 횟수 new[a + i][b + j] = (new[a + i][b + j] + t) % 4 return new def solution(clockHands): result = [] c = clockHands l = len(c) # 목표 모양 target = [[0] * l for _ in range(l)] # 맨 윗줄 고정 시킬 회전 수 경우의 수 중복 순열 check = deque(list(product(range(4), repeat=l))) while check: # 회전 시킬판 deepcopy 대신 시간복잡도가 덜 드는 슬라이싱 활용! new=copy.deepcopy(c) #new = [i[:] for i in c] # 기준점이 돌아가는 횟수 count = 0 # 고정 시킬 첫줄 회전 횟수 체크 k = check.popleft() # k[i]: 첫 줄 i번째 회전시킬 횟수 for i in range(l): # 해당 지점 돌리기 # new[0][i]=change[(new[0][i]+k[i])%4] count += k[i] # 동서남북 바꾸기 new = clock(new, 0, i, k[i], l) for v in range(1, l): for w in range(l): if new[v - 1][w] != 0: # 위를 0으로 만들기 위한 돌릴 횟수 지정 x = 4 - new[v - 1][w] # 해당 지점 돌리기 # new[v][w]=(new[v][w]+x)%4 count += x # 동서남북 바꾸기 new = clock(new, v, w, x, l) else: continue # 목표한 모양과 같은 경우 기록 (맨 아래가 다를 수 있기 떄문이다) if sum(new[l - 1]) == 0: result.append(count) # print(new) return min(result) if len(result) > 0 else 0

""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/76502 """ # 풀이 과정 def solution(s): from collections import deque result = 0 count = 0 k = deque(list(s)) check = [] open_ = ["[", "(", "{"] close_ = ["]", ")", "}"] if len(s) == 1: return 0 while count < len(s): if k[-1] in open_ or k[0] in close_: a = k.popleft() k.append(a) count += 1 else: check = [] flag = False for b in k: if b in open_: check.append(b) elif b in close_: if len(check) == 0: flag = True break else: c = close_.index(b) d = open_.index(check[-1]) if c == d: check.pop() else: break if len(check) == 0: if flag == False: result += 1 a = k.popleft() k.append(a) count += 1 else: a = k.popleft() k.append(a) count += 1 return result