lv2) 짝지어 제거하기 c++로 lv5 정도 될 듯 하다.

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

프로그래머스

 

스택으로 하면 풀이가 쉬운데, 효율성 tc1, 2가 시간초과가 났다.

 

파이썬의 경우 스택으로 풀이 시 통과이나, c++에서 프로그래머스 업데이트 시점 이후로 문제가 생겼다고 한다.

 

참고자료

https://blog.naver.com/coldman1224/224331901845

[프로그래머스] 짝지어 제거하기 최신 답안 (C++)

 

 

 

 

 

정답(With Claude)

#include <string>
using namespace std;

int solution(string s)
{
    // 문자열 길이 저장
    // size()를 반복 호출하지 않도록 한 번만 저장하여 불필요한 연산 제거
    size_t len = s.size();

    // 짝지어 제거는 항상 2개씩 제거되므로
    // 문자열 길이가 홀수이면 절대 모두 제거할 수 없음
    // 비트 연산(& 1)은 % 2 == 1과 같은 의미이며 조금 더 가벼운 연산
    if (len & 1)
        return 0;


    // 가상의 스택 크기
    // 실제 stack 자료구조를 사용하지 않고 문자열 앞부분을 스택처럼 활용
    // top은 현재 스택에 저장된 문자 개수
    size_t top = 0;


    // 최적화 핵심:
    // 별도의 stack/vector를 생성하지 않고 입력 문자열 자체를 스택 공간으로 재사용
    // 추가 메모리 할당이 없어 O(1) 공간 사용
    char* write = &s[0];


    // 문자열을 처음부터 끝까지 한 번만 순회
    // 시간복잡도 O(N)
    for (size_t i = 0; i < len; i++)
    {
        // 현재 확인할 문자
        char c = s[i];


        // 현재 가상 스택의 마지막 문자와 현재 문자가 같으면
        // 두 문자가 한 쌍이므로 제거
        //
        // 실제 stack을 사용하면 pop()이지만,
        // 여기서는 top 위치만 감소시켜 제거 효과를 구현
        if (top > 0 && write[top - 1] == c)
        {
            --top;
        }
        else
        {
            // 같은 문자가 아니면 스택에 추가
            //
            // 실제 stack의 push() 대신
            // 문자열 앞부분에 현재 문자를 덮어쓰기하여 저장
            // 동적 할당 및 함수 호출 오버헤드 제거
            write[top++] = c;
        }
    }


    // 모든 문자가 제거되었다면 top은 0
    // 남은 문자가 있으면 top > 0
    return top == 0;
}

 

 

내풀이1) 오답

시간초과인데  substr 자체가 O(N)이다 보니 While문과 함께 사용 시 10억번(10초)이 넘기에 사용 불가다.

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

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

    //투포인터
    int stPt = 0;
    int endPt = 1;

    int cnt = 0;
    while(s.size()!=0){
        if(cnt == s.size() || ((s[0] != s[1]) && s.size() == 2)) {
            return 0;
        }
        if(s.size() %2 == 1)return 0;
        cnt++;
        
        if(s[stPt] ==s[endPt]){
            //구분 영역이 아니니
            if(stPt == 0){
                if(s.size()==2){{
                    return 1;
                }}
                s = s.substr(endPt+1,s.size()); // loop 문(O[N]) + s.substr(O[N]) 최악 n^2라서 시간초과나나..
                
            }
            else{ // 구분 영역
                s = s.substr(0, stPt) + s.substr(endPt+1,s.size());
                
            }
            stPt=0;
            endPt = 1;
            continue;
        }
        stPt++;
        endPt++;
        if(stPt>=s.size())return 0;
    }
    return 0;
}

 

내풀이2) 오답, 

 

1. 스택이 있으면 계속 진행

2. 스택이 비면 억지로 다음 문자 넣음

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

int solution(string s)
{
    if(s.size()%2==1)return 0; // 홀수일경우
    stack<char>st;
    int idx = 0;
    st.push(s[idx]);
    
    while(st.size()!=0){ 
        idx++;
        if(idx >= s.size())return 0;
        if(st.top() == s[idx]){
            st.pop();
            if(st.empty() && idx + 1 < s.size()){
                st.push(s[++idx]);
            }
        }
        else{
            st.push(s[idx]);
        }
    }
    return 1;
}

 

내풀이3) 효율성 tc 1, 2 오답 (프로그래머스 자체 문제)

(정석 풀이법)

1. 문자열 끝까지 진행

2. 현재 문자와 stack top 비교

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

#1
int solution(string s)
{
    stack<char> st;
    int idx = 0;

    while(idx < s.size())
    {
        if(!st.empty() && st.top() == s[idx])
        {
            st.pop();
        }
        else
        {
            st.push(s[idx]);
        }

        idx++;
    }

    return st.empty() ? 1 : 0;
}



#2
int solution(string s)
{
    stack<char> st;

    for(char c : s)
    {
        if(!st.empty() && st.top() == c)
            st.pop();
        else
            st.push(c);
    }

    return st.empty() ? 1 : 0;
}

 

내풀이4) 효율성 추구, stack 사용않하고

#include <string>
using namespace std;

int solution(string s)
{
    int top = 0;

    for (char c : s)
    {
        if (top > 0 && s[top - 1] == c)
        {
            --top;
        }
        else
        {
            s[top++] = c;
        }
    }

    return top == 0 ? 1 : 0;
}