1.문제
2. 접근/체크포인트
- 문자열의 크기가 홀수이면 무조건 하나가 남는다.
- 문자열 삭제 후 다시 이어 붙여야 함.
- 정확성과 효율성을 모두 생각해야 함.
3. 해결 방법
- 문자열의 크기만큼 문자열을 순회한다.
- 문자열을 순회하면서 스택에 문자열을 하나씩 넣고, 스택의 최상단 원소와 문자열이 같을 경우 스택에서 해당 문자열을 삭제한다.
- 문자열의 크기만큼 반복한 뒤 스택이 비어있으면, 모두 제거할 수 있는 경우로 1 반환, 아니면 0 반환.
4.전체코드
#include <iostream>
#include<string>
#include<stack>
using namespace std;
int solution(string s)
{
int answer = 0;
// 홀수는 무조건 하나 남음
if(s.empty() || s.size() % 2 != 0)
return answer;
stack<char> s_stk;
for(int i = 0; i < s.size() ; i++)
{
//스택이 비어있거나 스택의 최상단 원소와 같지 않으면 문자열 하나 push
if(s_stk.empty() || s_stk.top() != s[i])
s_stk.push(s[i]);
else
s_stk.pop();
}
if(s_stk.empty())
answer=1;
return answer;
}
5. 참고사항
👉 C++ 에서의 문자열 처리
1. char형 배열로 처리하는 방법.
ex) char num[3] = {'1','2','3'}
-> 크기가 고정적, 배열의 마지막에 항상 자동으로 Null 이 추가됨.2. String 클래스 사용하는 방법.
ex) string s = "123"
- #include <string> 헤더파일 포함해야함.
- 문자의 끝에 Null 이 포함되지 않는다.
- '+' 연산자로 문자열을 합칠 수 있음.
- 배열처럼 index 로 접근 가능
- 다양한 멤버함수 사용 가능
- str.front() : 맨 앞 문자 반환
- str.back() : 맨 뒤 문자 반환
- str.length(), str.size() : 문자열의 크기 반환
- int -> string 변환 : to_string(int);
- sting -> int 변환 : atoi(stirng);
- str.empty() : 문자열이 비어있으면 1 반환
- str.clear() : 문자열 전체 지우기
- str.erase(idx1, idx2) : idx1은 제거 시작할 index, idx2는 삭제할 문자 개수
6.다른 방법으로 풀어보기
생략
7. 후기
처음에는 아래 처럼 풀었는데 정확성은 100이지만 효율성이 0이라 다시 풀었다.
#include <iostream>
#include<string>
using namespace std;
int solution(string s)
{
int answer = 0; //다 제거 가능하면 1, 아니면 0 리턴
for(int i=0; i<s.size();){
if(s[i] == s[i+1]){
s.erase(i, 2); //해당 인덱스의 문자 지우기
i=0;
}else{
i++;
}
}
if(s.empty()){
return 1;
}else{
return 0;
}
return answer;
}이렇게 풀 경우 문자열을 제거한 뒤 다시 처음으로 돌아가서 순회하는 과정을 반복하게 되어서 시간복잡도가 커지기 때문에 효율성에서 1개의 케이스도 통과할 수 없었다. 스택을 사용하여 문자열의 크기만큼만 반복하는 방식으로 구현한다면 되돌아가는 과정이 생략되어 효율성 테스트에서도 통과할 수 있음! 처음에는 생각보다 간단한 문제라고 생각했는데 효율성을 생각하지 못했다.
Frontend-Devloper