백준_5430_AC

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

 

 

뒤집기와 삭제(R과 D) 명령과 숫자 배열을 입력받은 뒤,

명령에 따라 배열을 뒤집거나 삭제하는 문제이다.

 

 

이 문제를 보고

 

배열을 숫자만 입력받는게 아닌데 어떻게 처리해야하지? 

 

라는 생각이 들었다.

 

생각을 하면서 두 가지 과정을 거치면 해결할 수 있을 것 같았다.

1. 배열의 처음과 끝은 무조건 대괄호이므로 이를 먼저 제거한다.

2. 문자열에서 쉼표를 찾아 쉼표 이전의 문자열을 숫자로 변환

 

 

아래 코드에서 tmp는 입력받은 배열을 저장한 string 이고, d는 int를 저장하는 deque이다.

deque를 사용한 이유는 아래서.

      tmp = tmp.substr(1, tmp.size() - 2);  //대괄호를 제거

      size_t pos = 0;
      size_t start = 0;
      while (true) {
        pos = tmp.find(',', start);  //쉼표를 찾는다
        if (pos == std::string::npos) break;  //더이상 쉼표가 없으면 반복종료

        //쉼표 이전의 문자열을 숫자로 변환에서 deque에 넣는다
        int token = stoi(tmp.substr(start, pos - start));
        d.push_back(token);
        start = pos + 1;  //다음 쉼표를 찾기 위해 start위치이동
      }

      //만약 배열에 남은 숫자가 있으면 마지막 숫자까지 추가
      if (start < tmp.size()) { 
        d.push_back(stoi(tmp.substr(start)));
      }

 

이제 문자열로 입력받은 배열을 숫자 배열로 만드는데 성공했으니

입력받은 명령에 따라 배열을 처리해야 한다.

 

R -> 배열 뒤집기

D -> 배열 삭제하기 ( 배열이 비어있으면 error 출력 )

 

R을 입력받을 때마다 배열을 뒤집는 행위는 매우 비효율적이다. (실제로 그렇게 구현해서 시간초과가 났었음)

 

명령으로 수많은 R만을 입력받는다면 시간이 매우 오래 걸릴 것이다.

 

R을 홀수 번 입력받으면 뒤집고, 짝수 번 입력받으면 처음 상태와 동일하므로,

이를 적용하기 위해 bool형의 IsReverse 변수를 사용했다.

 

그리고, 여기서 deque를 사용한 이유가 나온다.

D명령어를 처리할 때 배열을 뒤집고 처리해야 할 떄가 있다.

 

그때마다 뒤집고 삭제하고를 반복하면 시간이 매우 오래 걸리므로

배열을 앞뒤로 넣고 삭제하고가 가능한 deque를 사용한 것이다.

 

pop_back을 하면 뒤집고 삭제하는 것과 동일한 작업을 하는 것이므로 시간을 아낄 수 있다는 장점이 있다.

(다만, 출력할 때 배열은 뒤집힌 상태로 출력해야 하므로 출력하는 부분에서 이를 신경써줘야 한다.)

 

또, 빈 배열을 삭제하려 하면 IsError을 참으로 만들고 반복문을 종료한다.

bool IsReverse = false;
bool IsError = false;

for (auto k : str) {
  if (k == 'R') {
    IsReverse = !(IsReverse);
  } else if (k == 'D' && d.empty()) {
    IsError = true;
    break;
  } else if (k == 'D' && IsReverse) {
    d.pop_back();
  } else {
    d.pop_front();
  }
}

 

 

이제 출력하는 부분을 살펴보자.

에러인 경우, 빈 배열인 경우, 둘 다 아닌 경우를 나누어서 출력해주고 

다음 수행을 위해 deque를 비워준다.

 

출력 함수를 호출할 때, 이 배열을 뒤집어야 하는지를 판별해주는 IsReverse변수를 꼭 같이 넣어줘야 한다.

if (IsError) {
  std::cout << "error" << '\n';
  d.clear();
} else if (d.empty()) {
  std::cout << "[]" << '\n';
} else {
  PrintDeque(d, IsReverse);
  d.clear();
}

 

위에서 호출하는 출력 함수도 살펴보자.

 

IsReverse가 참일 때와 거짓일 때로 나누어서 

역순 혹은 원래 순서대로 출력해주면 된다.

 

다만, 출력할 때 [1,2,3,4] 의 형태로 출력해야 하기 때문에

처음과 마지막에 대괄호를 출력해주고

 

배열의 마지막 값이 아닌 경우에 ',' 까지 함께 출력하는 부분을 넣어주었다.

void PrintDeque(std::deque<int> d, bool IsReverse) {
  std::cout << '[';

  if (IsReverse) {
    for (auto i = d.rbegin(); i != d.rend(); i++) {
      if (i != d.rbegin()) std::cout << ',';
      std::cout << *i;
    }
  } else {
    for (int i = 0; i < d.size(); i++) {
      if (i != 0) std::cout << ',';
      std::cout << d[i];
    }
  }

  std::cout << ']' << '\n';
}

 

 

문제만 보면 쉬워보이지만,

생각 없이 풀면 시간 초과 혹은 오답이 나올 수 있는 문제였던 것 같다.

 

앞으로 무지성 풀이가 아니라 시간 복잡도도 계산하면서 풀어야겠다는 생각이 들게 하는 문제였다.

 

전체 코드)

// #include <bits/stdc++.h>

#include <algorithm>
#include <deque>
#include <iostream>
#include <string>

void PrintDeque(std::deque<int> d, bool IsReverse) {
  std::cout << '[';

  if (IsReverse) {
    for (auto i = d.rbegin(); i != d.rend(); i++) {
      if (i != d.rbegin()) std::cout << ',';
      std::cout << *i;
    }
  } else {
    for (int i = 0; i < d.size(); i++) {
      if (i != 0) std::cout << ',';
      std::cout << d[i];
    }
  }

  std::cout << ']' << '\n';
}

int main(void) {
  std::ios::sync_with_stdio(false);
  std::cin.tie(NULL);

  int N;
  std::cin >> N;

  std::string str;
  std::deque<int> d;
  for (int i = 0; i < N; i++) {
    std::cin >> str;

    int len;
    std::cin >> len;

    bool IsReverse = false;
    bool IsError = false;

    std::string tmp;
    if (len == 0) {
      std::cin >> tmp;
    } else {
      std::cin >> tmp;

      tmp = tmp.substr(1, tmp.size() - 2);

      size_t pos = 0;
      size_t start = 0;
      while (true) {
        pos = tmp.find(',', start);
        if (pos == std::string::npos) break;

        int token = stoi(tmp.substr(start, pos - start));
        d.push_back(token);
        start = pos + 1;
      }

      if (start < tmp.size()) {
        d.push_back(stoi(tmp.substr(start)));
      }
    }

    for (auto k : str) {
      if (k == 'R') {
        IsReverse = !(IsReverse);
      } else if (k == 'D' && d.empty()) {
        IsError = true;
        break;
      } else if (k == 'D' && IsReverse) {
        d.pop_back();
      } else {
        d.pop_front();
      }
    }

    if (IsError) {
      std::cout << "error" << '\n';
      d.clear();
    } else if (d.empty()) {
      std::cout << "[]" << '\n';
    } else {
      PrintDeque(d, IsReverse);
      d.clear();
    }
  }
}