๋ฌธ์ :
https://programmers.co.kr/learn/courses/30/lessons/12973
ํ์ด :
์์ : "baabaa"
๋๊ฐ์ฉ ์ง ์ง์ผ๋ฉด ๋ฌธ์์ด์์ ์ ๊ฑฐ ํ ์ ์์ผ๋ฏ๋ก,
์ฒ์๋ถํฐ ์ํํ์ฌ ๋๊ฐ ๋์ค๋ ์์๊ฐ ์์ผ๋ฉด string์์ ์ ๊ฑฐํ๊ณ ๋ค์ ์ธ๋ฑ์ค๋ฅผ ์ฒ์์ผ๋ก ํ์ฌ string ๊ธธ์ด๊ฐ ์ธ๋ฑ์ค๋ณด๋ค ์์์ง๋๊น์ง ๋ฐ๋ณตํ์๋ค. ํ์ง๋ง O(n^2) ์๊ฐ ๋ณต์ก๋์๊ธฐ ๋๋ฌธ์ ํจ์จ์ฑ์์ ์๊ฐ ์ด๊ณผ ์๋ฉ ์ป์๋ค ใ
๋ธ๋ก๊ทธ๋ฅผ ์ฐธ๊ณ ํด stack ์๋ฃ ๊ตฌ์กฐ๋ฅผ ์ด์ฉํ ๋ฐฉ๋ฒ๋๋ก ํ ์ ์๋ค๋ ๊ฒ์ ์๊ฒ ๋์๊ณ ๋ค์ ํ์ด๋ณด์๋ค.
ํจ์จ์ฑ ์๋ฌ c++ ์ฝ๋ :
#include <iostream>
#include<string>
using namespace std;
int solution(string s)
{
int i = 0;
while(true){
if(i > s.length()){
break;
}
char target = s[i];
if(i+1 < s.length() && s[i+1] == target){
s.erase(i, 2);
i = 0; // ์ด๊ธฐํ -> ์ฒ์๋ถํฐ ๊ฒ์ฌ
}
else {
i++; // ๋ค์ ํ๊ฒ์ผ๋ก ๋์ด๊ฐ
}
}
if(s.length() == 0){
return 1;
}
return 0;
}
ํจ์จ์ฑ ์ป์ c++ ์ฝ๋ :
#include <string>
#include <stack>
using namespace std;
int solution(string s) {
stack<char> str;
for (int i = 0; i < s.length(); i++) {
if (str.empty() || str.top() != s[i]) {
str.push(s[i]);
} else if (str.top() == s[i]) {
str.pop();
}
}
if (str.empty()) return 1;
return 0;
}
๊ฒฐ๊ณผ :
'Algorithm๐ฐ > ํ๋ก๊ทธ๋๋จธ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[ํ๋ก๊ทธ๋๋จธ์ค] Swift 2020 ์นด์นด์ค ์ธํด์ญ ํคํจ๋ ๋๋ฅด๊ธฐ (0) | 2022.04.08 |
---|---|
[ํ๋ก๊ทธ๋๋จธ์ค] ํ๊ฒ ๋๋ฒ DFS C++ (0) | 2022.03.25 |
[ํ๋ก๊ทธ๋๋จธ์ค] ๊ฐ์ฅ ํฐ ์ STL(sort) (0) | 2022.03.25 |
[ํ๋ก๊ทธ๋๋จธ์ค] ํํธ์ง 2021 ์นด์นด์ค ์ธํด์ญ STL(set) (0) | 2021.09.09 |
[ํ๋ก๊ทธ๋๋จธ์ค] ๊ฑฐ๋ฆฌ๋๊ธฐ ํ์ธํ๊ธฐ 2021 ์นด์นด์ค ์ธํด์ญ DFS (0) | 2021.09.05 |
๋๊ธ