백준 [단계별로 풀어보기]: (16단계) "스택, 큐, 덱", python

백준 [단계별로 풀어보기]: (16단계) "스택, 큐, 덱", python

 

1. 문제번호 및 정답비율

16단계 스택,큐,덱 : 문제번호 및 정답 비율

2. 문제별 필요 지식 및 풀이 포인트

# 1. 28278 스택2

# 2. 10773 제로

 

# 3. 9012 괄호

조건 걸기가 어렵네

 vps = list(input()) #split()필요없음 : 무지성으로 넣지 말 것!

풀이point1. cnt = 0 # "("과 ")"을 담아줄 객체 생성

풀이point2. if cnt < 0: print('NO') # -1이 되는 순간 "())"형태가 되므로 잘못된 형식이 된다

 

# 4. 4949 균형잡힌 세상

a = input() # list로 받아버리면, 마침표'.'가 입력됐을 때, break를 할 수 X

if a == ".": break

 

# 5-2. 12789 도키도키 간식드리미

풀이point1. list형식의 입력값 외에 하나 더 list를 생성해야
풀이point2. sys.exit()를 활용해야

<sys.exit()의 특징>
1) 종료코드를 반환하며 기본값은 0이다.
2) return은 함수의 종료이며, sys.exit()은 더 큰 범위인 스크립트 전체가 종료된다.
3) break는 반복문을 중단할때 사용한다.'''

 

# 6. 18258 큐2, # 9. 28279 덱2 (같은 내용)

 

# 7. 2164 카드2

queue와 출력을 위한 stack = [ ]을 선언하여 쌓아준다.

 

# 8. 11866 요세푸스 문제0

(7,3) = 3627514, 원에서 사람이 제거되는 순서 123'456'7 / 3 6 ..
풀이point1. deque.rotate()를 사용할 줄 아는가?
풀이point2. 출력형식이 list가 아닌 <>형태로, f'{}'말고, " ".join()을 사용할 줄 아는가? (절대 "\b"를 사용해선 안된다.)

 

# 10. 2346 풍선 터뜨리기

풀이point1. 열거객체를 반환해주는 enumerate(iterable, start=)를 활용해야 풀 수 있다.

dict()처럼, idx에대한 원소값을 갖는 형태를 구성해야 한다는 느낌이 들었다. 풍선12345과 종이321-3-1때문이다.

풀이point2. 원판에서, "양수가 적혀 있을 경우에는 오른쪽으로 이동"은 시계반대방향으로 회전을 의미하므로, -(p-1)만큼 회전시켜 주어야한다. ("음수가 적혀 있을 때는 왼쪽으로 이동"은 시계방으로회전을 의미한다.)

 

# 11. 24511 queuestack

문제이해가 안되었다

3. 문제별 풀이 코드

# 1. 28278 스택2
import sys
n = int(sys.stdin.readline()) #9, int(input())하면, 시간초과 발생
stack = []
for _ in range(n): #0~8
    m = list(map(int, sys.stdin.readline().split())) #list형태가 아니면, ValueError 발생
    if m[0] == 1:
        stack.append(m[1])
    elif m[0] == 2:
        if len(stack) != 0:
            print(stack.pop())
        else:
            print(-1)
    elif m[0] == 3:
        print(len(stack))
    elif m[0] == 4:
        if len(stack) != 0:
            print(0)
        else:
            print(1)
    elif m[0] == 5:
        if len(stack) != 0:
            print(stack[-1])
        else:
            print(-1)
    else:
        break


# 2. 10773 제로
n = int(input())
stack = []
for _ in range(n):
    m = int(input())
    if m != 0:
        stack.append(m)
    else:
        stack.pop()
print(stack)


# 3. 9012 괄호
'''조건 걸기가 어렵네'''
'''t = int(input())
for i in range(t):
    vps = list(input()) #split()필요없음 : 무지성으로 넣지 말 것!
    #print(vps[-1])
    if vps.count('(') != vps.count(')') or vps[0] != '(' or vps[-1] != ')':
        print('No')
    else:
        print('YES')'''

'''append()와 pop()이 상쇄되어 일정한 값을 유지하게끔 조건 설정'''
t = int(input())
for i in range(t):
    vps = list(input())
    #print(vps)
    cnt = 0 #'('과 ')'을 담아줄 *객체 생성
    for j in range(len(vps)):
        if vps[j] == '(':
            cnt += 1
        elif vps[j] == ')':
            cnt -= 1
        #print(cnt) #())(()의 경우: 미해결..인 줄 알았는데..?!
        if cnt < 0: #-1이 되는 순간 '())'형태가 되므로 잘못된 형식이 된다
            print('NO')
            break
    if cnt == 0:
        print('YES')
    elif cnt > 0:
        print('NO')


# 4. 4949 균형잡힌 세상
'''
계속되는 NameError발생.........
from line13 to line18(elif ~ break)내용: 잘 체크할 것'''
while True:
    a = input() #list로 받아버리면, 마침표'.'가 입력됐을 때, break를 할 수 X
    #print(s)
    arr = []
    if a == ".": #'.'로 써서 NameError가 뜨나;그런가..?
        break
       
    for i in a:
        if i == '[' or i == '(':
            arr.append(i)
        elif i == ']':
            if len(arr) != 0 and arr[-1] == '[': #len(arr) != 0 조건들어가야
                arr.pop()
            else:
                arr.append(']')
                break
        elif i == ')':
            if len(arr) != 0 and arr[-1] == '(':
                arr.pop() #arra.pop()..아 오타.................
            else:
                arr.append(')')
                break
                
    if len(arr) == 0:
        print('yes')
    else:
        print('no')
    '''
    아래는 '잘못된 접근법'. <9012 괄호>처럼 접근하려했지만, 애매했다.
    그래서, str로 받아 list에 append/pop하는 방식으로 접근했다.
    
    for i in range(len(s)):
        if s[i] == '(':
            cnt += 1
        elif s[i] == ')':
            cnt -= 1
        elif s[i] == '[':
            cnt += 2
        elif s[i] == ']':
            cnt -= 2
        if cnt < 0:
            print('NO')
            break
    if cnt == 0:
        print('YES')
    elif cnt > 0:
        print('NO')'''


# 5-2. 12789 도키도키 간식드리미
'''list형식의 입력값 외에 하나 더 list를 생성해야'''
'''sys.exit() 특징
1) 종료코드를 반환하며 기본값은 0이다.
2) return은 함수의 종료이며, sys.exit()은 더 큰 범위인 스크립트 전체가 종료된다.
3) break는 반복문을 중단할때 사용한다.'''
import sys
n = int(input()) #5
wait = list(map(int, input().split())) #5 4 1 3 2
tmp = []
target = 1
for i in wait:
    tmp.append(i)
    while tmp and tmp[-1] == target: #tmp끝원소가 1일때(->2->3..점차증가)
        tmp.pop() #while list: if list is not None and some value present in it
        target += 1
        #print(tmp)
    if len(tmp) > 1 and tmp[-1] > tmp[-2]:
        print('Sad')
        sys.exit() #그냥 break 시 틀렸다고 나옴.
if tmp == 0:
    print('Sad')
else:
    print('Nice')
    
    
# 6. 18258 큐2
from collections import deque
import sys
n = int(sys.stdin.readline().strip())
dq = deque()

for i in range(n):
    l = sys.stdin.readline().strip().split()
    if l[0] == 'push':
        dq.append(l[1])
    elif l[0] == 'pop':
        if len(dq) != 0:
            print(dq.popleft())
        else:
            print(-1)
    elif l[0] == 'size':
        print(len(dq))
    elif l[0] == 'empty':
        if len(dq) == 0:
            print(1)
        else:
            print(0)
    elif l[0] == 'front':
        if len(dq) != 0:
            print(dq[0])
        else:
            print(-1)
    elif l[0] == 'back':
        if len(dq) != 0:
            print(dq[-1])
        else:
            print(-1)


# 7. 2164 카드2
#4321 -> 243 / 1 -> 42 / 1,3 -> 4 / 1,3,2
from collections import deque
n = int(input())
dq = deque()
for i in range(1,n+1):
    dq.append(i)
#print(dq) #[1,2,3,4,..] :출력비교위함
for _ in range(n-1):
    dq.popleft()
    dq.append(dq.popleft())
print(dq[0])


# 8. 11866 요세푸스 문제0 '''200%틀린풀이'''
#(7,3) = 3627514, 원에서 사람이 제거되는 순서 123'456'7 / 3 6 ..
'''deque.rotate()를 사용할 줄 아는가?'''
'''출력형식이 list가 아닌 <>형태로, f'{}'말고, 절대"\b"를 사용해선 안된다.'''
'''참고) https://djm03178.tistory.com/29'''
from collections import deque
n,k = list(map(int, input().split())) #7 3
dq = deque()
for i in range(1,n+1):
    dq.append(i)
