[프로그래머스 코딩테스트 고득점 Kit] 스택 / 큐 문제

1. 같은 숫자는 싫어

문제 풀이

1. 첫 번째 순서(arr[0])은 무조건 들어가니까 먼저 넣어줍니다.

2. arr의 두번째부터 끝까지 for문을 돌려가며 i-1번째와 i번째 숫자를 비교해주며 넣으면 됩니다.

def solution(arr):
    answer = []
    answer.append(arr[0])
    for i in range(1, len(arr)):
        if arr[i-1] == arr[i]:
            continue
        else:
            answer.append(arr[i])
    return answer

 

2. 기능개발

문제 풀이

최악의 경우 N^2이 걸리는 방법이지만 n이 그다지 크지 않기 때문에 깡으로 계산해도 된다고 판단하여 간단한 방법으로 풀었습니다.

 

1. 왼쪽 끝에 있는 것부터 끝내야 하므로 progress와 speeds를 deque로 변환

2. for문을 돌아가며 pro의 i번째에 spd[i]를 더해줍니다

3. 만약 pro의 0번째가 100을 넘기게 되면 pro와 spd에서 popleft를 해서 0번째를 치운 다음 cnt에 +1를 해줍니다.

그 뒤에 있는 작업들도 보며 100을 넘긴 경우에도 같은 작업을 진행합니다.

4. cnt가 0 이상인 경우에는 return에 cnt를 삽입합니다

from collections import deque

def solution(progresses, speeds):
    answer = []
    pro = deque(progresses)
    spd = deque(speeds)
    while pro:
        cnt = 0
        for i in range(len(pro)):
            pro[i] += spd[i]
            
        while pro and pro[0] >= 100:
            pro.popleft()
            spd.popleft()
            cnt += 1
        
        if cnt != 0:
            answer.append(cnt)
            cnt = 0
            
    return answer

3. 올바른 괄호

문제 풀이

stack이라는 빈 리스트를 만들어 (인 경우에는 stack.append 해주고 )인 경우에는 pop해줍니다.

stack이 비어있는 상태에서 )가 나올 경우에는 문제가 있는 것이므로 false를 반환하고 과정이 다 끝났는데 stack이 비어있지 않아도 false를 반환하고 그 외에는 true를 반환하면 됩니다.

def solution(s):
    answer = True
    stack = []
    for i in s:
        if i == '(':
            stack.append(i)
        elif i == ')':
            if not stack:
                return False
            stack.pop()
    
    if stack:
        return False
    else:
        return True

4. 프로세스

문제 풀이

처음에는 ABCD라고 해뒀길래 뭐가 나와야 종료인지 헷갈렸는데 문제를 잘 읽어보면 priorities의 location 번째 숫자가 나왔을 때 해당 숫자보다 큰 수가 priorities에 없으면 몇 번째로 탈출한 것인지 구하는 문제였습니다.

 

저는 priorities를 prior라는 deque에 복사하고 process라는 deque를 하나 더 만들어서 진행하였습니다.

깊은 복사를 해서 pop(0) 을 하는 방법도 있지만 이건 나중에 리스트의 길이가 커지면 메모리가 터질 확률이 있기 때문에 0번째를 pop한다고 하면 deque를 사용하는게 좋습니다(마지막에 있는건 상관 없음).

 

이번 문제에서는 안해봤지만 아마 안터지긴 할걸..요?

이건 list와 deque의 성질 차이라 나중에 사용할겁니다(연결리스트 뭐시기...하면서)

 

process의 location번째 숫자를 -1로 만들고 while문을 돌려 process와 prior에서 target1, target2로 popleft 해줍니다.

이 때 target1 = -1이고 target2가 process에서 가장 큰 숫자라면 while문을 종료시키고, target1이 -1이 아니라면 process의 최대값과 비교하여 아예 빼버리거나 process에 다시 append하는 작업을 하면 됩니다.

대신 target1 != -1이고 max(process) <= target1 이라면 answer에 +1을 하고 아니라면 집어넣기만 합니다.

 

그리고 popleft를 하면서 prior에 아무것도 남지 않으면(우선순위가 1이라 마지막에 나오는 경우) max(prior)를 할 수 없어 런타임 오류가 뜨므로 해당 조건까지 넣어주면 답이 됩니다.

 

