문제 설명 처럼 2개 짝짓고 제거하면 시간초과로 풀 수 없다. 첫 풀이는 다음과 같았다. 먼저 abcc 이런식으로 a, b가 홀수개이면 절대 문장은 제거되지 않는다. 그렇기 때문에 먼저 원소들의 개수를 세는 작업을 했고 이 작업을 통과하였을 때 제거 연산을 해봤다. 그러나 별짓을 다 해도 저 3개의 효율 테스트를 통과할 수가 없었다... 결국 아이디어를 구하기 위해 질문하기를 보았는데 답은 "스택" 이었다. 최대 크기가 100만일 때 부터 알아봤어야하는데 나는 아직 멀었다. 85점까진 받았기 때문에 코테나 대회였다면 바로 넘겼을 문제이기는 하다.
스택을 사용한다.
ex) dcaabbcd 가 들어왔을 때
1. d를 꺼내 c와 비교한다. 둘은 다르다! 그러므로 꺼낸 d를 또다른 서브 스택에 넣어둔다 .
현재 기존스택 : dcaabbc 서브스택: d
2. c를 꺼내 b와 비교한다. 둘은 또 다르다 . 그러므로 꺼낸 c를 서브스택에 넣는다.
현재 기존스택 : dcaabb 서브스택 : cd
3. b를 꺼내 b와 비교한다. 이번엔 서로 같다. 그러므로 꺼낸 b를 서브스택에 넣지 않고 버린다. 다음 b도 같으므로 버린다.
현재 기존스택 : dcaa 서브스택 : cd
4. a를 꺼내 a와 비교한다. 3번처럼 둘다 사라진다.
현재 기존스택 : dc 서브스택 : cd
5. c를 꺼내 d와 비교한다. 둘은 다르다. 그러나 서브스택의 top에 같은 것이 있다. 그러므로 서브스택의 c와 기존스택의 c 둘다 제거한다.
현재 기존스택 : d 서브스택 : d
6. 이제 비교 선택지는 한가지 이므로 이 둘이 같다면 return 1 다르다면 return 0이 된다.
무언가 한개씩 비교하고 나열하는 문제가 나오고 주어지는 배열의 길이가 길다고 판단되면 스택, 큐, 덱을 꼭 고려해보자!!
#include <iostream>
#include <string>
using namespace std;
string convert(string str){
string tmp = "";
for(int i = 0; i < str.size();){
if(i == str.size() - 1){
tmp.push_back(str[str.size() - 1]);
return tmp;
}
else if(str[i] == str[i + 1]){
i += 2;
continue;
}
tmp.push_back(str[i]);
i++;
}
return tmp;
}
int solution(string s)
{
int answer = -1;
int cnt[26 + 'a'] = {0,};
for(int i = 0; i < s.size(); i++){
cnt[s[i]]++;
}
for(int i = 0; i < 26; i++){
if(cnt[i + 'a'] % 2 != 0)
return 0; }
while(true){
string temp = s;
s = convert(s);
// cout << s << endl;
if(temp == s)
return 0;
else if(s.size() == 0)
return 1;
}
}
#include <iostream>
#include <string>
#include <stack>
using namespace std;
int solution(string s)
{
stack<char> stk;
stack<char> substk;
for(int i = 0; i < s.size(); i++){
stk.push(s[i]);
}
while(!stk.empty()){
int tmp = stk.top();
stk.pop();
if(!stk.empty() && tmp == stk.top())
stk.pop();
else if(!substk.empty() && tmp == substk.top())
substk.pop();
else
substk.push(tmp);
if(substk.empty() && stk.empty())
return 1;
}
return 0;
}
'프로그래머스 풀이 > Lv 2' 카테고리의 다른 글
프로그래머스 - 삼각 달팽이(c++) (0) | 2023.02.21 |
---|---|
프로그래머스 - 마법의 엘리베이터(C++) (0) | 2023.02.20 |
프로그래머스 - 귤 고르기(C++) (0) | 2022.12.26 |
프로그래머스 - 할인 행사 (C++) (0) | 2022.12.25 |
프로그래머스 - 혼자 놀기의 달인 (C++) (0) | 2022.11.27 |