짝지어 제거하기 C++(팁스다운2017)[프로그래머스]

※ 저의 풀이가 무조건적인 정답은 아닙니다.

다른 코드가 좀더 효율적이고 좋을 수 있습니다.

다른사람들의 풀이는 언제나 참고만 하시기 바랍니다.

문제 주소입니다.

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

코딩테스트 연습 - 짝지어 제거하기 | 프로그래머스

 

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

3.1 주석 없는 코드

3.2 주석 있는 코드

3.3 테스트 코드

4. 결과

 

---

1. 문제 설명

문제!!

짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다. 예를 들어, 문자열 S = baabaa 라면 b aa baa → bb aa → aa → 의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

 

제한사항

문자열의 길이 : 1,000,000이하의 자연수 문자열은 모두 소문자로 이루어져 있습니다.

 

예시

s	return
"baabaa"	1
"cdcd"	0

 

입출력 예 #1 위의 예시와 같습니다. 입출력 예 #2 문자열이 남아있지만 짝지어 제거할 수 있는 문자열이 더 이상 존재하지 않기 때문에 0을 반환합니다.

 

---

2. 문제풀이

이번 문제는 효율성테스트를 통과하기 위해서 고생을 했었습니다. 처음에는 단순하게 2개가 겹쳐서 나오면 그부분을 제거하고 처음부터 순회를 돌았습니다. 그랬더니 O(N^2)의 시간이 걸렸고 역시나 효율성 테스트에서 광탈했습니다.   그래서 자료구조를 통한 속도향상을 기대했습니다. 중간에 삭제를하고 비교하는 과정에서 시간을 줄여야 된다고 생각했고, 중간에 사라지면 사라진 앞부분과 뒷부분끼리 다시 비교를 하면 된다고 생각해서 스택을 이용했습니다.   스택이 비어있거나 top부분이 현재 문자와 다르다면 스택에 푸쉬합니다. 만약 스택의 top부분과 현재문자가 일치한다면 pop을 합니다. 그렇다면 자연스럽게 다음부분과 그전부분과의 비교가 이루어집니다. 이로인해 순회는 한번만 하면되므로 O(N)의 시간이 걸렸습니다.   추가적으로 글자의 개수가 홀수인경우 짝지어 없앨수 없다고 생각해서 홀수인경우 바로 1을 리턴하도록 추가했습니다.(그런데 글자가 홀수인경우가 없는거같네요)

 

---

3. 소스코드

3.1 주석없는 코드

#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;
}

3.2 주석있는 코드

#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();
    }
    //스택이 비어있다면 모두제거한것이므로 1리턴
    if (str.empty())    return 1;
    return 0;
}

3.3 테스트 코드 추가

#include <string>
#include <stack>
#include <iostream>
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();
    }
    //스택이 비어있다면 모두제거한것이므로 1리턴
    if (str.empty())    return 1;
    return 0;
}
 
void print(string s, int answer) {
    int t = solution(s);
    if (t == answer)
        cout << "정답" << endl;
    else
        cout << "틀림" << endl;
}
 
int main() {
    print("baabaa", 1);
    print("cdcd", 0);
    return 0;
}

 

---

4. 결과