문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 $k$개의 점수만 기록하려면 점수를 정렬해서 관리하는 것이 필요하다. $k$일 이후에는 가장 작은 값 1개만 제거하면 되기 때문에 우선 순위 큐를 사용해 시간 복잡도를 줄였다. 우선 순위큐의 push, pop의 시간 복잡도는 $O(\log N)$이다. import heapq def solution(k, score): answer = [] # 최하 점수만 확인하면 되기 때문에 heapq 사용 heap = [] for i in score: heapq.heappush(heap, i) # 개수 ..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 박스에 담을 사과 개수가 $m$으로 고정돼 있어 내림차순 정렬만으로도 최대 가격을 설정할 수 있다. 내림차순으로 정렬하게 되면 매번 $m$ 번째 사과의 점수가 전체 사과 상자의 가격을 결정한다. # 점수가 가장 낮은 사과가 가격을 결정 # 따라서 점수가 높은 사과끼리 묶어야 최대 가격 설정 가능 def solution(k, m, score): answer = 0 score.sort(reverse = True) # idx 대소 비교 과정에서 계속 계산되기 때문에 미리 계산 score_len..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 아직 문자가 나오지 않은 경우엔 $-1$ 값을 가지기 때문에 초기 answer 성분을 -1로 설정했다. def solution(s): char_set = {} # -1로 초기화 answer = [-1] * len(s) for i, char in enumerate(s): # 문자가 이미 나온 경우 if char in char_set: answer[i] = i - char_set[char] # 위치 정보 업데이트 char_set[char] = i return answer

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 동일한 메뉴가 양쪽에 위치하려면, 메뉴가 짝수개만큼 있어야 한다. 문자열은 sequence type이기 때문에 slicing이 가능하다. # -> 물

문제 확인하기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 a개의 콜라를 제출해서 1개의 콜라를 받는다고 가정하면, N개의 콜라는 Q 번 교환하는데 사용된 콜라와, 교환에 활용되지 못한 R 개의 콜라로 표현할 수 있다. Q번의 교환을 통해 얻을 수 있는 콜라의 개수는 콜라 교환비 값인 b를 곱해주면 된다. # 몫 : 새로 받을 콜라 개수, 나머지 : 남은 콜라 개수 def solution(a, b, n): answer = 0 # 교환 가능할 때 까지 실행 while n >= a: q, r = divmod(n, a) # 교환 비가 1보다 큰 경..

14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 나의 풀이 +, -,*, / 연산자 각 원소의 개수에 맞춰서 인덱스 리스트를 만들어서 저장했다. 이후 인덱스 리스트로 순열을 만들어서 완전 탐색을 진행해서 풀었다. 순열을 직접 구현하고 사용해보려고 이런 방식으로 풀었는데, itertools의 permutations 함수를 사용하면 통과가 되지만 구현한 수열 함수로는 시간 초과가 발생한다. def get_perm(arr, n): perm_list = [] # ..

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 나의 풀이 오랜만에 푸는 DP 문제이다. 고민하다가 못 풀어서 결국 풀이를 참고했다. 각 날짜 별 최대 이윤을 DP 테이블로 구성하고, 최대 이윤 값을 얻을 땐 뒤쪽 날짜부터 거꾸로 진행해서 계산해야 한다. 이렇게 되면 DP[i] = max(현재 상담 일자의 최대 이윤 + 현재 상담이 끝난 후를 기준으로 한 최대 이윤, 기존 최댓값)으로 표현이 가능하다. n = int(input()) # 전체 상담 개수 t_list = [] # 상담 완료까지 기간 p_list = [] # 상담 완료 시 받을 수 있는 금액 dp = [0] * (n + 1) max_value = 0 for _ in range(n): t..

13458번: 시험 감독 첫째 줄에 시험장의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 각 시험장에 있는 응시자의 수 Ai (1 ≤ Ai ≤ 1,000,000)가 주어진다. 셋째 줄에는 B와 C가 주어진다. (1 ≤ B, C ≤ 1,000,000) www.acmicpc.net 나의 풀이 우선 총 감독을 1명씩 배치하고, 이후 보조 감독을 배치했다. 보조 감독 배치는 몫의 값 만큼 진행하고, 나머지가 0이 아닌 경우 1명씩 추가로 배지했다. import sys N = int(input()) A_list = list(map(int, sys.stdin.readline().split())) B, C = map(int, input().split()) # 총 감독 배치 answer = 0 ..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. 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..