2017 팁스다운: 짝 지어 제거하기

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

코딩테스트 연습 - 짝지어 제거하기

해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다.

문자가 연속되는 경우에만 이를 삭제한다.

 

풀이법

1) 효율성과 정확성을 고려한다면 stack을 이용하면 문제를 쉽게 풀 수 있다.

2) 스택의 맨 위 값과 새로 들어오는 값을 비교하여 두 값이 같으면 pop, 다르면 push 해준다

3) 최종 stack의 크기가 0이면 모두 짝 지어서 제거된 것이고, 아닐 경우 제거할 수 없는 경우이다.

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

int solution(string s)
{
    int answer = 0;
    stack<char> st;
    for(int i=0; i<s.size();i++)
    {
        if(st.empty())
        {
            st.push(s[i]);
        }
        else if(st.top()==s[i])
        {
            st.pop();
        }
        else
        {
            st.push(s[i]);
        }
    }
    if(st.size()==0)
    {
        answer=1;
    }
    return answer;
}

주의사항)

스택만 생각해 냈다면 어렵지 않게 해결할 수 있는 문제이다.

아래 있는 코드는 정답에는 도달할 수 있으나 효율성에서 0점을 맞은 코드이다.

그러나, string 클래스의 substr과 resize의 사용법에 대해 재고할 수 있는 코드이기에 첨부하였다.

 

효율성이 박살난 코드

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

int solution(string s)
{
    int answer = 0;
    bool check = false;
    while (!s.empty())
    {

        for (int i = 0; i < s.size() - 1; i++)
        {
            int j = i + 1;
            if(j>=s.size())
            {
                break;
            }
            if (s[i] == s[j])
            {
                string s1;
                s1 = s.substr(j + 1);
                s.resize(i);
                s = s + s1;
                check = true;
            }
         
        }
        if (check ==true)
        {
            check = false;
        }
        else
        {
            break;
        }
    }
    if (s.size() == 0)
    {
        answer = 1;
    }
    return answer;
}

substr함수는 string을 index부터 잘라서 반환하는 함수이다.

string s="abcdefg"

s.substr(3) : 0부터 세기 시작해서 "3" 번째 인자부터 끝까지의 문자열을 반환한다.

즉 "defg"의 값을 얻을 수 있다.

해당 함수의 반환값을 다른 string 인자에 값을 담을 수 있다.

 

resize함수는 string을 n만큼의 크기로 만든다.

(원래 사이즈보다 resize한 함수가 작으면 남은 부분은 버리고, resize함수가 클 경우 빈 공간으로 채운다)

string s="abcdefg"

s.resize(3) : 크기를 3으로 만드는 것이기에 0~2번째 index만 남는다

즉 "abc"의 값을 얻을 수 있다.

 

위의 코드에서는 해당 함수의 반환 값을 다른 string인자에 담을 수 있는 substr함수를 먼저 사용 후, resize함수를 사용하였다. (resize함수를 사용 후 substr함수를 사용하려 하면, 이미 resize함수로 인해 string s의 값이 줄어들어 있기에 문제가 발생한다.)

 

Ex) string s= "baabba" 에서 "baaa"로 바꾸기 위해서는 index 3과 index 4를 지워야 한다.

string s1= s.substr(5) //5번 index이후 값을 반환

s.resize(3) //3번 index 이전 값을 반환(3번 index 포함 x)

s=s+s1; // 3번 index 이전 값과 5번 index 이후 값을 합침

 

최종 값: "baaa"

-> substr함수와 resize함수를 이용한다면 필요한 부분을 지우는 것이 가능하다.