[프로그래머스]Lv2. 짝지어 제거하기

본 페이지는 C++ 독학을 위해 작성한 포스트입니다 풀이과정도 포함되어있지만 문법공부에 대한 비중이 있습니다.
(+  Java언어 내용도 포함되어있습니다. )

 

 

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

프로그래머스

 

 

1.문제설명

문제 설명
짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다.
먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다.
이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요.

성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다.예를 들어, 문자열 S = baabaa 라면b aa baa → bb aa → aa →의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

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

 

2. 문제해결 접근

• 자료구조(스택)을 사용한다
• 문자열을 처음부터 검사하여 스택의 top과 같다면 제거(pop) / 다르다면 삽입(push) 하는 로직으로 구현할 수 있다.
• 스택이 비어있다면 1을 반환, 남아있는 문자열이 있다면(else) 0을 반환하여 조건을 만족시킨다.

 

스택의 구조를 알고 있다면 쉽게 풀 수 있는 문제...

 

3. C++ 답안

1차시도

#include <iostream>
#include <string>

using namespace std;

int solution(string s)
{
	//answer는 0으로 초기화, 값이 남아있으면 0을 반환한다
    int answer = 0;

    for(int i = 0 ; i < s.size(); i++ )
    {
        if(s.size() <= 1)
            break;
		// 순차적으로 각 인덱스의 문자를 비교한다.
        // 문자와 다음인덱스의 문자가 같다면 
        if(s[i] == s[i + 1])
        {
        	//두 문자를 모두 제거 (erase) 한다
            s.erase(s.begin() + i);
            s.erase(s.begin() + i);
            // 문자를 제거한 후에는 처음부터 다시 검사한다.(다음문자가 달라지기 때문에)
            i = 0;
        }
       
    }
    cout << s ;
	// 배열이 비어있을경우 1을 반환한다,
    if(s.empty())
        answer = 1;

    return answer;
}

... 시간초과가 뜬다...!

 

 

#include <iostream>
#include<string>
#include <stack>

using namespace std;
    // 스택사용을 위한 초기화 선언
    stack<char> str;

int solution(string s){
    int answer = -1;

    for(int i = 0; i<s.size();i++)
    {
        // 스택이 비어있거나 || i인덱스의 글자와 다르면, stack에 추가(push)
        if(str.empty() || str.top()!=s[i]) str.push(s[i]);
        else if(str.top() == s[i]) str.pop();
    }
    
    // 스택이 비어있다면? 모든 문자가 짝을 이뤄 삭제된것
    if( str.empty() ) answer = 1;
    else answer = 0;
    

    return answer;
}

 

4.  자료구조 개념 및 관련 문법

스택(Stack)

물건을 쌓아 올린 더미 또는 쌓는 행위

자료 구조에서 스택은 데이터를 쌓아 올리듯이 저장하는 선형 자료구조로 후입선출 원리에 따라 삽입과 삭제가 수행됨

데이터의 입출력이 한쪽 방향에서만 수행되는 리스트

 

 

 

스택의 주요 연산

push( e ) -  스택의 맨 위에 원소 e를 추가
pop()    - 스택의 맨 위에 있는 원소를 삭제
top()    - 스택의 맨 위에 있는 원소를 참조. peek()
empty()    - 스택이 비어있으면 true 반환
size()    - 스택의 원소 개수를 반환
search(Object o) -  해당 Object의 위치를 반환

 

스택의 구현

문제의 종류에 따라 배열보다 스택에 데이터를 저장하는 것이 더 적합한 방법일 수 있다.

• 배열과 달리 스택은 상수 시간에 i번째 항목에 접근할 수 없다.
• 하지만 스택에서는 데이터를 추가하거나 삭제하는 연산은 상수 시간에 가능하다.
• 배열처럼 원소들을 하나씩 옆으로 밀어줄 필요가 없다.

-재귀 알고리즘
재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.

 

-웹 브라우저 방문기록 (뒤로가기)
-실행 취소 (undo)
-역순 문자열 만들기
-수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)
 Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
-후위 표기법 계산

스택(Stack)은 연결리스트 로 구현할 수 있다. 연결리스트의 같은 방향에서 아이템을 추가하고 삭제하도록 구현한다.

 

https://gmlwjd9405.github.io/2018/08/03/data-structure-stack.html

[자료구조] 스택(Stack)이란 - Heee's Development Blog