[프로그래머스/C++ 문제 풀이] Lv. 2 - 짝지어 제거하기

2024. 8. 24. 11:30·코딩테스트/프로그래머스 (Lv. 2)
728x90
반응형

문제 설명

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

예를 들어, 문자열 S = baabaa 라면

b aa baa → bb aa → aa →

의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다.

제한 사항

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

입출력 예

 

입출력 예 #1
위의 예시와 같습니다.


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


문제 풀이

이번 문제는 알파벳을 짝지어 같은 알파벳이 연속으로 나오는 경우 제거해야하는 문제입니다.

 

이번 문제와 같이 [짝짓기] 문제가 나온다면 우선적으로 Stack 자료구조를 생각해볼 필요가 있습니다.

 

Stack은 FILO(First In Last Out) 구조로, 알맞는 짝을 지어 제거하는 문제에서 마지막 들어온 요소와 다음 요소를 비교하기 매우 편한 자료구조이기에 저의 경우 스택을 사용해 문제를 바로 해결하게 되었습니다.

 

간단히 풀이 방법에 대해 설명하자면 다음과 같습니다.

1. 스택이 비어있지 않고, 스택의 최상단(마지막)요소가 들어올 문자열과 같은지 체크하기

2. 체크한 결과가 참이라면 스택의 최상단 요소를 제거하기

3. 체크한 결과가 거짓이라면 짝짓기에 실패한 것으로 생각하여 스택에 문자 추가하기

4. 모든 문자 순회 후 스택이 비어있다면 모두 제거에 성공한 것으로 생각하기

정답 코드

더보기

풀이 시간 : 3m 10s

#include <string>
#include <stack>

using namespace std;

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

    stack<char> stk;
    
    for (int i = 0; i < s.length(); i++)
    {
        // 스택의 크기 체크 및 스택의 최상단 요소가 s[i]와 동일하다면?
        if (!stk.empty() && stk.top() == s[i])
        {
            // 같은 알파벳이 연속으로 들어온 것으로 생각하고 스택의 최상단 요소를 제거합니다.
            stk.pop();
        }
        // 스택의 최상단 요소와 같지 않거나 스택의 크기가 0인 경우
        else
        {
            // 스택에 s[i]번째 알파벳을 추가합니다.
            stk.push(s[i]);
        }
    }
    
    // 위 반복문을 통해 모든 문자열을 순회한다면 폭파가 되는 문자는 제거될 것입니다.
    // * 즉, 스택이 비어있으면 모든 문자가 제거된 것으로 생각할 수 있습니다.
    answer = stk.empty() ? 1 : 0;

    return answer;
}
728x90
반응형
저작자표시 비영리 변경금지 (새창열림)

'코딩테스트 > 프로그래머스 (Lv. 2)' 카테고리의 다른 글

[프로그래머스/C++ 문제 풀이] Lv. 2 - 점프와 순간 이동  (0) 2024.08.26
[프로그래머스/C++ 문제 풀이] Lv. 2 - 카펫  (0) 2024.08.25
[프로그래머스/C++ 문제 풀이] Lv. 2 - 피보나치 수  (0) 2024.08.23
[프로그래머스/C++ 문제 풀이] Lv. 2 - 다음 큰 숫자  (0) 2024.08.23
[프로그래머스/C++ 문제 풀이] Lv. 2 - 숫자의 표현  (0) 2024.08.23
'코딩테스트/프로그래머스 (Lv. 2)' 카테고리의 다른 글
  • [프로그래머스/C++ 문제 풀이] Lv. 2 - 점프와 순간 이동
  • [프로그래머스/C++ 문제 풀이] Lv. 2 - 카펫
  • [프로그래머스/C++ 문제 풀이] Lv. 2 - 피보나치 수
  • [프로그래머스/C++ 문제 풀이] Lv. 2 - 다음 큰 숫자
리태s
리태s
게임 클라이언트 프로그래머 직무를 준비하며 공부한 내용을 정리한 블로그입니다.
    반응형
    250x250
  • 리태s
    LeeTaes 공부노트
    리태s
  • 전체
    오늘
    어제
    • Home (165)
      • 프로젝트 (20)
        • Isaac 3D (5)
        • TimelessAdventure (13)
        • FruitsPuzzle (2)
      • Game Programming (25)
        • C# (8)
        • Unity Engine (6)
        • Unreal Engine (8)
        • UE_Multiplayer (3)
      • 코딩테스트 (111)
        • 프로그래머스 (Lv. 0) (27)
        • 프로그래머스 (Lv. 1) (31)
        • 프로그래머스 (Lv. 2) (21)
        • 백준 (Study) (29)
        • 알고리즘 (3)
      • CS지식 (7)
        • 운영체제 (7)
      • 일상 (2)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    fsoftobjectpath
    issac3d
    2018 kakao
    코딩테스트
    c#
    2022 kakao
    delegate
    백준
    unrealengine
    프로세스
    후기
    구현
    프로그래머스
    project t.a develop
    Summer/Winter Coding
    sesac
    프로젝트
    Algorithm
    C++
    tsoftobjectptr
    ai controller
    timelessadventure
    fruitspuzzle
    청년취업사관학교
    CS지식
    pcce 기출문제
    Unreal Engine
    dataasset
    2019 kakao
    unity
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
리태s
[프로그래머스/C++ 문제 풀이] Lv. 2 - 짝지어 제거하기
상단으로

티스토리툴바