-
""" 출처:프로그래머스 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
-
""" 출처:프로그래머스 https://school.programmers.co.kr/learn/courses/30/lessons/67259 """ # 풀이 과정 """ 0:비어있음 1:벽이 있음 start:(0,0) destination:(n-1,n-1) 목표: 최소 비용으로 건설하기 생각 방향: 게임 보드를 활용 > bfs or dfs """ from collections import deque import copy import heapq # 수직 확인 def check(direction, direc): # 수직 여부 P = False if direction == "up" or direction == "down": one = True else: one = False if direc == "up" or direc == "down": two = True else: two = False if one == two: return P else: return True def solution(board): result = float("inf") b = board # 행,열 m = len(board) n = len(board[0]) # [[0, 1], [1, 0], [-1, 0], [0, -1]]; # 방향성 확인 dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] d = ["right", "left", "down", "up"] # {"right":float("inf"),"left":float("inf"),"down":float("inf"),"up":float("inf")} cost_table = [[0] * len(board[0]) for i in range(len(board))] for i in range(len(b)): for j in range(len(b)): cost_table[i][j] = {"right": float("inf"), "left": float("inf"), "down": float("inf"), "up": float("inf")} # 현 위치(x,y), 방향,비용 q = [(0, (0, 0), "stop")] while q: cost, location, direction = heapq.heappop(q) # 위치 x, y = location[0], location[1] if x == m - 1 and y == n - 1: cost_table[x][y][direction] = min(cost, cost_table[x][y][direction]) continue # # 방문처리 # if cost_table[x][y]<cost-600: # continue # else: # cost_table[x][y]=cost for nx, ny, direc in zip(dx, dy, d): # 해당판 내부 확인 if 0 <= x + nx < m and 0 <= y + ny < n: if board[x + nx][y + ny] == 0: # 방향성 체크 if direction == "stop": heapq.heappush(q, (cost + 100, (x + nx, y + ny), direc)) cost_table[x + nx][y + ny][direc] = cost + 100 else: p = check(direction, direc) if p == True: if cost_table[x + nx][y + ny][direc] < cost + 600: continue # 수직 + 직선 거리도 이동 heapq.heappush(q, (cost + 600, (x + nx, y + ny), direc)) cost_table[x + nx][y + ny][direc] = cost + 600 else: if cost_table[x + nx][y + ny][direc] < cost + 100: continue heapq.heappush(q, (cost + 100, (x + nx, y + ny), direc)) cost_table[x + nx][y + ny][direc] = cost + 100 result = float("inf") for i in cost_table[len(b) - 1][len(b) - 1].values(): result = min(result, i) return result
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/176962 """ # 풀이 과정 def solution(plans): result = [] # 결과 check = [] # 현재 진행중인 과제 remain = [] # 남겨둔 과제 time = 0 # 현재 시간 plans.sort(key=lambda x: (x[1].split(":")[0], x[1].split(":")[1])) # 시작 시간에 따른 정렬 print(plans) for x in plans: if len(check) < 1: check.append(x) work_start = check[0][1].split(":") work_minute = int(work_start[0]) * 60 + int(work_start[1]) time = work_minute work_check = int(work_start[0]) * 60 + int(work_start[1]) + int(check[0][2]) else: new_work = x[1].split(":") new_work_time = int(new_work[0]) * 60 + int(new_work[1]) if new_work_time < work_check: remain_work_time = work_check - new_work_time remain.insert(0, [check[0][0], remain_work_time]) check.pop() check.append(x) work_start = check[0][1].split(":") work_minute = int(work_start[0]) * 60 + int(work_start[1]) time = work_minute work_check = int(work_start[0]) * 60 + int(work_start[1]) + int(check[0][2]) else: result.append(check[0][0]) check.pop() time = work_check while True: # 공백 시간 과제 가능한지 체크 if len(remain) == 0: break elif time + remain[0][1] <= new_work_time: time = time + remain[0][1] result.append(remain[0][0]) remain.pop(0) elif time + remain[0][1] > new_work_time: remain[0][1] = abs(new_work_time - (time + remain[0][1])) time = new_work_time break check.append(x) work_start = check[0][1].split(":") work_minute = int(work_start[0]) * 60 + int(work_start[1]) work_check = int(work_start[0]) * 60 + int(work_start[1]) + int(check[0][2]) result.append(check[0][0]) final = [v for v, w in remain] result = result + final return result
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12907 """ def solution(n, money): dp = [0] * (n + 1) dp[0] = 1 for m in money: for now in range(m, n + 1): if now >= m: dp[now] += dp[now - m] return dp[n] % 1000000007
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/1844 """ #풀이과정 from collections import deque def solution(maps): q = deque([[0, 0, 1]]) visit = [[False] * len(maps[0]) for _ in range(len(maps))] dx = [1, -1, 0, 0] dy = [0, 0, 1, -1] while q: x, y, z = q.popleft() visit[x][y] = True for new_x, new_y in zip(dx, dy): if 0 <= x + new_x < len(maps) and 0 <= y + new_y < len(maps[0]) and visit[x + new_x][y + new_y] == False and \ maps[x + new_x][y + new_y] != 0: q.append([x + new_x, y + new_y, z + 1]) visit[x + new_x][y + new_y] = True if visit[len(maps) - 1][len(maps[0]) - 1] == True: return z + 1 return -1
