프로그래머스 : 짝지어 제거하기 [C++]

문제 링크

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

 

문제 설명

1. 알파벳 소문자로 이루어진 문자열이 매개변수로 주어진다.
2. 문자열에서 같은 알파벳이 2개가 붙어 있는 짝을 찾습니다.
3. 같은 알파벳 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다
4. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기 종료
5. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 리턴값 반환하기.
6. 성공적으로 수행은 1리턴, 아닐 경우 0 리턴

 

문제 입출력 예)

s	result
baabaa	1
cdcd	0

 

문제 풀이1

• 반복문을 사용해서, 앞과 뒤의 값이 같은지 확인하면 된다.

1. for 문을 활용하여 배열[i], 배열[i+1]의 값이 같은지 확인한다.
2. 같으면 제거하고, 아니면 다음 i값으로 이동한다.

#include <iostream>
#include <string>
using namespace std;


int solution(string s)
{
    int count = 0;
    while(count>=0){
        for(int i=0; i<s.size(); i++){
            if(s[i] == s[i+1]){
                s.erase(i,2);
                count++;
                break;
            }
        }
        count--;
    }
    return s.size()==0?1:0;
}

 

 

O(N^2)의 시간이 소요되었고,

효율성 테스트에서 실패 (시간 초과)가 되었다.

위의 소스코드는 중간에서 값을 삭제하게되면

처음부터 순회를 돌아야 하기 때문에 누가봐도,, 효율성이 떨어지는 코드였다.

 

 

문제 풀이2 - 스택

• stack을 활용해서 top의 값과 next의 값을 비교한다.

1. stack을 사용하도록 한다.
2. stack 값이 비었거나, top이 현재값과 다르면, 현재값을 push
3. top이 현재값과 같으면, top을 pop 하도록 한다.
4. stack의 결과값이 empty일 경우 1을 반환, 그렇지 않을경우 0을 반환한다.

#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();
    }
    return str.empty()?1:0;
}

Stack의 특징

자료 구조 중 하나로써, 상자에 물건을 쌓아 올리는 듯이

데이터를 쌓아 올리는 자료 구조이다. (Last In First Out)

• LIFO(Last In First Out)구조
• 스택 메모리의 영역에서 버퍼오버플로우 취약점을 이용한다.
• 재귀함수 호출할 때 사용한다.
• 깊이 우선 탐색 (DFS)에서 사용된다.
• 인터럽트처리, 수식 계산, 서브루틴 복귀 번지를 저장할 때 사용한다.

Stack 선언	#include <stack> stack<int> str; stack<char> str;
값 추가	str.push(1); str.push(2);
값 제거	str.pop(); str.pop();
상단 값 출력	str.top();
스택 사이즈 출력	str.size();
비어있는지 확인	str.empty();  비어있으면 true, 아니면 false 반환
요소 바꾸기	swap(stack1, stack2)

 

 

리뷰

• 자료구조 공부를 틈틈히 하도록 하자....