Coding Test stack & queue, Heap

김태준·2023년 3월 2일
0

Coding Test - Programmers

목록 보기
13/29

그동안 프로그래머스 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

< 풀이 과정 >
스택을 이용하여 간단하게 구현할 수 있다.

  • for문으로 s를 돌며 i가 '('인 경우 스택에 집어넣고, i가 ')'인 경우는 두가지로 나눈다.
    stack이 비어있지않으면 스택에 (가 있는 것을 의미하므로 pop해주고, 아닌 경우 False를 리턴한다.
    추가로, for문을 다돌고나서 stack에 값이 있으면 False를 리턴하고 없으면 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초간 가격이 떨어지지 않은 것으로 보기 때문이다.

✅ Heap

🎈 더 맵게

음식의 스코빌 지수를 담은 배열과 원하는 스코빌 지수 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하여 입력받는다.

  • 주어진 알파벳이 I이면 heappush로 num을 answer에 넣는다.
  • I가 아니라면, num이 -1인 경우 heappop으로 최솟값을 빼주고
  • num이 1이라면 answer에서 remove함수로 최대값을 찾아 빼준다.
    for문으로 모든 경우의 수를 돌아 answer에 비어있으면 [0,0]을 아닌 경우 answer의 최대, 최소를 리턴한다.

🎈 디스크컨트롤러

하드디스크는 한 번에 하나의 작업만 수행할 수 있다.
각 작업에 대해 [작업 요청시점, 작업 소요시간]을 담은 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 길이만큼 나눈 것을 리턴한다.

profile
To be a DataScientist

0개의 댓글