[파이썬] 코딩테스트 문제 풀이 - 스택/큐 문제 (프로그래머스)

Writer : Harim Kang

스택/큐 문제 - 프로그래머스

스택과 큐 자료구조를 사용하는 문제입니다. 파이썬에서는 리스트를 사용합니다. 스택과 큐의 파이썬 구현에 대한 내용은 아래의 포스팅에 있습니다. 문제의 코드들은 모두 다 통과를 한 코드입니다.

https://davinci-ai.tistory.com/16?category=911813

파이썬으로 구현하는 자료구조 요약 정리 - 배열(Array), 큐(Queue), Stack, Linked List

또한, 해당 포스팅에서 푸는 문제는 아래의 6가지 문제입니다.

1. 탑
2. 다리를 지나는 트럭
3. 기능개발
4. 프린터
5. 쇠막대기
6. 주식가격

해당 문제들은 프로그래머스의 코딩테스트 연습 > 코딩테스트 고듬적 kit > 스택/큐에 모여있는 6문제입니다.

https://programmers.co.kr/learn/courses/30/parts/12081

프로그래머스

1. 탑 (Level 2)

문제

https://programmers.co.kr/learn/courses/30/lessons/42588

문제 요약

• 높이가 존재하는 탑들이 있을 때, 각각 탑들은 왼쪽으로 레이저 신호를 발사합니다.
• 자신보다 높은 탑을 만나면 신호를 전송합니다.
• 해당 인덱스에서 왼쪽으로 신호를 보낼 때, 받은 위치를 return 리스트의 해당 인덱스에 저장합니다.
• height : 탑들의 높이 배열
• return : 각 탑들이 보낸 신호가 도달하는 탑의 위치

테스트 케이스

제한 사항

• 수신하는 탑이 존재하지 않으면 (index 가 0인 탑 또는 왼쪽에 자신보다 큰 크기의 탑이 존재하지 않을때), 0으로 표시됩니다.

해결

• answer : 정답을 담는 리스트입니다. 탑의 수만큼 미리 0으로 채워놓습니다.
• i는 height 리스트의 맨 뒤부터 시작합니다. (신호를 왼쪽으로 보내기 때문)
• i를 기준으로 0부터 i-1까지 j가 순회하면서 i보다 큰수를 cur에 넣습니다.
• 이때, cur은 i보다 크면서 i와 가장 가까운 수가 들어갑니다.
• 반복을 하면서 answer의 i번째에 cur을 넣어줍니다.

코드

def solution(heights):

    answer = [0 for _ in range(len(heights))]
    for i in reversed(range(len(heights))):
        cur = 0
        for j in range(i):
            if heights[i] < heights[j]:
                cur = j + 1
        answer[i] = cur
    return answer

2. 다리를 지나는 트럭 (Level 2)

문제

https://programmers.co.kr/learn/courses/30/lessons/42583

문제 요약

• 트럭들이 일차선 다리를 순서대로 지나갈때, 최소 시간을 return하는 문제입니다.
• 트럭은 1초에 1만큼 움직입니다.
• bridge_length : 다리 길이입니다.
• weight : 다리가 견딜 수 있는 무게입니다.
• truck_weights : 트럭들의 무게를 다리를 지나는 순서대로 나열한 배열입니다.

• 길이가 2, 무게 제한은 10이고, 1초에 1만큼 움직이는 트럭 [7, 4, 5, 6]이 다리를 건너가는 순서는 위와 같습니다.

테스트 케이스

제한 사항

• 트럭이 완전히 다리에 올랐을 때, 무게가 인정됩니다.

해결

• continue_ : 해당 리스트는 다리를 건너는 중인 트럭을 담은 리스트입니다. continue_안에는 [트럭의 무게, 다리위의 위치]의 형태로 이루어집니다.

• finish : 해당 리스트는 다리를 다 건넌 트럭을 담은 리스트입니다.

• timer : 시간을 재는 정수로서 반복분이 돌때마다 1초가 추가됩니다.

• cur_w : 현재 다리위의 트럭 무게의 총합입니다.

• num은 트럭의 총 대수이고, finish의 트럭 수가 num 이상이 되면 반복문을 종료합니다.

    finish = []
    continue_ = []
    timer = 0
    num = len(truck_weights) 
    while len(finish) < num:
            timer = timer+1

