백준 1406 S2 에디터

문제: 에디터

풀이 접근 과정

• 지우고 삽입하는 것을 버퍼에 마킹하고 출력할 때 한꺼번에 처리하려고 했는데, 같은 위치에 지우고 삽입하고 지우고 삽입하고 반복된 명령이 들어오는 경우 처리가 불가능해서, 실제로 지우고 삽입을 진행
• 문자열 중간에서 삽입과 삭제가 빈번하게 일어날 것이므로, std::list 자료구조를 채택.

코드

#include <iostream>
#include <string>
#include <list>

using namespace std;

#define CMD_I 0
#define ARG_I 2

int main() {
  string str; cin >> str; // [a-z], [100'000]
  int M; cin >> M; // [1, 500'000]

  cin.ignore(); 

  list<char> l_str(str.begin(), str.end());

  // 커서는 자기가 가리키는 문자 바로 앞의 위치에 있음
  auto cursor = l_str.end();

  for (int i = 0; i < M; ++i) {
    string  i_cmd; getline(cin, i_cmd);

    switch (i_cmd[CMD_I]) {
      case 'L': // 커서를 왼쪽으로 한 칸 옮기기
        if (cursor != l_str.begin()) {
          cursor = prev(cursor);
        }
        break;

      case 'D': // 커서를 오른쪽으로 한 칸 옮기기
        if (cursor != l_str.end()) {
          cursor = next(cursor);
        }
        break;

      case 'B': // 커서 왼쪽에 있는 문자 삭제
        if (cursor != l_str.begin()) {
          cursor = l_str.erase(prev(cursor));
        }
        break;

      case 'P': // 왼쪽에 인자로 전달된 문자 추가
          cursor = next(l_str.insert(cursor, i_cmd[ARG_I]));
        break;
    }
  }

  for (char c: l_str) cout << c;
}

기타 문법적 사항

반복자 이동

• prev, next
  • 한칸 단위로 이동하는 경우 ++나 -- 쓰는 것이 간결하고 가독성에도 좋음.
  • 결론: 반복자를 여러 칸 오른쪽이나 왼쪽으로 이동시키고 싶을 때 쓰자.
• 반복자 범위 초과
  • 시작 반복자에서 --나 prev 쓰는 것은 정의되지 않은 행동임.
  • 끝 반복자에서 ++나 next 쓰는 것은 정의되지 않은 행동임.

반복자를 사용한 C++ 컨테이너의 삽입과 삭제

• 반복자 무효화
  • 컨테이너 요소의 삽입 & 삭제 연산을 하고 나면 그 이전의 반복자는 무효화(Invalidate) 되며, 무효화된 반복자를 사용하는 것은 정의되지 않은 행동임.
  • 단 std::list와 std::forward_list는 삽입 시에는 반복자가 무효화 되지 않고, 삭제 시에는 삭제한 요소를 가리키고 있던 반복자만 무효화됨. ¹
• erase의 동작
  • 반복자가 가리키는 위치에 있는 요소를 삭제하고, 삭제한 요소의 오른쪽에 위치했던 반복자를 반환함.
• insert의 동작
  • 반복자가 가리키는 위치의 왼쪽에 새 요소를 삽입하고, 새 요소를 가리키는 반복자를 반환함.

한 줄 입력

• std::cin은 공백까지만 입력을 받아서, 문제에서 제시하는 P x같은 명령을 한번에 받을 수 없음.
  • 사실, P가 들어왔으면 std::cin을 한번 더 사용하는 것으로 해결되기는 함
• C++에서는 한 줄 입력에 std::getline을 사용.
  • std::cin은 '\n'을 처리하지 않고 입력 버퍼에 남겨두고, std::getline은 '\n'을 입력 버퍼에서 가져와 처리하려고 하므로, 둘을 연속해서 쓰면 문제가 발생할 수 있음.
  • std::cin.ignore를 호출하여 입력 버퍼의 맨 앞 문자 하나를 지워주는 것이 좋음.

다른 풀이?

• std::stack 두개나, std::deque 두 개로도 풀 수 있음. 커서를 기준으로 왼쪽 문자열과 오른쪽 문자열로 나누어서, 해당 경계에서만 삽입과 삭제가 일어나도록 하면 됨.
  • 애초의 문제풀이 의도는 이쪽?인 것 처럼 느껴지기도 함.

참고 문헌

• cin과 getline을 같이 사용할 때 cin.ignore()이 필요한 이유 기록/GoodLuck2Me2/티스토리