프로그래머스 사칙연산 배정 문제 보기 풀이 oper : operator 리스트 nums : operand 리스트 find(s,e,case) : oper의 인덱스를 기준으로 s부터 e까지 연산자를 사용했을때 만들수 있는 max(case='max'), min(case='min')값 리턴 operator를 기준으로 dp를 사용했다. 구간의 최대, 최소값을 모두 저장해야 하므로 max_dp, min_dp 2개를 사용. 구간의 최대, 최소값을 구할때 주의할점 oper[i]가 '+'일때 max = s~i까지의 max + i+1~e까지의 max min = s~i까지의 min + i+1~e까지의 min oper\[i\]가 '-'일때 max = s~i까지의 max..

프로그래머스 호텔 방 배정 문제 보기 처음 생각한 이분탐색 풀이와 코드 방의 갯수 k가 10^12 이므로 2^10(1024)를 대략 10^3으로 보면 10^12는 대략 2^40이므로 이분탐색으로 40번안으로 탐색할 수 있겠고 200,000개의 요청각각 40번 탐색이면 200,000*40 = 8,000,000이므로 시간초과에 걸리지 않을것이라고 생각했다. 하지만.. 효율성패스를 통과하지못했다. 생각해보니 남아있는 방들을 저장하고 있는 empty배열을 만들때 10^12개의 요소를 넣으며 이미 시간초과가 나버린것같다... 이분탐색 코드는 아래와 같다. def solution(k, room_number): answer = [] used = [] empty = [i for i in range(k+1)] for n..

프로그래머스 튜플 문제 보기 문제풀이 정규식을 활용하여 요소 갯수로 정렬된 리스트를 만들고 리스트에 새롭게 추가 되는 숫자를 answer에 추가하는 식으로 구현했다. [[2],[3,2],[1,3,2]] # 이런경우 2,3,1 순서로 추가되도록 Code import re def solution(s): answer = [] orderedList = [] parts = s.split("},") for part in parts: numbers = re.findall("\d+",part) orderedList.append(list(map(lambda x:int(x),numbers))) orderedList = sorted(orderedList, key = lambda x:len(x)) answer.append(i..

프로그래머스 불량 사용자 문제 보기 문제풀이 1.banned_id마다 가능한 user_id를 찾아서 matchedList를 만든다. [[1,2],[3,4],[3,4,5]] #이런식으로 각 banned_id가 될 수 있는 user_id의 idx로 matchedList를 만든다. 2.matchedList의 요소 갯수가 n일때, depth n으로 탐색하는 dfs로 조합을 만든다. 이때, 미리 matchedList를 정렬해놓고 + 조합을 set에 저장하면 중복을 없앨 수 있다. 3.set의 요소 갯수가 답이다. 정규식 사용 banned_id마다 가능한 user_id를 찾을때 정규식으로 찾았다. (dfs로 그냥 찾아도 될듯하다.) # "fr*do" 같은 경우 아래와 같이 pattern을 만들어서 정규식을 사용한다..

프로그래머스 주식가격 문제 보기 문제풀이 prices의 길이가 "10만"이기 때문에, 2중 for문으로 풀면 안된다고 생각했다. Stack을 사용하면 prices배열을 한번만 보면 되기 때문에 O(n)이 가능하다. Stack을 어떻게? prices배열에서 i(index),p(price)를 리스트로 stack에 계속 저장하는데 p가 이전의 p보다 작아지는 상황이면, stack에서 해당 p보다 큰 값들은 모두 pop()해서 index로 시간을 계산한 후 answer에 넣어준다. 그래프로 이해하면 prices 배열이 [1,2,3,4,2,3]일때 [4,2]가 나올때 [3,4], [2,3]이 pop되고 이후 [5,3]이 추가된다. pop될때 각각 index로 차이를 계산해서 answer에 넣어준다. 그 이후 st..

N으로 표현 문제보기 N과 number가 주어지면, 최소한의 갯수의 N으로 number를 만드는 문제 예를 들어, N = 5, number = 12 일때 12 = (55 + 5) / 5 이므로, 4개의 5로 12를 표현 할 수 있다. 문제풀이 set을 이용한 DP 문제로 풀 수 있다. 최대 8개의 N만 사용 가능하므로, 8개의 set을 만들고 i번째 set은 i개의 N을 사용했을 때 만들 수 있는 모든 수를 가진다. i번째 set에 들어갈 수 있는 숫자는 N을 i개 붙여서 만든 숫자 (예를 들어 N=5, i=7일때 5555555) 1번째 set과 i-1번째 set에 들어가는 숫자들 각각 끼리의 사칙연산 2번째 set과 i-2번째 set에 .. ... i/2번째 set과 i-(i/2)번째 set에 들어가는..