#print(dq) #[1,2,3,4,5,6,7]
st = "<"
for i in range(n):
    dq.rotate(-k) #dq.rotate():오른쪽방향으로 1칸씩 회전
    #print(dq)
    st += f'{dq.pop()}, '
print(st[:-2].rstrip(),"\b>") #<3, 6, 2, 7, 6, 1, 4>


# 8. 11866 요세푸스 문제0 '''200%옳은 풀이'''
#(7,3) = 3627514, 원에서 사람이 제거되는 순서 123'456'7 / 3 6 ..
'''deque.rotate()를 사용할 줄 아는가?'''
'''출력형식이 list가 아닌 <>형태로, f'{}'말고, .join()을 사용할 줄 아는가?'''
from collections import deque
n,k = list(map(int, input().split())) #7 3
dq = deque()
for i in range(1,n+1):
    dq.append(i)
#print(dq) #[1,2,3,4,5,6,7]
st = []
for i in range(n):
    dq.rotate(-k) #dq.rotate():오른쪽방향으로 1칸씩 회전
    #print(dq)
    st.append(str(dq.pop())) #str형식으로 바꿔줘야
print('<'+ ', '.join(st) +'>')


# 9. 28279 덱2
from collections import deque
import sys

n = int(sys.stdin.readline())
dq = deque()

