백준 26122번: 가장 긴 막대 자석 (C++)

https://www.acmicpc.net/problem/26122

26122번: 가장 긴 막대 자석

---

Level: Silver V

Solved By: Stack, Implementation

 

확실히 다른 분들의 풀이를 보니 더 깔끔한 풀이들이 존재합니다. 스택을 사용할 필요도 없었던 거죠.

급한 마음을 다루는 연습이 필요하다고 생각합니다.

 

풀이는 이렇습니다.

 

문자열을 for문을 통해 탐색하면서 해당 문자에 대한 스택에 1을 담아줍니다. 그리고, 진행을 하면서 앞 전 문자와 다르다면 스택의 크기(= 부분 중복 문자열의 길이)를 v라는 벡터에 담아줍니다.

 

앞 전 문자와 다르다는 것을 확인하기 위해서 flag라는 bool 변수를 통해 확인해줍니다. 그리고, 다르다는 것이 인식된 이후에는 앞 전 문자가 'N'이었다면 'N'에 대한 스택을 모두 비워버립니다. 탐색이 끝난 후에도 두 스택 중 남아있는 것이 있으니 남아있는 스택의 크기를 v에 담아줍니다.

 

그리고, 끝에 0을 v에 담아줍니다. 0을 담아준 이유는 결과 식과 문제에서 제공된 2번째 케이스로 설명할 수 있습니다.

input: 
5
NNNNN
result:
0

다음 결과가 0인 이유는 N만으로는 막대 자석 문자열을 만들 수 없기 때문입니다. 여기까지 설명해도 0을 넣은 이유에 대해 설득이 되지 않습니다. 결과 식을 어떻게 선언했는지에 대해 설명하면 이해가 됩니다.

결과 식을 어떻게 선언했냐면

for(int i = 1; i < v.size(); i++){
    res = max(res, 2 * min(v[i - 1], v[i]));
}

각 문자로만 구성된 길이를 담은 배열 v에서 앞의 값과 현재 값을 비교하여 두 값 중 작은 것을 채택합니다. 왜냐하면 막대 자석 문자열을 만들 때는 N과 S의 개수가 같아야 하기 때문입니다. 그리고 총문자열의 길이는 N과 S 둘 다이기 때문에 * 2를 해주었고, 그중 최댓값을 고르게 했습니다.

 

0을 넣은 이유는 "NNNNN"이 주어진다면, v의 값들을 {5, 0}이 되어있습니다. N만 가지고서는 문자열을 만들 수 없다는 걸 알려줘야 하기 때문에 0을 넣어주었습니다.

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define ll long long
using namespace std;

int K;
string S;

int main(){
    FASTIO
    cin >> K >> S;
    stack<int> n, s;
    vector<int> v; 
    bool flag = false; // n = true, s = false;
    for(int i = 0; i < S.length(); i++){
        if(S[i] == 'N'){
            n.push(1);
            if(!flag){
                v.push_back(s.size());
                while(!s.empty()) s.pop();
            }
            flag = true;
        }
        else if(S[i] == 'S'){
            s.push(1);
            if(flag){
                v.push_back(n.size());
                while(!n.empty()) n.pop();
            }
            flag = false;
        }
    }
    
    if(flag){
        v.push_back(n.size());
    }
    else v.push_back(s.size());
    
    v.push_back(0);
    
    //for(auto i : v) cout << i << ' ';
    //cout << '\n';
    
    int res = 0;
    
    for(int i = 1; i < v.size(); i++){
        res = max(res, 2 * min(v[i - 1], v[i]));
    }
    
    cout << res;
    return 0;
}