-
""" 출처:프로그래머스, 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)
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12985 """ # 풀이 과정 def solution(n, a, b): from collections import deque k = deque([a for a in range(1, n + 1)]) answer = 1 # 라운드 if a > b: b, a = a, b next_ = [] count = 0 while True: blue = k.popleft() red = k.popleft() if blue == a and red == b: return answer else: if blue == a or blue == b: k.append(blue) else: k.append(red) if blue == a or blue == b or red == a or red == b: count += 1 if count == 2: answer += 1 count = 0 return answer
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/258705 """ # 풀이 과정 # 일정 규칙성을 지닌 것으로 판단되어 점화식>dp 생각 접근 # 점화식 찾기 # 위에 삼각형이 있나 없나 여부에 따른 점화식의 변화 # 직전한을 수가 아닌 모양으로 표현해서 규칙성 찾아보기! def solution(n, tops): reuslt = 0 dp = [0] * (n + 1) # 0~n # case 분류 # \\ 실행 여부로 구분! i = [0] * (n + 1) # 실행 j = [0] * (n + 1) # 비실행 i[0] = 0 j[0] = 1 # 두번 째 항 if tops[0] == 1: i[1] = 1 j[1] = 3 else: i[1] = 1 j[1] = 2 for k in range(1, n): if tops[k] == 1: i[k + 1] = (i[k] + j[k]) % 10007 j[k + 1] = (i[k] * 2 + j[k] * 3) % 10007 else: i[k + 1] = (i[k] + j[k]) % 10007 j[k + 1] = (i[k] + j[k] * 2) % 10007 return (i[n] + j[n]) % 10007
-
""" 출처:프로그래머스, https://school.programmers.co.kr/learn/courses/30/lessons/12981 """ # 풀이 과정 def solution(n, words): count = 1 all_count = 1 check = [] for k in range(len(words)): if k == 0: check.append(words[k]) count += 1 continue if check[-1][-1] == words[k][0] and not words[k] in check: check.append(words[k]) if count < n: count += 1 all_count += 1 else: count = 1 all_count += 1 else: return [count, int(all_count / n) + 1] return [0, 0]
-
""" 출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/92345 """ # 풀이 과정 # 조건 # 발판 있는 곳 없는 곳 존재 # 밟던 발판 다른 곳으로 이동 시 사라짐 # 양 플레이어 상하좌우로 움직임 # 움직일 발판이 없는 경우 or 밖으로 넘어가는거 포함 패배 # 같은 발판에 존재 가능 # 같은 발판에 있다 둘중 한 플레이어가 이동하여 해당 발판이 사라지면 다른 플레이어 패배 # 시작: 플레이어 a 시작 # 항상 이길 수 있는 플레이어 패배하는 플레이어가 정해져 있음 # 항상 이기는 플레이어는 실수하지 않고 항상 지는 플레이어는 최대한 버티는 방향으로 했을 때 최적값 구하기 # 목표: 양플레이어가 최적으로 움직였을 때 횟수의 합 # 생각 방향: 보드 게임 bfs or dfs 접근 # 각 플레이어가 최적으로 움직이는 부분을 구현 핵심 누가 항상 이기는 플레이어인지 확인하기 # 최적이란? 이기는 플레이는 이길 수 있는 방향으로 지는 플레이어는 무조건 버티도록 하는 방향성 고민 # 항상 이기는 플레이어의 조건 # min,max 알고리즘 및 dfs 활용 # board: 보드 상태 aloc:a의 위치 bloc:b의 위치 dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] game = [] # 게임판 진행 상황 def start(ax, ay, bx, by, board, m, n): global game if game[ax][ay] == 1: return 0 count = 0 for x, y in zip(dx, dy): new_x = ax + x new_y = ay + y # 범위 밖 또는 해당판 존재x if not 0 <= new_x < m or not 0 <= new_y < n or board[new_x][new_y] == 0 or game[new_x][new_y] == 1: continue # 해당 말 움직였으므로 해당판 존재사라짐 game[ax][ay] = 1 # dfs 구현 # a의 말이 움직인 후에 같은 방식으로 b의 말이 움직임 enemy = start(bx, by, new_x, new_y, board, m, n) + 1 # 그 다음 for문을 위해 원복 game[ax][ay] = 0 if count % 2 == 0 and enemy % 2 == 1: count = enemy elif count % 2 == 0 and enemy % 2 == 0: count = max(count, enemy) elif count % 2 == 1 and enemy % 2 == 1: count = min(count, enemy) return count def solution(board, aloc, bloc): global game m = len(board) # 열 n = len(board[0]) # 행 ax, ay = aloc[0], aloc[1] bx, by = bloc[0], bloc[1] # 게임판 진행 상황 체크 game = [[0] * n for _ in range(m)] result = start(ax, ay, bx, by, board, m, n) return result
