그동안 프로그래머스 level1, level2를 풀었고, 이제는 자료구조 및 알고리즘 기준으로 문제를 풀기 위해 프로그래머스 코딩테스트 고득점 kit을 풀어보려한다.
배열 array가 주어지고 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려 한다.
- ex) arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
def solution(arr):
answer = []
answer.append(arr[0])
for i in range(1, len(arr)):
if arr[i] != answer[-1]:
answer.append(arr[i])
else:
continue
return answer
< 풀이 과정 >
answer에 우선 주어진 배열의 0번째 인덱스 값을 집어넣고 1부터 arr길이만큼 순회하며 answer에 끝 값과 같지 않은 경우에만 answer에 추가해준다.
작업 개수(progresses, speeds) 가 주어지고 각 작업(기능)은 100%의 진도일 때 서비스에 반영할 수 있다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 progresses와 각 작업의 개발속도가 적힌 speeds배열로 동일하게 소요된 날짜만큼의 결과를 리턴하는 문제
def solution(progresses, speeds):
answer = []
day = 0
while progresses:
if progresses[0] + speeds[0] >= 100:
day += 1
progresses.pop(0)
speeds.pop(0)
else:
for i in range(len(speeds)):
progresses[i] += speeds[i]
if day:
answer.append(day)
day = 0
answer.append(day)
return answer
< 풀이 과정 >
progresses가 빌 때까지 progresses+speeds의 0번째 인덱스 값이 100을 넘어야 다음 작업을 할 수 있으므로 100을 넘는다면, 날짜 +1, progresses 작업 완료 처리를 위해 pop해준다.
만일, 100을 넘지않는다면 각 작업에 개발속도를 더해주고, day가 0이 아니라면 answer에 집어넣고 다시 0으로 처리해준다.
최종적으로 100이 넘는 경우 day + 1 이후 answer에 append하여 마지막 작업의 완료도 반영한다.
괄호로 이루어진 문자열을 입력받는데, 괄호가 () 형태로 닫히면 true를, 아닌 경우 False를 리턴한다.
def solution(s):
stack = []
for i in s:
if i == '(':
stack.append(i)
else:
if stack:
stack.pop()
else:
return False
if stack:
return False
return True
< 풀이 과정 >
스택을 이용하여 간단하게 구현할 수 있다.
문서 별 중요도를 나타낸 배열이 주어지고, 내가 인쇄를 요청한 문서의 위치정보가 담긴 숫자를 통해 몇번째로 인쇄되는가를 묻는 질문
ex) 2 1 3 2로 문서 별 중요도가 주어지고, 내가 인쇄를 요청한 문서의 위치정보가 2인 경우 중요도 3인 문서가 제일 먼저 나오게 되므로 결과는 첫번째, 즉 1이다.
def solution(priorities, location):
# 변화하는 문서 위치 정보로 인해 copy 사용해 리스트 생성
wait_list = priorities.copy()
# 인덱스 느낌
importance = 0
# 문서 별 인덱스 부여 및 저장
idx = [i for i in range(len(priorities))]
while True:
# 현위치보다 더 중요도가 높은게 뒤에 있다면 맨 앞에 값 뒤로 보내기
if wait_list[importance] < max(wait_list[importance+1:]):
wait_list.append(wait_list.pop(importance))
idx.append(idx.pop(importance))
else:
importance += 1
# 정렬된 것과 일치하면 중단
if wait_list == sorted(wait_list, reverse = True):
break
# 앞서 저장한 idx리스트의 location값이 있는 위치 + 1 리턴
answer = idx.index(location)+1
return answer
< 풀이 과정 >
priorities를 그대로 사용하게 되면, 정렬된 것과 비교를 할 수 없으므로 copy를 사용해 리스트를 새로 만든다.
다리에 올라갈 수 있는 트럭 수, 다리가 견딜 수 있는 무게, 트럭 별 무게가 주어지고 이를 통해 모든 트럭이 다리를 건너는데 소요된 최소 시간을 구하는 문제
def solution(bridge_length, weight, truck_weights):
answer = 0
bridge = [0 for _ in range(bridge_length)]
while bridge:
answer += 1
bridge.pop(0)
if truck_weights:
if sum(bridge) + truck_weights[0] <= weight:
truck = truck_weights.pop(0)
bridge.append(truck)
else:
bridge.append(0)
return answer
< 풀이 과정 >
bridge라는 스택을 만들어주고, bridge가 빌때까지 진행한다.
진행을 한 번 할 때마다 1초가 소요되므로 answer + 1, bridge 맨 앞 부분 제거 해주고, truck_weights가 비어있지 않는 경우에 한해서 bridge 내의 트럭 무게 합 + 다음 트럭 무게를 더해 weight보다 작으면 bridge에 다음 트럭을 이동시키고, 아닌 경우 0을 다시 추가해준다.
초 단위로 주식가격이 담긴 prices가 주어질 때 가격이 떨어지지 않은 시간을 구하는 문제
def solution(prices):
answer = [0] * len(prices)
for i in range(len(prices)):
for j in range(i+1, len(prices)):
if prices[i] <= prices[j]:
answer[i] += 1
else:
answer[i] += 1
break
return answer
< 풀이 과정 >
answer를 prices길이만큼의 0을 가진 배열로 만든 다음, 2중 for문으로 범위를 지정해 j가 항상 i보다 크도록 만들어 i번째 인덱스보다 j번째 인덱스가 크다면 answer[i] + 1을 해준다.
만일 i번째 인덱스가 j번째 인덱스보다 커도 +1을 해주는데, 그 이유는 3>2로 가격이 떨어질 경우를 보면 1초뒤에 가격이 떨어지는 것이고 1초간 가격이 떨어지지 않은 것으로 보기 때문이다.
음식의 스코빌 지수를 담은 배열과 원하는 스코빌 지수 k가 주어질 때 배열이 모두 스코빌 지수 k를 넘기 위해 섞어야 하는 최소 횟수를 구하는 문제
섞는 조건은 가장 맵지 않은 음식의 스코빌지수 + 두번째로 안매운 음식*2이다.
import heapq
def solution(scoville, k):
answer = 0
heapq.heapify(scoville)
while scoville[0] < k:
mixing = heapq.heappop(scoville) + heapq.heappop(scoville)*2
heapq.heappush(scoville, mixing)
answer += 1
if scoville[0] < k and len(scoville) == 1:
return -1
return answer
< 풀이 과정 >
heapq 모듈을 활용하여 우선 주어진 scoville 리스트를 힙 자료구조로 변환해준다.
그 이후 scoville의 첫번째 인덱스는 가장 작은 값이므로, 이 값이 k 보다 작은 경우를 while문으로 반복해준다.
반복 시 주어진 조건대로 섞은 결과 mixing을 heap에 집어넣는 횟수를 answer + 1 해주고, 모든 조건을 실행했는데도 k보다 작다면 -1을 리턴하고 아니면 answer를 리턴한다.
주어진 operation은 다음 명령어를 가지고 있다.
- I 숫자 : 큐에 주어진 숫자 삽입
- D 1 : 큐에서 최댓값을 삭제
- D -1 : 큐에서 최솟값을 삭제
이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때 모든 연산 처리 후 큐가 비어있다면 [0,0]을 아니면 [최대, 최소]를 리턴하는 문제
import heapq
def solution(operations):
answer = []
for i in operations:
alpha, num = i.split()
num = int(num)
if alpha == 'I':
heapq.heappush(answer, num)
elif answer:
if num == -1:
heapq.heappop(answer)
else:
answer.remove(max(answer))
if not answer:
return [0, 0]
else:
return [max(answer), answer[0]]
< 풀이 과정 >
heapq 모듈 사용하여 구현한 풀이.
우선 operations를 for문으로 순회하여 주어진 I,D 와 num을 split하여 입력받는다.
하드디스크는 한 번에 하나의 작업만 수행할 수 있다.
각 작업에 대해 [작업 요청시점, 작업 소요시간]을 담은 2차원 배열 jobs가 주어질 때 작업 요청 ~ 종료까지 걸린 시간의 평균을 가장 줄이는 방법을 골라 그 평균이 얼만지 출력하는 문제.
작업 요청시점이 더 뒤에 있어도, 작업 소요시간이 더 짧다면 먼저 수행하는 것이 평균을 줄일 수 있다. 또한 하드디스크가 작업을 수행하지 않고 있다면 먼저 요청이 들어온 작업부터 처리를 진행한다.
import heapq
def solution(jobs):
# 시점, 시간 정보 변수 저장
point, time = 0, 0
# jobs이 다 비면 길이를 알 수 없기에 미리 세팅
n = len(jobs)
# jobs 내역이 없을 때까지 반복
while jobs:
# 현 시점보다 작거나 같은 작업 리스트 저장
wait_list = [x for x in jobs if x[0] <= point]
# 동일 시점의 경우, 작업 소요시간이 적은 것부터 실행하기 위해 오름차순 sorting
wait_list.sort(key = lambda x: x[1])
# 남은 작업들 저장
rest_list = [x for x in jobs if x[0] > point]
# 작업 가능한 것이 있으면
if wait_list:
# heap으로 뽑고 현 시점 + 해당 작업 소요시간, 총 소요시간 + 현 시점 - 해당 작업 요청시점
x = heapq.heappop(wait_list)
point += x[1]
time += point - x[0]
else:
point += 1
# 다음 작업 처리 위해 jobs 생성
jobs = wait_list + rest_list
answer = time // n
return answer
< 풀이 과정 >
입력 값인 jobs가 [작업 요청시점, 소요시간]으로 구성되어 있고, 작업 별로 해당 2개의 정보가 연결되어 있으므로 point, time 두 변수를 미리 지정한다.
jobs가 빌 때까지 반복하여 wait_list와 rest_list를 point(요청시점)을 기준으로 나눈 후 작업할 목록들인 wait_list는 소요시간을 기준으로 오름차순 정렬한다.
작업대상인 wait_list에 작업이 존재하면, point와 time을 해당 작업한 이후만큼 변경해준다.
이후 총 소요시간을 jobs 길이만큼 나눈 것을 리턴한다.