<Programmers> Lv2. String, Stack_짝지어 제거하기 c++
Solution 1
- 탐색하다가 2개가 겹쳐서 나오는 부분이 있으면 해당 부분을 '_'으로 만들어주고 다시 처음부터 순회하는 방법을 사용했다
- 문자열의 길이는 최대
1,000,000
이므로O(N^2)
의 시간 복잡도를 가지므로 최대1,000,000 X 1,000,000
의 시간 복잡도를 가지게 되어 효율성에서 틀렸다
#include <iostream>
#include<string>
using namespace std;
int solution(string s) {
bool flag=true;
while (flag) {
flag=false;
for (int i=1; i<s.length(); i++) {
int prev=i-1;
int cur=i;
if (s[prev]=='_') continue;
if (s[cur]=='_')
while (cur<s.length() && s[cur]=='_') cur++;
if (s[prev]==s[cur]) {
s[prev]=s[cur]='_';
flag=true;
break;
}
}
}
for (int i=0; i<s.length(); i++)
if (s[i]!='_') return 0;
return 1;
}
Solution 2
Stack
을 사용하여 글자를 하나씩 넣어보며 top에 있는 글자와 현재 넣으려는 글자가 같으면 pop을 하고 아니면 하나씩 넣으며 확인한다O(N)
의 시간 복잡도를 가짐
#include <iostream>
#include<string>
#include <stack>
using namespace std;
int solution(string s) {
stack<char>str;
for (auto i: s) {
if (str.empty() || str.top()!=s[i])
str.push(s[i]);
else if (str.top()==s[i]) str.pop();
}
if (str.empty()) return 1;
else return 0;
}
Author And Source
이 문제에 관하여(<Programmers> Lv2. String, Stack_짝지어 제거하기 c++), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@kimmy/Programmers-String-Stack짝지어-제거하기-c저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)