문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 완전 탐색으로 풀면 시간 복잡도가 $O(N^2)$이기 때문에, 다른 방법으로 접근했다. 우선, 가격이 떨어지지 않는 경우를 가정해서 초기 [ic]answer[/ic]를 설정했다. 이후 가격이 떨어진다면, 현재 시간과 해당 prices 값이 입력된 시간 사이 차이를 계산해 answer 값을 수정해야 했다. '어떻게 구하지?'라고 고민하다가 결국 다른 사람 풀이를 참고했다. # 가격이 떨어지지 않은 기간 # '초기화 - 갱신'을 어떤 방식으로 할 지 고민 # [1] -> [1, 2] -> [..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 트럭이 진입한 시간, 다리 위에서의 무게를 계산하는 과정에서 pop(0)가 많이 발생하므로 Queue를 활용했다. 트럭이 막 진입한 시간을 0초, 진입 후에 1초가 된다는 생각으로 answer 값을 활용했다. from collections import deque def solution(bridge_length, weight, truck_weights): truck_weights = deque(truck_weights) # 다리에 트럭이 진입한 시간 time_list = deque() # 현재 다리 ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 원하는 location이 나올 때까지, 프린터 대기 목록을 수정하고, 위치 정보를 유지하는 것이 핵심이다. 이를 위해서 [ic]priorities[/ic]와 [ic]location[/ic] 정보를 각각 queue에 담아 처리했다. from collections import deque def solution(priorities, location): # 위치 / 우선 순위 저장 queue = deque(range(len(priorities))) priorities = deque(priorities) a..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 배포 완료된 경우, pop(0)를 실행해야 하기 때문에 stack 대신 queue를 활용했다. 돌아보면 배포 가능한 프로그램을 굳이 담아둘 필요가 없었다. from collections import deque def solution(progresses, speeds): # 배포 / 개발 속도 progresses = deque(progresses) speeds = deque(speeds) answer = [] deploy_list = [] while progresses: # 하루 작업 진행 for i..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 [ic]([/ic] 괄호가 나올 때만 스택에 저장해뒀다가, [ic])[/ic] 괄호가 나오면 pop()을 진행해 제거했다. pop() 과정에서 런타임 오류가 발생하지 않도록, 짝이 불가능한 경우 False를 바로 반환했다. def solution(s): # 짝 확인 stack = [] for char in s: if char == "(": stack.append(char) else: # 짝 불가능 if len(stack) == 0: return False else: stack.pop() return..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 가능한 여러 경로를 얻고, 이 중에서 가장 앞서는 경로를 찾는 것이 핵심이다. 이중에서 가장 앞서는 경로를 처리하는데 어려움을 느껴 다른 사람의 풀이를 참고했다. 백트래킹 활용 현재 위치 정보를 전달해서 중복된 방문을 제한했다. [ic]path[/ic] 들을 저장해둔 [ic]answer[/ic]를 정렬하면서 가장 앞서는 경로를 얻을 수 있었다. from collections import defaultdict def solution(tickets): # 방문 여부 visited = defaultdic..

15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 나의 풀이 오름차순이라는 조건을 만족시키기 위해서 [ic]get_num[/ic] 함수를 통해 최소 값을 전달해줬다. def get_num(k, min): if k == m: print(*num_list) return # 최소 값을 전달 for i in range(min, n + 1): num_list[k] = i get_num(k + 1, i) def solution(): global n global m n, m = map(int, input().split())..

15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 나의 풀이 수열이 오름차순인지 확인하기 위해서, 정렬 전후가 같은지 체크하는 방식으로 풀었다. 답은 맞았지만, 가능성이 없는 수열도 불필요하게 계산된다는 단점이 있다. def get_num(k): # 수열이 완성된 경우 if k == m: if sorted(num_list) == num_list: print(*num_list) return # 수열에 원소 저장 for i in range(1, n + 1): if not isused[i]: num_list[k] =..

15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 나의 풀이 백트래킹 유형 기본 문제라고 하는데, 어려워서 풀이를 참고하면서 풀었다. 원소 사용 여부를 저장하는 것이 핵심이었다. def get_num(k): # 수열이 완성된 경우 if k == m: print(*num_list) return # 수열에 원소 저장 for i in range(1, n + 1): if not isused[i]: num_list[k] = i isused[i] = 1 get_num(k + 1) # 사용 후 제거 isused[i] = 0..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 단어를 변환하려면 1 글자만 달라야 하기 때문에, 이를 이용해서 그래프를 구성한 다음에 BFS로 탐색했다. from collections import deque def bfs(start, end, graph, visited): # 시작점 입력 + 방문 처리 queue = deque() queue.append([start, 1]) visited[start] = 1 while queue: node, cnt = queue.popleft() if node == end: return cnt else: for..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 최단 거리를 구하기 위해서 BFS를 활용했다. # 최단 거리 반환 from collections import deque def bfs(maps, x, y): # 다음에 방문할 지점 저장 next_visit = deque() next_visit.append([x, y]) # 방향 설정 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # 방문 시작 while next_visit: x, y = next_visit.popleft() # 이동 for i in range(4): ..

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 기존에 DFS, BFS를 시뮬레이션에서만 활용했어서 간단한 문제임에도 못 풀었다. DFS를 활용할 때, 어떤 값을 넘겨줄 지가 정확히 설계하는 것이 중요함을 깨달았다. DFS를 재귀, stack 방식 모두를 활용해 구현해봤다. from collections import deque def dfs(num_sum: int, idx: int, max_idx: int, numbers: list, target: int): global answer # DFS 진행 동안 answer 값 증가 if idx == m..