• 다리 위에 트럭이 존재하면 if continue_: 안쪽의 코드로 들어가고 존재하지 않으면 else: 문으로 진행됩니다. else문에서는, 대기 트럭이 존재할 때 다리위로 옮기는 역할을 합니다.

    if continue_:
            # 다리 위에 트럭이 존재할 때
    else:
            # 다리 위에 트럭이 없으면,
        if truck_weights: # 대기 중인 트럭이 있을 때, 
                    # 맨 앞 순서의 트럭을 빼서, 다리 위로 옮긴다.
            continue_.append([truck_weights.pop(0),1])

• continue_ 리스트를 순회합니다.

  • [트럭 무게, 다리에서 위치] 중 무게가 0이면 다음 순서로 넘어갑니다.

  • 트럭 무게가 0이상이면, 다리에서의 위치에 1을 더해서 위치를 1만큼 움직여줍니다.

  • 1만큼 움직인 위치가 다리의 길이보다 길다면 트럭을 finish 리스트에 넣고 continue_의 원래 자리는 초기화 해줍니다.

  • 1만큼 움직인 위치가 다리 길이보다 작다면, cur_w에 트럭 무게를 더해줍니다.

    for i in range(0, len(continue_)):
        if continue_[i][0] == 0:
            continue
        continue_[i][1] = continue_[i][1] + 1
        if continue_[i][1] >bridge_length:
            finish.append(continue_[i][0])
            continue_[i] = [0, 0]
        else:
            cur_w = cur_w + continue_[i][0]

• 대기 중인 트럭이 존재하고, 대기 중 트럭의 맨앞 트럭의 무게 + 현재 다리위의 트럭 무게 총합이 제한 무게 이하라면, 트럭을 하나 다리 위로 올립니다.

    if truck_weights and (cur_w + truck_weights[0] <= weight):
        continue_.append([truck_weights.pop(0), 1])

코드

def solution(bridge_length, weight, truck_weights):
    finish = []
    continue_ = []
    timer = 0
    num = len(truck_weights)
    while len(finish) < num:
        timer = timer+1
        cur_w = 0
        if continue_:
            for i in range(0, len(continue_)):
                if continue_[i][0] == 0:
                    continue
                continue_[i][1] = continue_[i][1] + 1
                if continue_[i][1] >bridge_length:
                    finish.append(continue_[i][0])
                    continue_[i] = [0, 0]
                else:
                    cur_w = cur_w + continue_[i][0]
            if truck_weights and (cur_w + truck_weights[0] <= weight):
                continue_.append([truck_weights.pop(0), 1])
        else:
            if truck_weights:
                continue_.append([truck_weights.pop(0),1])
    answer = timer
    return answer

3. 기능개발 (Level 2)

문제

https://programmers.co.kr/learn/courses/30/lessons/42586

문제 요약

• progresses : 현재 각 기능들의 진도입니다. 100이 되면 서비스에 반영됩니다.
• speeds : 기능 개발속도입니다. 하루에 진행되는 진도를 의미합니다.
• 배포는 하루에 한번 하며, 앞선 기능보다 먼저 진도가 완성되어도 앞의 기능을 기다린 후에 같이 배포됩니다.
• 배포마다 몇 개의 기능들이 함께 배포되는 지를 찾는 문제입니다.

테스트 케이스

제한 사항

• 각 값들은 모두 자연수입니다.

해결

• 각각의 기능들이 완성되는데에 얼마나 걸리는지에 대해 계산이 가능합니다. 기능들마다 완성에 걸리는 일수를 day라는 리스트로 저장합니다.

  • (100 - 현재 기능의 진도) // 개발 속도가 바로 걸리는 일수 입니다. 이때, 나머지가 있는 경우에는 1을 더해주어야 올바른 일수가 나옵니다.

    n = len(progresses)
    day = [0 for _ in range(n)]
    for i in range(n):
        day[i] = (100 - progresses[i]) // speeds[i]
        if (100 - progresses[i]) % speeds[i] != 0:
            day[i] += 1

