문제 이해 단계
짝수 팰린드롬이라고
"수열의 길이가 짝수이고 뒤집은 후의 수열과 뒤집기 전의 수열이 동일" 하다고 정의한다.
여기서 동일하다는 것은 순서까지 동일하다는 것이다.
위에 예제를 보면 좀 더 이해하기가 편할 것이다.
입력으로 수열의 길이 N이 주어지고,
짝수개의 원소가 나열될 때, 모든 수열을 나눴을 때 짝수 팰린드롬을 만족하는지 확인한다.
만족한다면 최대 몇 개로 나눌 수 있는지 확인하는 문제
문제 접근 단계
이 문제를 풀기 위해서는 짝수 팰린드롬의 특징부터 알아내야 할 것 같다.
예제 1번에서 나온 답을 보면
(1, 1), (5, 6, 7, 7, 6, 5), (5, 5)인데,
여기서 알 수 있는 특징은 짝수 팰린드롬이 성립하려면,
각 집합을 동일한 길이로 2 등분하였을 때 대칭돼야 한다는 것이다.
이게 무슨 소리냐면 (5,6,7,7,6,5)를
동일한 길이로 2 등분하면 (5,6,7) (7,6,5)이다.
만약 가운데에 (5,6,7) | (7,6,5)
이런 기점이 있다고 할 때, 해당 기점을 기준으로 두 집합은 서로 대칭이다.
다른 말로 하면 두 집합은 데칼코마니라는 소리이다.
대칭성 구현
대칭성이라고 하니 서로 짝을 짓는 게 생각났다.
괄호 문제처럼 '('와 ')'를 서로 탐색하는 것처럼.
단지 이건 그 짝을 확인하는 과정이 더 디테일해졌을 뿐이다.
그래서 괄호 문제처럼 스택을 사용하기로 하였다.
알고리즘은 아래와 같다. 탐색 순서는 순차적으로 진행한다.
전체적인 과정
1. 스택이 비어있다면 현재 원소를 넣고 다음 원소로 넘어간다.
2. 스택이 비어있지 않다면, 대칭성을 검사하는 알고리즘을 실행한다.
3-1.
대칭성을 검사하는 알고리즘이 true라면, 스택을 비우고 정답개수 + 1을 한다.
그리고 다음 원소는 (현재 원소 + 기존 스택의 개수)로 설정한다.
3-2.
대칭성을 검사하는 알고리즘이 false라면
스택에 현재 원소를 넣고 다음 원소로 넘어간다.
대칭성 검사 알고리즘
1. 스택을 복사해서 또 다른 스택을 하나 만든다.
2. 복사한 스택의 top과 현재 원소를 비교한다.
3-1. 같다면 복사한 스택에서 pop 하고, 다음 원소와 또 비교한다.
3-2. 다르다면 false를 반환한다.
4. 스택이 빌 때까지 false를 반환하지 않으면, true를 반환한다.
설명만으로는 무슨 말일지 이해가 잘 안 갈지도 모르기 때문에
예제 1번으로 시뮬레이션을 돌리면서 설명하겠다.
왼쪽같이 원소의 배열과 스택이 있다고 생각하고 시작하겠다.
일단은 스택이 비어있기 때문에, 1번 원소는 그냥 스택에 들어간다.
2번 원소는 메인 스택 안에 원소가 들어있기 때문에
이제부터 대칭성을 검사하는 알고리즘을 실행한다.
이는 오른쪽에 있는 복사한 스택에서 실행한다.
여기서 2번 원소를 넣고 검사하는데, 1 == 1 이기 때문에 사라진다.
그렇게 되면 복사한 스택이 비어버리게 되므로, 대칭성이 되는 조건이 만족된다.
그래서 메인 스택을 비워주고 정답 개수를 하나 올려준다.
그리고 (현재원소 인덱스 + 메인 스택 사이즈) = 2
즉, 3번 원소로 이동하여 검사를 진행한다.
마찬가지로 3번 원소를 넣을 때는
메인 스택이 비어있기 때문에 그냥 넣어준다.
4번 원소도 똑같이 대칭성 검사를 해주는데,
이번에는 두 수가 다르기 때문에, false를 반환하고 메인 스택에 6을 넣는다.
5번 원소(7)도 4번 원소처럼 똑같이 되기 때문에
그림은 생략하고 바로 6번 원소로 넘어가겠다.
대칭성 검사를 해주는데,
이번에는 스택에 3개가 들어있었기 때문에 한 번이 아닌 3번을 검사해줘야 한다.
검사를 해줄 때 6번 원소부터 시작하여 +1씩 올려주면서 검사해줘야 한다.
그림에서 확인할 수 있듯 스택에 top이 원소들과 일치하며
팰린드롬을 이루는 것을 확인할 수 있다.
스택이 모두 비워졌으므로, 이를 메인 스택에 반영하고 ans+1을 한다.
그리고 메인 스택의 사이즈만큼 원소 인덱스를 뒤로 미뤄서 검사 작업을 계속한다.
최종적으로 끝까지 탐색을 다 마치면 답이 3이 될 것이다.
이제 이 로직을 코드로 구현만 하면 된다.
문제 구현 단계
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
vector<int> list; // 원소 배열
// 대칭성 검사 함수
bool isSuccess(stack<int> s, int idx){
while(!s.empty()){
// 일치하지 않을 때
if(s.top() != list[idx]) return false;
s.pop();
idx +=1;
}
return true;
}
int main(){
int N;
scanf("%d",&N);
stack<int> s; // 메인 스택
for(int i = 0; i < N; i++) {
int val;
scanf("%d",&val);
list.push_back(val);
}
s.push(list[0]);
int ans = 0;
for(int i = 1; i < list.size(); i++){
// 비었을 때 그냥 넣음
if(s.empty()) s.push(list[i]);
else{
// 대칭일 시
if(isSuccess(s,i)){
ans++;
i = i + s.size()-1; // 다음 탐색으로 이동
while(!s.empty()) s.pop();
}
else s.push(list[i]);
}
}
// 스택이 비지 않았다는 것은 실패했다는 뜻
if(s.empty()) printf("%d",ans);
else printf("-1");
}코드 자체는 그렇게 길지도 않고
어렵지도 않기 때문에 그냥 한 번에 넣었다.
대칭성 검사를 하는 함수는 isSuccess이다.
대칭이면 true, 아니면 false를 반환한다.
인자로 메인 스택을 복사해서 만든 스택 s와
원소 배열 인덱스 번호를 받는다.
이 함수는 간단한데, 그냥 이 복사한 함수가 빌 때까지
일치하지 않는 게 나오지 않으면 true, 나오면 false이다.
main문에 있는 것은 위에 설명했던 것 그대로,
순차적으로 탐색해서 비어있으면 그냥 넣고
isSuccess가 성공했으면 스택을 비워주고 정답+1,
그리고 다음 탐색을 위해 인덱스를 이동해 준다.
근데 여기서 왜 (자기 원소 인덱스 + 스택 크기)라고 했는데 1을 빼줄까?
왜냐하면 반복문을 돌리기 때문에
이 함수가 반복될 때마다 1을 더해주기 때문이다.
그렇게 해서 최종적으로 출력된 메인 스택이 비어있지 않으면
팰린드롬에 실패한 것이고, 비어있으면 성공한 것이므로 적절하게 출력해 준다.
시행착오
옛날에 풀다가 못 푼 문제, 1년 전에 자바로 풀다가 포기했었던 거 같은데
아무래도 실력이 좋아지긴 한 것 같다.
근데 이거 분류 보니까
DP 아니면 그리디로 풀었던데, 난 왜 스택이 떠올랐지?
DP로 풀면 더 어려울 것 같은데..
그리고 그리디로도 풀 수 있다는데 이 방법은 잘 모르겠네
일단 난 스택으로 풀기도 했고
뭔가 이 방법이 도움 될 사람도 있지 않을까 싶어서 블로그에 올린다.
많이 도움 됐으면 좋겠다.
스택으로 풀면 골드 3까지는 안 가는 거 같기도 하다.