[백준 1406번] 에디터

 

https://www.acmicpc.net/problem/1406

 

수정전 

message = gets.chomp.to_s
N = message.length
M = gets.chomp.to_i
cursor = N
for i in 0...M
  view = gets.chomp.split.map(&:to_s)
  if view[1] == nil
    if view[0] == 'L' && cursor != 0
      cursor -= 1
    elsif view[0] == 'D' && cursor != message.length
      cursor += 1
    elsif view[0] == 'B' && cursor != 0
      message[cursor - 1] = ""
      cursor -= 1
    end
  else
    message.insert(cursor, view[1])
    cursor+=1
  end
end

print message

 

 

수정후 

left_stack = gets.chomp.chars
right_stack = []

M = gets.chomp.to_i

M times do
  command = gets.chomp.split

  case command[0]
  when 'L'
    if !left_stack.empty?
      right_stack.push(left_stack.pop)
    end
  when 'D'
    if !right_stack.empty?
      left_stack.push(right_stack.pop)
    end
  when 'B'
    if !left_stack.empty?
      left_stack.pop()
    end
  when 'P'
    left_stack.push(command[1])
  end
end

puts (left_stack + right_stack.reverse).join

 

 

정말 최고의 걸작 문제다!

처음에는 단순히 커서를 이동하면서 해당 인덱스에 문자를 추가하거나 삭제하는 간단한 문제일 줄 알았다. 쉽게 구현했지만, 60%에서 시간 초과가 발생했다!

문제를 분석해 보니, 역시나 N이 최대 100,000, M이 최대 500,000까지 가능했다. 즉, 최악의 경우 문자열 중간에 100,000번 삽입이 발생하면, 뒤에 있는 문자들이 모두 한 칸씩 밀려나야 하므로 O(N) 시간이 걸린다. 따라서 전체 시간 복잡도는 O(N × M) 이 되어 비효율적이다.

이 문제를 해결하려면 스택을 활용해야 한다.
위 코드처럼 스택 두 개를 사용하여 커서 왼쪽은 left_stack, 커서 오른쪽은 right_stack에 저장하는 방식으로 해결할 수 있다.
이 방식에서는 어떤 명령어가 들어오든 각 문자는 한 번만 이동하므로, 전체 시간 복잡도는 O(M) 이다.

시간 복잡도를 분석할 때 중요한 것은 단순한 연산 횟수가 아니라, "한 문자가 몇 번 이동하는지"이다.

정말 좋은 문제였다! 🚀