• stack : day의 앞쪽 순서부터 pop을 통해 값을 구해서 스택에 넣습니다. 스택은 한꺼번에 배포할 수 있는 것들을 담는 용도입니다.

  • 이때, 다음의 day안의 값과 비교해서 기존 스택안의 값이 더 크거나 같으면 스택에 다음 값을 넣습니다.

  • 기존 스택 안의 값이 day의 다음 값보다 낮으면, 한꺼번에 배포가 불가능한 것이 다음이라는 의미이고, 기존의 스택 안의 것들만 함께 배포한다는 의미입니다.

  • 스택에 쌓인 개수를 answer에 넣습니다. 그리고 새로운 다음 값을 스택을 초기화하여 넣습니다.

  • day가 pop을 통해 모두 비워질 때까지 진행됩니다. 다 비었다면 스택안의 값 개수를 answer에 추가합니다.

    stack = []
    answer = []
    stack.append(day.pop(0))
    while day:
        current = day.pop(0)
        if stack[0] >= current:
            stack.append(current)
        else:
            answer.append(len(stack))
            stack = [current]
        if not day:
            answer.append(len(stack))

코드

def solution(progresses, speeds):

    n = len(progresses)
    day = [0 for _ in range(n)]
    for i in range(n):
        day[i] = (100 - progresses[i]) // speeds[i]
        if (100 - progresses[i]) % speeds[i] != 0:
            day[i] += 1
    stack = []
    answer = []
    stack.append(day.pop(0))
    while day:
        current = day.pop(0)
        if stack[0] >= current:
            stack.append(current)
        else:
            answer.append(len(stack))
            stack = [current]
        if not day:
            answer.append(len(stack))
    return answer

4. 프린터 (Level 2)

문제

https://programmers.co.kr/learn/courses/30/lessons/42587

문제 요약

• 다음의 규칙을 지키면서, 프린터가 동작합니다.
  1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
  2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
  3. 그렇지 않으면 J를 인쇄합니다.
• priorities : 인쇄 대기목록입니다. 이때 숫자가 클 수록 중요도가 높다는 의미입니다.
• location : 몇번째로 출력이 되는지 알고자하는 문서의 위치입니다.
• location에 존재하는 문서가 몇번째에 출력이 되는지를 return하는 문제입니다.

테스트 케이스

제한 사항

• 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.
• location의 index는 0부터 시작합니다.

해결

• seq : 각 문서의 인덱스를 저장한 리스트입니다. priorities를 중요도에 따라 순서를 정리할 때, 인덱스를 기억하도록 함께 순서를 정리하는 용도입니다.
• priorities가 빌 때까지 반복문을 수행합니다.
  • priorities의 값을 앞에서부터 하나씩 pop을 사용하여 꺼냅니다. 이때, seq의 인덱스도 함께 pop을 사용하여 꺼냅니다.
  • 꺼낸 것이 마지막 값이었다면 ans리스트에 인덱스를 바로 담고 반복문을 벗어납니다.
  • 마지막 값이 아니고, 현재 꺼낸 값이 남아 있는 문서들의 중요도 최대값보다 작다면, priorities의 맨 마지막에 다시 집어넣고, 인덱스도 seq의 뒤에 집어넣습니다.
  • 현재 꺼낸 값이 최대값이라면, ans 리스트에 인덱스를 담습니다.
• 반복문이 끝나면, 규칙에 맞게 ans 리스트에 각 문서의 인덱스들이 담깁니다. 최종 답은 location과 동일한 문서가 ans의 몇번째 칸에 있는지를 알면 됩니다.
• 이때, ans의 인덱스에 +1을 해주어야 정상적인 자연수가 나옵니다.

코드

def solution(priorities, location):

    seq = [i for i in range(len(priorities))]
    ans = []

    while priorities:
        current = priorities.pop(0)
        s = seq.pop(0)
        if not priorities:
            ans.append(s)
            break
        if current < max(priorities):
            priorities.append(current)
            seq.append(s)
        else:
            ans.append(s)
    answer = ans.index(location) + 1

    return answer

5. 쇠막대기 (Level 2)

문제

https://programmers.co.kr/learn/courses/30/lessons/42585

문제 요약

