20. 스택 수열 (1874), 에디터(1406)

문제.

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.
1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push 하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

답:

count = 1
temp = True
stack = []
op = []

N = int(input())
for i in range(N):
    num = int(input())
    # num이하 숫자까지 스택에 넣기
    while (count <= num):
        stack.append(count)
        op.append('+')
        count += 1

    # num이랑 스택 맨 위 숫자가 동일하다면 제거
    if (stack[-1] == num):
        stack.pop()
        op.append('-')
    # 스택 수열을 만들 수 없으므로 NO
    else:
        temp = False
        break

# 스택 수열을 만들수 있는지 여부에 따라 출력 
if (temp == False):
    print("NO")
else:
    for i in op:
        print(i)

스택의 특성은 입출구가 하나인 자료 구조라는 것이다.

이미지

push로 넣고, pop으로 뺀다. 파이썬에서는 append가 push의 역할을 해준다.

스택은 가장 마지막 부분에서 나가기에 마지막 배열부터 빼줘야 한다. (배열에서는 -1이 마지막 인덱스가 되어준다.)

그리고 스택 수열이 되는지 안되는지는 if문으로 판별한다. (처음에는 temp은 true로 설정해준다.)

---

문제.

한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.
이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가 있다.
이 편집기가 지원하는 명령어는 다음과 같다.

초기에 편집기에 입력되어 있는 문자열이 주어지고, 그 이후 입력한 명령어가 차례로 주어졌을 때, 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 구하는 프로그램을 작성하시오. 단, 명령어가 수행되기 전에 커서는 문장의 맨 뒤에 위치하고 있다고 한다.

첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수를 나타내는 정수 M(1 ≤ M ≤ 500,000)이 주어진다. 셋째 줄부터 M개의 줄에 걸쳐 입력할 명령어가 순서대로 주어진다. 명령어는 위의 네 가지 중 하나의 형태로만 주어진다.

첫째 줄에 모든 명령어를 수행하고 난 후 편집기에 입력되어 있는 문자열을 출력한다.

답:

import sys 

stack_l = list(input()) #스택의 왼쪽
stack_r = [] #스택의 오른쪽
n = int(input()) 

for i in range(n):
    command = sys.stdin.readline().split() #커서의 역할을 해줍니다.

    if command[0] == "L" and stack_l:
        stack_r.append(stack_l.pop())
    elif command[0] == "D" and stack_r:
        stack_l.append(stack_r.pop())
    elif command[0] == "B" and stack_l:
        stack_l.pop()
    elif command[0] == "P":
        stack_l.append(command[1])

print("".join(stack_l + list(reversed(stack_r)))) #join은 파이썬에서 합치는 함수다.

시간이 굉장히 짧은 문제이다. 그래서 input은 사용하면 안 된다.

대신 sys.stdin.readline을 이용해서 입력을 컨트롤해줘야 한다. (가장 빠르게 입력 가능함)

또한, 이 문제에서 포인트가 스택을 2개 만든다는 발상이다.

오른쪽은 스택을 뒤집어서 빼야 한다. (스택은 입출구가 하나다.)

---

여기에서 command는 커서의 역할을 해준다.

그리고 문제에서 나왔듯 경우의 수를 나누어서 계산해야 한다. (그림 참고)

이후 모든 if문이 끝나면 스택에 데이터들이 들어갈 것이고, join 함수로 합쳐준다. (합칠 때에는 공백에 넣어주면 됨.)

 

결론

매우 어려웠음. 구글링 안 하면 모름..