for i in range(n):
    m = list(map(int, sys.stdin.readline().split()))
    if m[0] == 1:
        dq.appendleft(m[1])
    elif m[0] == 2:
        dq.append(m[1])
    elif m[0] == 3:
        if len(dq) != 0:
            print(dq.popleft())
        else:
            print(-1)
    elif m[0] == 4:
        if len(dq) != 0:
            print(dq.pop())
        else:
            print(-1)
    elif m[0] == 5:
        print(len(dq))
    elif m[0] == 6:
        if len(dq) == 0:
            print(1)
        else:
            print(0)
    elif m[0] == 7:
        if len(dq) != 0:
            print(dq[0])
        else:
            print(-1)
    elif m[0] == 8:
        if len(dq) != 0:
            print(dq[-1])
        else:
            print(-1)


# 10. 2346 풍선 터뜨리기
'''첫 번째 시도 : 틀린 풀이'''
'''
풍선 원형 배열: n) 1 ... i-1 i i+1 ... n (1
풍선 안 종이) -n<=p<=n, p만큼 이동
ex) 풍선 1 2 3 4 5
    종이 3 2 1 -3 -1
터짐순서 1 4 5 3 2
'''
from collections import deque
n = int(input()) #5
p = list(map(int, input().split())) #3 2 1 -3 -1
dq = deque()
for i in p:
    dq.append(i)
#print(dq)
result = []
for i in range(len(dq)):
    print(dq.popleft())
    dq.rotate(dq[i])
    print(dq)
print(result)


# 10. 2346 풍선 터뜨리기
'''
풍선 원형 배열: n) 1 ... i-1 i i+1 ... n (1
풍선 안 종이) -n<=p<=n, p만큼 이동
ex) 풍선 1 2 3 4 5
    종이 3 2 1 -3 -1
터짐순서 1 4 5 3 2
'''
'''dict()처럼, idx에대한 원소값을 갖는 형태를 구성해야 할듯?'''
'''enumerate(iterable, start=) : 열거객체반환'''
'''if p>0: rotate(p-1); if p<0: rotate(p)로 해도 문제에서 요구하는 결과값이 나오지만,
원판에서, "양수가 적혀 있을 경우에는 오른쪽으로 이동" = "시계반대방향으로회전"을 의미하며
"음수가 적혀 있을 때는 왼쪽으로 이동" = "시계방으로회전"을 의미하기때문에,
-(p-1)과 -p만큼 회전시켜주는 것이 맞다.
'''
from collections import deque
n = int(input()) #5
dq = deque(enumerate(map(int, input().split()), start=1)) #3 2 1 -3 -1
#print(dq) #deque([(1, 3), (2, 2), (3, 1), (4, -3), (5, -1)])
#print(dq.popleft()) #(1, 3)
result = []
for _ in range(n):
    idx, p = dq.popleft() #튜플(1,3)을 각 원소형태1 3로 받고
    result.append(str(idx))
    #dq.rotate(p-1) #출력값이 다름
    if p>0:
        dq.rotate(-(p-1)) #원판에서 회전시, 시계반대방향으로 회전해야함
    elif p<0:
        dq.rotate(-p) #p
print(' '.join(result)) #str()로 변환


# 11. 24511 queuestack
'''문제이해가 안되었다.. / 아직 못 풀었다.'''
from collections import deque
n = int(input()) #4
#ds = list(map(int, input().split())) #0 1 1 0
el = list(map(int, input().split())) #1 2 3 4
#m = int(input()) #3
#c = list(map(int, input().split())) #2 4 7

dq = deque()
st = []
for i in range(n):
    if ds[i] == 0: #queue
        dq.append(el[i])
    elif ds[i] == 1: #stack
        st.append(el[i])
print(dq)
print(st)