2022. 7. 23. 22:13ㆍ2022 땅울림 썸머코딩
입력값
테스트 케이스인 T, 명령문이 주어지고, 배열의 정수의 개수, 배열의 입력될 정수들을 입력받는다.
출력값
R을 입력받았을때 배열을 reverse해주고 D를 입력받았을때 첫번째 수를 버리는 명령문을 실행한다.그리고 실행후의 결과를 출력한다. 단, D는 배열이 비어있을 때 실행시 error를 출력한다.
『문제 접근 방법』
함수가 단순히 reverse와 첫 번째 원소 삭제뿐이어서 간단하게 해결할 수 있는 문제라고 생각했다. 그렇지만, 입력으로 받는 정수의 배열이 그냥 숫자가 아니라 [1,2,3]이런식의 문자열로 주어지는게 고민이 되었다. 그래서 처음에 접근했던 방식은 문자열자체를 하나씩 입력받되 cin자체를 이용해서 걸러보려고했다.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main() {
int T, length; //테스트 케이스,정수의 개수
string cmd; //명령문
cin >> T;
while (T--) {
vector<int>num_list; //정수들의 배열
cin >> cmd>>length;
int array_count = 2 + length + (length - 1); // '[',']'그리고 숫자들 ','의개수(숫자 -1)
while (array_count--) { //문자열을 하나씩 받아볼 생각이였다.
int num;
cin >> num;
if (!cin) { //int형이 아니면 입력에 실패하고
cin.clear(); //cin자체에 있는 flag를 초기화
cin.ignore(); //cin 버퍼를 초기화
} //즉 cin자체를 이용해서 int형이아닐때를 구분하려고했다.
else {
num_list.push_back(num);
}
}
for (auto& i : cmd) {
if (i == 'R') {
reverse(num_list.begin(), num_list.end());
}
else if (i == 'D') {
if (num_list.empty()) { cout << "error\n"; break; } //비어있을때 error
num_list.erase(num_list.begin()); //첫번째 삭제
}
}
if (!num_list.empty()) {
cout << "[";
for (int i = 0; i < num_list.size(); i++) {
if (i == num_list.size() - 1) {
cout << num_list[i];
break;
}
cout << num_list[i] << ",";
}
cout << "]\n";
}
}
}문제를 풀면서 여러 가지 오류를 발견하고 까다로운 문제라고 생각했다. 우선은 시간 초과가 발생해 고민하다가 reverse가 두 번이면 굳이 실행할 필요가 없음을 알았다. 또한, 명령문이 100,000번 주어질 수 있기 때문에 최악의 경우 reverse 연산을 100,000번 해야 할 수도 있겠구나 싶었다. 그래서, reverse를 이전에 실행했는지를 체크하기위해 bool변수를 만들었는데, 또 한번 벽에 막혔다. 왜냐하면, 명령문 'D'를 만나면 어쨌든 reverse를 해줘야 순서에 맞게 제거를 할텐데 reverse를 그때 마다 실행하면 RDRDRDRDRDRDRDRDRD...RDRD이런식으로 반복되면 결국 또 수많은 reverse연산을 해야겠구나 라는 생각이 들었기 때문이다. 그래서 고민하다가 이건 진짜 역순을 취하는게 아니라 취하는척을 하면되겠구나 싶었다. 그러니까, reverse를 하지않았을때는 배열의 앞에서 제거해주고, reverse를 했을때는 배열의 뒤에서 제거해주는 식이다.
다음은 떠오른 아이디어에 대한 수정한 코드이다.
for (auto& i : cmd) {
if (i == 'R') {
if (is_reverse == true) {//'R'이 홀수면 reverse해주고
is_reverse = false;
}
else { //'R'이 짝수면 reverse안해줌
is_reverse = true;
}
}
else if (i == 'D') {
if (num_list.empty()) { cout << "error\n"; break; }
if (is_reverse == true) { //reverse를 해줘야하는 상황이므로 뒤에서 삭제
num_list.pop_back();
}
else {
num_list.erase(num_list.begin());
}
}
}
if (is_reverse) {//마지막 출력전에 reverse여부확인후 딱 한번 실행
reverse(num_list.begin(), num_list.end());
is_reverse = false;
}
이렇게 했을 때 reverse연산이 딱 한번만 실행되어서 좀 뿌듯했다. 하지만 어김없이 오답이였고 반례들을 찾기위해서 여러가지 값들을 입력해보았다.
input RR
0
[]
output
input DDD
3
[1,2,3]
outputif (!num_list.empty()) {
cout << "[";
for (int i = 0; i < num_list.size(); i++) {
if (i == num_list.size() - 1) {
cout << num_list[i];
break;
}
cout << num_list[i] << ",";
}
cout << "]\n";
}
명령문이 R일때는 배열이 비어있어도 오류가 뜨면 안된다, 3개의 배열의 3개를 제외해주었으니 빈 배열 []를 출력해주어야하는데 나는 error조건을 배열이 비어있을때로 두었고 '[', ']'의 출력조건을 num_list가 비어있지 않을때로 설정을 해주어서 빈 배열일 경우와 error상황일때 구분을 할수가 없었다. 그래서 bool변수를 하나 더 만들어 error표시를 해주어야만 구분할수있겠다고 생각했다.
else if (i == 'D') {
if (num_list.empty()) { is_error = true; break; } //에러일때 true로 전환해서 표시함
if (is_error) { //에러가 true일때 출력해주기
cout << "error\n";
continue;
}
else { //에러가 false이면 이전에 처리방식대로 출력 reverse유무 탐색후 ~이렇게 수정을 조금 해주니 error와 비어있을때는 구분이 되었다. 하지만 오답이나왔고, 또 다른 반례를 찾았는데, 내가 사용한 !cin과 cin.ignore(), cin.clear()과 관련된 문제인것같다.
처음에 빈 배열을 입력했고 그다음에 D를 넣고 length 변수를 입력하지 않았는데 자동으로 []가 출력이 돼버린다;; 그런데 세 번째 testcase에서는 잘 실행이 된다.. cin에 대해 좀 알아보았지만 정확한 이유를 모르겠다. //질문하기//
결론은 입력 방법을 바꿔야겠다고 생각했다. 여기서 또 고민을 많이 했는데. 나는 string에 + 연산이 된다는 것이 떠올랐다, 입력 변수와 벡터를 string으로 바꾸어주고 string의 i 번째 인덱스로 비교하는데 i 번째-'0'이 (0~10]의 범위에 있으면 임시 string에 더해주고 ','와 ']'를 만났을 때 s가 기본값이 아니면 벡터에 넣어주는 형식이다.
s = ""; //임시변수 s 초기화
cin >> num;
for (auto i : num) {
if (i - '0' >= 0 && i - '0' < 10) {
s += i; //처음엔 0을 포함하지않아서 10을 입력하면 1로 저장되었다.
}
else if (i ==','||i == ']') {
if (s != "") {
num_list.push_back(s);
s = "";
}
}
}
이렇게 하니 다시 시간 초과가 떴다. 나는 그래서 reverse 한 번조차 하면 안 되는 건가 하고 고민하다가 처음에 코드를 구성할 때 vector에 첫 번째 원소 삭제함 수로 pop_front가 있는 줄 알았다. 하지만, 없어서 erase(vector.begin())이 함수를 사용했는데 이게 계속 찝찝했다 뭔가. 그래서 erase 함수를 검색해 보니 이 함수로 첫 번째 원소를 삭제하면 shift 연산이 일어나 시간이 많이 사용되는 것이었다. 자료구조시간에 배우면 뭐 하나,, 이렇게 쉽게 까먹는데 하여튼 앞에서 삭제가 용이한 방법은 다행히 바로 떠올랐다 deque였다. 양방향으로 삭제가 가능하니 shift 연산도 필요 없고 바로 적용해 보았다. 결국 정답을 맞혔다.. 너무 많은 오류를 계속 찾다 보니 자신감이 많이 떨어져서 정답을 맞히고 너무나 기뻤던 것 같다.
정답코드
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
string cmd;
bool is_error;
bool is_reverse;
cin >> T;
while (T--) {
int length;
is_error = false;
is_reverse = false;
string num,s;
deque<string>num_list;
cin >> cmd >> length;
s = "";
cin >> num;
for (auto i : num) {
if (i - '0' >= 0 && i - '0' < 10) {
s += i;
}
else if (i ==','||i == ']') {
if (s != "") {
num_list.push_back(s);
s = "";
}
}
}
for (auto& i : cmd) {
if (i == 'R') {
if (is_reverse == true) {
is_reverse = false;
}
else {
is_reverse = true;
}
}
else if (i == 'D') {
if (num_list.empty()) { is_error = true; break; }
else {
if (is_reverse == true) {
num_list.pop_back();
}
else {
num_list.pop_front();
}
}
}
}
if (is_error) {
cout << "error\n";
continue;
}
else {
if (is_reverse) {
reverse(num_list.begin(), num_list.end());
}
cout << "[";
for (int i = 0; i < num_list.size(); i++) {
if (i == num_list.size() - 1) {
cout << num_list[i];
break;
}
cout << num_list[i] << ",";
}
cout << "]\n";
}
}
}느낀점
이번 문제는 생각보다 너무 어렵게 풀어서 기가 많이 빨렸다. 그래도 멘탈이 많이 좋아진것같다. 코드를 바꿀때도 조금 수월하게 짱구가 굴러가는것같아서 기분이 좋다. 어려웠던점은 위에 줄줄이 많이쓴것같아서 여기에 쓸내용이 떠오르지가 않는것같다..