22. 덱(10866) ,단어 뒤집기2(17413)

문제.

정수를 저장하는 덱(Deque)를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.
명령은 총 여덟 가지이다.
push_front X: 정수 X를 덱의 앞에 넣는다.
push_back X: 정수 X를 덱의 뒤에 넣는다.
pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
size: 덱에 들어있는 정수의 개수를 출력한다.
empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다.
문제에 나와있지 않은 명령이 주어지는 경우는 없다.

답:

import sys #sys.stdin.readline()을 가져오는 import
from collections import deque #덱 구조를 가져오는 import

N = int(sys.stdin.readline().strip())
dq = deque() #덱을 dq 변수에 저장

for i in range(N):

  command = sys.stdin.readline().split()

  if (command[0] == 'push_front'):
    dq.appendleft(command[1]) #왼쪽에 추가.
  
  elif (command[0] == 'push_back'):
    dq.append(command[1])
  
  elif (command[0] == 'pop_front'):
    if (len(dq) == 0):
      print(-1)
    else:
      print(dq[0])
      dq.popleft() #왼쪽을 빼기
  
  elif (command[0] == 'pop_back'):
    if (len(dq) == 0):
      print(-1)
    else:
      print(dq[len(dq) - 1])
      dq.pop()
  
  elif (command[0] == 'size'):
    print(len(dq))

  elif (command[0] == 'empty'):
    if len(dq) == 0:
      print(1)
    else:
      print(0)

  elif (command[0] == 'front'):
    if (len(dq) == 0):
      print(-1)
    else:
      print(dq[0])

  elif (command[0] == 'back'):
    if (len(dq) == 0):
      print(-1)
    else:
      print(dq[len(dq)-1])

덱의 표현

덱은 큐를 양방향으로 뚫어둔 것이다.

그래서 양방향에서 빠른 추가/삭제가 가능해 효율적인 자료 구조이다.

이후 이 덱을 파이썬에서 경우의 수를 나누어서 구현하면 된다.

(파이썬에는 딱히 이런 자료구조 문법을 따로 지원해주지 않는다...)

---

문제.

문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다.
먼저, 문자열 S는 아래와과 같은 규칙을 지킨다.
알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('<', '>')로만 이루어져 있다.
문자열의 시작과 끝은 공백이 아니다.
'<'와 '>'가 문자열에 있는 경우 번갈아가면서 등장하며, '<'이 먼저 등장한다. 또, 두 문자의 개수는 같다.

태그는 '<'로 시작해서 '>'로 끝나는 길이가 3 이상인 부분 문자열이고, '<'와 '>' 사이에는 알파벳 소문자와 공백만 있다. 단어는 알파벳 소문자와 숫자로 이루어진 부분 문자열이고, 연속하는 두 단어는 공백 하나로 구분한다. 태그는 단어가 아니며, 태그와 단어 사이에는 공백이 없다.

첫째 줄에 문자열 S가 주어진다. S의 길이는 100,000 이하이다.

첫째 줄에 문자열 S의 단어를 뒤집어서 출력한다.

답:

data = input()

stack = []
ans = ''
check = False # 괄호안의 여부를 체크
for d in data:
    # 스택에 존재하는 값을 역으로 추가합니다.
    if (d == '<'):
        check = True
        for k in range(len(stack)):
            ans += stack.pop()

    stack.append(d)
    # 스택에 존재하는 값은 괄호안의 값이기에 순차적으로 추가합니다.
    if (d == '>'):
        check = False
        for _ in range(len(stack)):
            ans += stack.pop(0)
    # 스택에 존재하는 값을 역으로 추가합니다.
    if (d == ' ' and check == False):
        for i in range(len(stack)):
            if (i == 0):
                stack.pop()
                continue
            ans += stack.pop()
        ans += ' '
# 스택에 값이 남아있는 경우는 괄호의 경우가 아니기에 역으로 추가합니다.
if stack:
    for _ in range(len(stack)):
        ans += stack.pop()

print(ans)

 

check 변수를 이용해서 괄호의 존재 여부를 체크할 것이다.

출력은 ans으로 할 것이고, 초반에는 공백으로 초기화해둔다.

스택은 stack이라는 빈 배열을 이용해서 자료를 넣고 뺄 것이다.

이후 경우의 수에서는 스택에 값이 있는 경우, 그 속에 괄호가 있냐 없냐로 나뉜다.

괄호가 있으면 그 안의 단어는 뒤집으면 안 된다, 반대로 괄호가 없는 단어는 뒤집으면 된다.

pop을 for문 안에서 돌리고 이후 append 함수를 이용해서 다시 문자를 넣어준다.

pop은 밖에 있는 것부터 해주고, 이후 append를 이용해서 합류가 되기 때문에.. 단어는 뒤집어지게 된다.

(예를 들어 a, b, c가 스택에 있고, 차례로 pop을 하면 c > b > a 순으로 나간다. 이후 다시 append를 하니 c > b > a으로 들어가지고 스택은 c, b, a로 자료가 남아지게 된다.)