문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 약수의 개수는 약수의 정의와 소인수 분해의 성질로 확인할 수 있다. 약수(소인수)를 찾기 위해서 1(2) ~ N까지 전부 확인할 경우, 시간 복잡도는 $O(N^2)$이 돼 시간 초과가 발생한다. 약수(소인수) 탐색은 $\sqrt N$ 만큼만 확인해도 되는 점을 활용하면, 시간 복잡도를 $O(N\sqrt N)$으로 줄일 수 있다. from collections import defaultdict # 성분의 곱을 계산할 수 있다. from math import prod # 약수 개수 구하기 1..

문제 확인 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 나의 풀이 공통된 숫자를 미리 확인한 뒤 필요한 숫자만 개수를 확인했다. 하지만 확인할 숫자의 개수가 10개 뿐이어서 굳이 그럴 필요는 없었던 거 같다. 0이 여러번 반복되는 문자열을 처리하기 위해서 정규 표현식을 사용 했다. from collections import Counter import re def solution(X, Y): answer = "" # 문자열로 변경 X, Y = map(str, (X, Y)) # 공통 숫자 확인 com_num = sorted(set(X) & set(Y), r..

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

조합 def get_comb(arr, n): comb_list = [] # 종료 조건 if n == 0: return [[]] # 현재 arr의 담긴 수를 확인 for i in range(len(arr)): # 선택된 수 num = arr[i] # 나머지 수로 구성된 배열 arr_left = arr[i+1:] for comb in get_comb(arr_left, n - 1): comb_list.append([num] + comb) return comb_list 순열 def get_perm(arr, n): perm_list = [] # 종료 조건 if n == 0: return [[]] # 현재 arr의 담긴 수를 확인 for i in range(len(arr)): # 선택된 수 num = arr[i] ..

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 ..

기본 연산 [ic]SUM[/ic], [ic]COUNT[/ic], [ic]AVG[/ic] : 합, 개수, 평균 [ic]ROUND[/ic](숫자, 반올림할 자릿수) : 자릿수를 기준으로 반올림 [ic]TRUNCATE[/ic](숫자, 버림할 자릿수) : 자릿수를 기준으로 버림 [ic]CEIL[/ic], [ic]FLOOR[/ic] : 정수화(올림, 버림) [ic]POW[/ic], [ic]SQRT[/ic] : 거듭 제곱, 제곱근 The Blunder | HackerRank Query the amount of error in Sam's result, rounded up to the next integer. www.hackerrank.com SELECT CEIL(AVG(SALARY) - AVG(REPLACE(CAST..