[프로그래머스] Lv.2 다리를 지나는 트럭, 스택/큐 문제를 풀 때 팁

프로그래머스

 

첫 번째 풀이(오답)

1. 트럭 deque와 0으로 이루어진 다리 deque를 만든다.

2. 트럭 deque가 0일 될때까지 while문을 반복한다. 트럭을 하나 popleft해주고
'다리도 하나 popleft 해준다.'(다리를 이동하는 것을 0 하나를 빼고 트럭을 올리는 거로 표현) 

2-1. 다리 deque의 합과 앞으로 올릴려는 트럭 deque에서 pop한 트럭의 합이 w보다 작거나 같은 경우,

pop한 트럭을 다리에 올려준다.

2-2. 다리 deque의 합과 앞으로 올릴려는 트럭 deque에서 pop한 트럭의 합이 w보다 작거나 같은 경우,

pop한 트럭을 트럭 deque에 appendleft 해주고 '0을 넣어준다.' (다리에 아무것도 올라가지 않았다는 표현)

from collections import deque

def solution(b_l, w, t):
    time = 0
    tque = deque(t)
    bl = deque([0]*b_l)
    
    while tque:
        time += 1
        pop = tque.popleft()
        bl.popleft()
        
        if sum(bl) + pop <= w:
            bl.append(pop)
            continue
        
        if sum(bl) + pop > w:
            bl.append(0)
            tque.appendleft(pop)
            continue

    time += b_l
    return time

로직은 맞았지만 케이스 하나에서 시간 초과가 발생했다. sum을 사용해서 그런 것 같다.

 

두 번째 풀이 (정답)

sum을 어떻게 바꿀지 고민해보자

그리고 무조건 처음에 pop을 하여 트럭을 빼는 방식은 비효율적이다.

다리가 버티는 무게(wei)를 따로 만들어 무게를 더하고 빼주자.

무조건 while 반복문을 시작할때, 다리 deque에서 popleft한 요소를 빼준다.

그리고 트럭 deque도 먼저 빼주지 말고 트럭 deque의 0 인덱스와 wei를 더한 무게를 다리가 버틸 수 있는 하중과 비교해주면 훨씬 간단하게 해결할 수 있다.

 

deque를 사용한 풀이

from collections import deque

def solution(b_l, w, t):
    time = 0
    tque = deque(t)
    bl = deque([0]*b_l)
    wei = 0
    
    while tque:
        time += 1
        wei -= bl.popleft()
        
        if wei + tque[0] <= w:
            wei += tque[0]
            bl.append(tque.popleft())
            continue
        
        if wei + tque[0] > w:
            bl.append(0)
            continue

    time += b_l
    
    return time

 

deque를 사용하지 않는 풀이

def solution(b, w, t):
    time = 0
    bridge = [0]*b
    wei = 0
    
    while len(t) != 0:
        time += 1
        wei -= bridge.pop(0)
        
        if wei + t[0] <= w:
            wei += t[0]
            bridge.append(t.pop(0))
        else:
            bridge.append(0)
        
    time += b
        
    
    return time

 

스택/큐 문제를 풀 때 팁

스택이나 큐에 쌓이는 것을 확인하고 싶을 때 위에서 했던 것처럼 +/-를 이용해 표현할 수 있다.

위에서는 다리에 올라간 트럭의 무게를 빠른 속도로 파악하기 위해 wei를 0으로 초기화하고, 들어오는 트럭과 나가는 트럭의 무게를 뺐는데 이는 스택을 사용하는 것과 같은 효과를 가지고 있다.

 

다리는 지나는 트럭 문제 외에 대표적인 문제로 올바른 괄호 찾기 문제가 있다.

이 문제는 중괄호로 주어진 문자열이 열림과 닫힘의 짝이 맞는 지 확인하는 문제이다.

기본적으로는 무조건 false인 경우를 처리한 후 스택에 문자열 순대로 넣으면서 스택에 들어간 괄호가 (이고 이어서 들어가는 괄호가 ) 라면 없애주고 그렇지 않은 경우는 그냥 계속 넣어준다. 결과적으로 스택에 아무것도 남아있지 않으면 올바른 괄호이고, 스택에 남아있다면 올바른 괄호가 아닌 것이다. 이를 정말 간편하게 변수를 0으로 초기화하고 +와 -로 구현할 수 있다.

def solution(s):
	answer = True
    judge = 0
    
    if s[-1] == '(' or s[0] == ')':
    	return False
    
    while s:
    	pop = s.pop(0)
        
        if pop == '(':
        	judge += 1
        
        if  judge > 0 and pop == ')': 
        # 아무것도 들어오지 않은 상태(0)에서 ')'를 넣으면(-1) 의미가 없기 때문에 아무 조치도 하지 않는다.
        	judge -= 1
        
    if judge != 0:
    	return False
        
    return answer

 

위와 같이 0에 +1 -1을 하는 방식으로 스택을 표현했다. 이를 다른 문제를 풀 때도 고려해보고 적용해보면 좋을 것이라 생각된다.