[백준] 1406. 에디터 풀이 / Python, JavaScript

1406번: 에디터

 

작성 코드 (.py)

import sys
input = sys.stdin.readline

ls, rs = list(input())[:-1], []
n = int(input())
for _ in range(n):
    inp = list(input().split())
    op = inp[0]
    if op == "L":
        ls and rs.append(ls.pop())
    elif op == "D":
        rs and ls.append(rs.pop())
    elif op == "B":
        ls and ls.pop()
    elif op == "P":
        ls.append(inp[1])
print("".join(ls) + "".join(reversed(rs)))

작성 코드 (.js)

function solution(init, operations) {
  const [ls, rs] = [init.split(""), []];
  operations.forEach((oper) => {
    oper = oper.split(" ");
    let op = oper[0];
    if (op === "L" && ls.length) rs.push(ls.pop());
    else if (op === "D" && rs.length) ls.push(rs.pop());
    else if (op === "B" && ls.length) ls.pop();
    else if (op === "P") ls.push(oper[1]);
  });
  return ls.join("") + rs.reverse().join("");
}

 

구현 로직

최악의 경우를 고려해야 합니다. 명령어는 반드시 순회해야 하므로 명령어 수를 n으로 했을 때 순회문 안에서 선형 시간이 걸리는 insert(py)나 splice(js)를 사용한다면 최악의 경우의 수는 초기 문자열 길이 최대 (100,000) * 명령어 수(500,000) 이므로 100억이 넘어가기 때문에 선형 시간 내로 알고리즘을 짜야 합니다.

 

스택을 사용하여 문자열을 두 파트로 나누어 관리합니다.

abcd
3
P x
L
B

입력 예시가 위와 같을 때 수행 과정은 다음과 같습니다.

P x: 왼쪽 스택(ls)에 x를 푸시합니다.

ls = [a, b, c, d, x] , rs = []

L: 오른쪽 스택(rs)에 ls에서 pop한 것을 푸시합니다. 

ls = [a, b, c, d], rs = [x]

B: 왼쪽 스택에서 pop합니다.

ls = [a, b, c], rs = [x]

 

결과는 ls와 rs 요소를 합친 결과가 됩니다. 단 rs는 오른쪽 부분의 스택이기 때문에 문자열의 원래 순서를 고려해 뒤집은 결과를 합칩니다.