from collections import deque

def solution(priorities, location):
    answer = 0
    process = deque(priorities)
    prior = deque(priorities)
    process[location] = -1
    
    while process:
        target1 = process.popleft()
        target2 = prior.popleft()
        
        if target1 == -1 and (not prior or max(prior) <= target2):
            answer += 1
            break
        elif target1 >= max(prior):
            answer += 1
        elif max(prior) > target1:
            process.append(target1)
            prior.append(target2)
            
    return answer

5. 다리를 지나는 트럭

문제 풀이

이전 문제들과 마찬가지로 deque를 사용해서 풀었습니다.

 

bridge_length가 있으므로 truck의 길이를 1로 생각하고 해당 길이만큼 시간이 지나가야 다리에서 트럭이 탈출 가능합니다.  [0,0,0...0,0] 이라는 리스트를 만들어서 각각의 자리에 트럭들의 무게를 넣고 1초가 지날 때마다 한칸씩 앞으로 간다고 생각하면 쉽게 풀리는 문제입니다.

 

만약 다리가 버틸 수 있는 무게보다 truck들의 무게 합이 더 작다면 다음에 올 트럭을 확인해보고 트럭이 있으면 다음 조건을 확인합니다.

다음 트럭이 올라가도 weight보다 작다면 다리 위로 올려보내면 되고 다음 트럭이 올라왔을 때 다리가 버틸 수 있는 무게를 초과하면 안올려보낸다는 의미의 0을 넣어주면 됩니다. 그렇게 쭉쭉 밀어주면서 다리 위에 아무것도 없다면 끝난거니 answer를 반환해주면 끝이 납니다.

 

from collections import deque

def solution(bridge_length, weight, truck_weights):
    answer = 0
    bridge = deque([0] * bridge_length)
    truck_weights = deque(truck_weights)
    total_weight = 0

    while bridge:
        answer += 1
        total_weight -= bridge.popleft()

        if truck_weights:
            if total_weight + truck_weights[0] <= weight:
                t = truck_weights.popleft()
                bridge.append(t)
                total_weight += t
            else:
                bridge.append(0)  # 무게 넘으면 weight가 0인 트럭이 간다고 생각하고 채움

    return answer

 

6. 주식가격

문제 풀이

이번에는 deque를 사용하지 않고 이중for문으로 풀어보았습니다.

 

1번째 값이 떨어지는 순간까지 time에 +1을 해주거나 끝까지 +1을 해주고 해당 값들을 answer에 넣으면 됩니다.

 

***오류 발견***

테케에서 최악의 경우가 없어서 통과가 되긴 했지만 prices의 길이가 10만까지라 최악의 경우에는 10만의 제곱이 나와서 시간 초과가 될겁니다. 아마 테케에 이 경우가 없어서 통과되는거 같네요.

 

1. 이중 for 문으로 돌린 답

def solution(prices):
    answer = []
    for i in range(len(prices)):
        time = 0
        for j in range(i+1, len(prices)):
            time += 1
            if prices[i] > prices[j]:
                break
        answer.append(time)
    return answer

 

2. while을 사용해 한 번만 보면 O(n)으로 시간복잡도를 개선한 방법

def solution(prices):
    answer = [0] * len(prices)
    stack = []

    for i in range(len(prices)):
        while stack and prices[stack[-1]] > prices[i]:
            top = stack.pop()
            answer[top] = i - top
        stack.append(i)

    for i in stack:
        answer[i] = len(prices) - 1 - i

    return answer

해당 방법은 말로 설명하니까 저도 꼬여서 지피티의 요약 도움을 받아서 표로 보여드리겠습니다

stack은 몇 초가 지났는지 넣는다고 생각하시면 되고 while문 내부에서는 stack의 -1번째 초가 지났을 때 주식이 떨어졌는지 아닌지 확인한다고 생각하시면 됩니다.

 

프로그래머스에선 Level 2짜리인데 백준가면 비슷한 문제가 골드 4인거 보면 3레벨 짜리인데 2로 들어가지 않았나 싶네요. 아마 이중 for문으로 풀리게 해서 그런듯? 그리디 + 스택으로 푸는 문제입니다