๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
Algorithm๐Ÿฐ/ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ์ง์ง€์–ด ์ œ๊ฑฐํ•˜๊ธฐ stack

by Jouureee 2022. 3. 25.

๋ฌธ์ œ :

https://programmers.co.kr/learn/courses/30/lessons/12973

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์ง์ง€์–ด ์ œ๊ฑฐํ•˜๊ธฐ

์ง์ง€์–ด ์ œ๊ฑฐํ•˜๊ธฐ๋Š”, ์•ŒํŒŒ๋ฒณ ์†Œ๋ฌธ์ž๋กœ ์ด๋ฃจ์–ด์ง„ ๋ฌธ์ž์—ด์„ ๊ฐ€์ง€๊ณ  ์‹œ์ž‘ํ•ฉ๋‹ˆ๋‹ค. ๋จผ์ € ๋ฌธ์ž์—ด์—์„œ ๊ฐ™์€ ์•ŒํŒŒ๋ฒณ์ด 2๊ฐœ ๋ถ™์–ด ์žˆ๋Š” ์ง์„ ์ฐพ์Šต๋‹ˆ๋‹ค. ๊ทธ๋‹ค์Œ, ๊ทธ ๋‘˜์„ ์ œ๊ฑฐํ•œ ๋’ค, ์•ž๋’ค๋กœ ๋ฌธ์ž์—ด์„ ์ด์–ด ๋ถ™

programmers.co.kr

 

ํ’€์ด :

์˜ˆ์‹œ : "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;
}

๊ฒฐ๊ณผ :

๋Œ“๊ธ€