본문 바로가기

algorithm/coding test14

프로그래머스 - 큰수만들기 (파이썬) number에서 k개의 숫자를 삭제해서 만들 수 있는 최대한 큰수를 만들어야 한다. number을 앞에서부터 돌면서 i+1번째 인덱스의 숫자가 i번째 인덱스보다 크면 앞에 숫자를 삭제해 주고 k를 1 감소시켰다. number을 한바퀴 돌아도 k가 남아있다면 number에 있는 숫자중 가장 작은값을 없애는 방식으로 k를 1씩 감소시켰다. def solution(number, k): answer = '' i=1 while(k>0): if number[i]>number[i-1]: number=number[:i-1]+number[i:] k-=1 if i>1: #i-1번째 인덱스를 제거했으므로 i번째 인덱스는 i-1번째 인덱스가 됨 i-=1 else: i+=1 if len(number)==i: break whil.. 2024. 4. 15.
프로그래머스 - 2xn타일링 (파이썬) 1. 조합사용(x) 가능한 경우의 수를 조합을 사용해서 풀어보았다. nCr을 풀기위해 nPr/r!을 만들었는데 n이 일정값 이상이 되면 nPr이 int형 범위를 벗어나 오버플로우 현상이 발생함을 확인했다. def comb_len(n,r): top,bottom=1,1 if n-r=0): answer+=(comb_len(n,one_len)) n-=1 one_len-=2 return answer 2. 피보나치수열 사용(dp) n값을 1부터 5까지 설정하여 answer을 구해보았다 n=1 -> answer=1 n=2 -> answer=2 n=3 -> answer=3 n=4 -> answer=5 n=5 -> answer=8 피보나치 수열을 이루므로 n이 3 이상일 때 앞에 두 값을 더해서 구해주었다. def so.. 2024. 4. 15.
프로그래머스 - 다리를지나는트럭 (파이썬) list를 que처럼 사용하여 풀기 def solution(bridge_length, weight, truck_weights): answer = 0 tot=0 que_i=0 que=[0]*bridge_length for truck_weight in truck_weights: tot-=que.pop(0) #맨 앞에 que값 다리를 건넘 while(tot+truck_weight>weight): #다리에 있는 트럭 무게가 weight보다 클경우 que.append(0) #0을 추가시키고 answer+=1 tot-=que.pop(0) #맨 앞에 que값 빼기 tot+=truck_weight que.append(truck_weight) #que맨뒤에 트럭의 무게 넣기 answer+=1 answer+=bridge_.. 2024. 4. 15.
프로그래머스 - 택배상자 (파이썬) 스택과 큐 사용 def solution(order): answer = 0 i_order=0 #현재 orderd의 인덱스 i_que=0 #큐의 앞에 값을 하나씩 없애면 시간복잡도 O(n)이기 때문에 값 없애지 않고 인덱스 증가시킴 que=[] stack=[] for i in range(1,len(order)+1): que.append(i) while i_order 2024. 4. 14.
프로그래머스 - 숫자변환하기 (파이썬) 이 문제는 범위에 제한이 있어야 풀리는 문제이다. dfs나 bfs를 사용하면 depth, width가 무한정 커질 수 있기 때문에 배열을 사용하여 범위에 제한을 두고 for문을 돌려야 한다. 1. dfs 사용(x) answer=1000000 def dfs(x,n,y,tot,cnt): global answer if tot>=x: if tot==x: answer=min(answer,cnt) return if tot%3==0: dfs(x,n,y,tot//3,cnt+1) if tot%2==0: dfs(x,n,y,tot//2,cnt+1) dfs(x,n,y,tot-n,cnt+1) def solution(x, y, n): global answer dfs(x,n,y,y,0) if answer==1000000: retu.. 2024. 4. 14.
프로그래머스 - 호텔 대실 (파이썬) 1. heapq 사용 heapq를 사용하면 우선순위큐처럼 값을 저장 시 오름차순으로 정렬되는 장점이 있다. 먼저 book_time 배열의 시간,분 값을 분단위로 합친후 대실시작시간을 기준으로 정렬한다. heapq를 사용하여 queue를 만든다. 방 개수만큼 큐 인덱스가 늘어나고, 해당 방의 대실 종료시간이 값으로 들어간다. queue에 값이 없거나 queue의 첫번째 값이 대실시작시간보다 크면 queue에 book_time의 대실 종료시간+10을 queue에 넣는다. 그렇지 않다면 queue에서 첫번째 인덱스를 빼고 해당 book_time의 대실 종료시간+10을 queue에 넣는다.( 해당 방을 book_time[i]가 빌릴 수 있으므로 방을 하나 늘리지 않고 해당 방의 대실종료시간을 업뎃하는 의미로 생.. 2024. 4. 14.

티스토리툴바