• 쇠막대기들을 겹쳐서 레이저로 절단하는 작업에 아래의 규칙을 따릅니다.
  • 쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있습니다.
  • 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓습니다.
  • 각 쇠막대기를 자르는 레이저는 적어도 하나 존재합니다.
  • 레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않습니다.
• 입력 값에 대한 규칙은 아래와 같습니다.
  • 레이저는 여는 괄호와 닫는 괄호의 인접한 쌍 '()'으로 표현합니다. 또한 모든 '()'는 반드시 레이저를 표현합니다.
  • 쇠막대기의 왼쪽 끝은 여는 괄호 '('로, 오른쪽 끝은 닫힌 괄호 ')'로 표현됩니다.
• arrangement : 쇠막대기와 레이저의 배치를 표현한 문자열
• 잘린 쇠막대기 조각의 총 개수를 찾는 문제입니다.

테스트 케이스

제한 사항

• arrangement의 여는 괄호와 닫는 괄호는 항상 쌍을 이룹니다.
• 위의 말은, arrangement의 시작값은 항상 '(' 이고, 끝 값은 항상 ')'입니다.

해결법

• bar : 막대기를 저장하는 배열입니다. '('가 들어오면 막대 하나라는 뜻인 1을 추가합니다. 시작값은 항상 '('로 시작하므로, bar는 [1]로 시작합니다.

• 두번째 문자열의 문자부터 순회합니다.

  • 만약 '('가 들어오면 bar 배열에 1을 추가해줍니다.

  • 만약 ')'가 들어왔는데, '()'과 같은 형태로 이어서 나오는 것이라면 이것은 레이저를 의미합니다. 이때는 기존 bar에 들어간 것은 막대가 아니므로 pop하여 꺼내고, bar에 있는 모든 막대들을 쪼개므로 answer에 bar의 모든 값의 총합을 더합니다.

    

  • 만약 '))'형태로 이어서 들어오면 이것은 막대 하나가 끝났다는 의미이므로, bar에서 가장 마지막으로 들어간 것을 pop으로 제거합니다.

    

코드

def solution(arrangement):
    answer = 0
    bar = [1]
    for i in range(1, len(arrangement)):
        if arrangement[i] == '(':
            bar.append(1)
        elif arrangement[i] == ')':
            if arrangement[i-1] == '(':
                bar.pop(-1)
                if bar:
                    answer += sum(bar)
                # 이때는 레이저
            else:
                answer += bar.pop(-1)

    return answer

6. 주식가격 (Level 2)

문제

https://programmers.co.kr/learn/courses/30/lessons/42584

문제 요약

• prices : 초 단위로 기록된 주식가격이 담긴 배열입니다.
• 각각의 prices 인덱스에서 가격이 떨어지지 않은 기간은 몇 초인지를 구하는 문제입니다.

테스트 케이스

제한 사항

• 1초가 지나면, 지난 후의 가격과 상관없이, 1초간 가격이 떨어지지 않은 것입니다.
• 마지막 인덱스의 가격은 항상 0초간 떨어지지 않는 것입니다.

해결법

• answer : 주어진 prices의 길이 만큼 0을 채워준 배열입니다.
• 반복문을 통해서 prices의 첫번째 값부터 순회합니다. 현재 순회중인 값을 current라고 하고, 현재 값 이후의 값을 2중 반복문을 사용하여 순회합니다.
  • current : 현재 기준이 되는 값으로, prices의 앞쪽 값부터 순서대로 선언됩니다.
  • count : current가 얼마 동안 가격이 떨어지지 않는지 확인하기 위한 값입니다.
  • comp : current 기준으로 뒤쪽 값들입니다. comp < current 조건으로, 가격이 떨어지는지를 확인하여 떨어진다면 반복문을 바로 빠져나갑니다.
  • count를 기준 인덱스의 answer에 기록합니다.
  • 위의 과정을 전체 prices에 대해 반복합니다.

코드

def solution(prices):
    answer = [0 for _ in range(len(prices))]
    for i in range(1, len(prices)):
        current = prices[i-1]
        count = 0
        for j in range(i, len(prices)):
            comp = prices[j]
            count += 1
            if comp < current:
                break
        answer[i-1] = count

    return answer
# 정확성: 66.7
# 효율성: 33.3
# 합계: 100.0 / 100.0