이번에는 백준 3986번 좋은 단어 문제를 풀어보았습니다.
이 문제는 문자열이 A와 B로만 이루어져 있을 때, 같은 글자끼리 선이 교차하지 않게 모두 짝지을 수 있는지를 판단하는 문제입니다.
처음에는 직접 규칙을 찾는 방식으로 접근했고, 이후에는 stack 자료구조를 사용하면 훨씬 간단하게 풀 수 있다는 점을 정리하게 되었습니다.
문제 설명
각 단어는 A와 B로만 이루어져 있습니다.
이때 같은 글자끼리 짝을 지었을 때, 선이 교차하지 않으면서 모든 글자를 정확히 하나씩 짝지을 수 있다면 그 단어를 좋은 단어라고 합니다.
입력으로 여러 개의 단어가 주어질 때, 좋은 단어의 개수를 세어 출력하면 됩니다.
처음 접근한 방식 (V1)
처음에는 A와 B의 위치를 따로 저장한 뒤,
짝이 될 수 있는지 직접 확인하는 방식으로 접근했습니다.
생각한 조건
먼저 A 또는 B의 개수가 홀수라면,
어떤 식으로 짝을 지어도 반드시 하나가 남게 됩니다.
그래서
A의 개수가 홀수이거나B의 개수가 홀수이면
바로 좋은 단어가 아니라고 판단했습니다.
그 다음에는 조건을 만족하려면
연속된 한 쌍의 같은 문자 인덱스 차이가 홀수여야 한다고 보고,
이를 기준으로 검사를 진행했습니다.
V1 코드
#include<bits/stdc++.h>
using namespace std;
vector<int> A;
vector<int> B;
int count_A;
int count_B;
vector<string> input_str;
int result_cnt;
void clear_input() {
count_A = 0;
count_B = 0;
A.clear();
B.clear();
}
int check(const vector<int>& vec) {
for (int j = 0; j < vec.size() / 2; j++) {
int dist = vec[2 * j + 1] - vec[2 * j];
if (dist % 2 == 0) {
return 0;
}
}
return 1;
}
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string temp;
cin >> temp;
input_str.push_back(temp);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < input_str[i].size(); j++) {
if (input_str[i][j] == 'A') {
A.push_back(j);
count_A++;
}
if (input_str[i][j] == 'B') {
B.push_back(j);
count_B++;
}
}
if (count_A % 2 == 1 || count_B % 2 == 1) {
clear_input();
continue;
}
int flag_A = check(A);
int flag_B = check(B);
if (flag_A && flag_B)
result_cnt++;
clear_input();
}
cout << result_cnt << "\n";
}처음 풀이에서 봤던 포인트
1. 문자 개수가 홀수면 좋은 단어가 될 수 없음
A든 B든 하나라도 개수가 홀수라면 전부 짝지을 수 없습니다.
그래서 아래 조건으로 먼저 걸러냈습니다.
if (count_A % 2 == 1 || count_B % 2 == 1) {
clear_input();
continue;
}2. 같은 문자들의 위치 차이를 확인
각 문자의 위치를 배열에 저장한 뒤,
쌍으로 묶인 인덱스 차이가 조건을 만족하는지 확인했습니다.
int check(const vector<int>& vec) {
for (int j = 0; j < vec.size() / 2; j++) {
int dist = vec[2 * j + 1] - vec[2 * j];
if (dist % 2 == 0) {
return 0;
}
}
return 1;
}이 방식은 직접 규칙을 찾아가며 문제를 보려고 했다는 점에서는 의미가 있었지만,
구현도 다소 복잡하고 문제를 본질적으로 더 단순하게 풀 수 있는 방법이 있었습니다.
더 간단한 방식 (V2)
이 문제는 stack을 사용하면 훨씬 간단하게 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- 문자를 하나씩 보면서
- stack의 top과 현재 문자가 같다면 pop
- 다르면 push
이 과정을 끝까지 반복했을 때 stack이 비어 있으면 좋은 단어입니다.
즉, 붙어 있는 같은 문자끼리 계속 지워나가는 방식으로 생각할 수 있습니다.
V2 코드
#include <bits/stdc++.h>
using namespace std;
int n;
int cnt;
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
stack<char> stk;
string s;
cin >> s;
for (int j = 0; j < s.length(); j++) {
if (stk.size() != 0 && stk.top() == s[j]) {
stk.pop();
} else {
stk.push(s[j]);
}
}
if (stk.size() == 0) {
cnt++;
}
}
cout << cnt << "\n";
return 0;
}풀이 흐름
- 단어를 하나 입력받는다.
- 문자열을 앞에서부터 하나씩 확인한다.
- stack이 비어 있지 않고 top이 현재 문자와 같다면 pop한다.
- 그렇지 않으면 push한다.
- 문자열을 모두 확인한 뒤 stack이 비어 있으면 좋은 단어로 센다.
- 모든 단어에 대해 반복한 뒤 좋은 단어 개수를 출력한다.
구현 포인트
1. stack의 top과 현재 문자가 같으면 제거
이 문제는 같은 문자끼리 짝을 지을 수 있느냐를 보는 문제인데,
stack을 사용하면 가장 최근에 들어온 문자와 현재 문자를 바로 비교할 수 있습니다.
if (stk.size() != 0 && stk.top() == s[j]) {
stk.pop();
} else {
stk.push(s[j]);
}이 과정은 결국 짝지어진 문자들을 하나씩 제거해나가는 것과 같습니다.
2. 마지막에 stack이 비어 있으면 좋은 단어
모든 문자를 확인한 뒤 stack이 비어 있다는 것은
문자들이 전부 짝지어져서 제거되었다는 뜻입니다.
if (stk.size() == 0) {
cnt++;
}즉, 이 조건만으로 좋은 단어인지 판단할 수 있습니다.
