[AtCoder - AGC034 B] ABC

난이도: 1101

 

태그

• Stack

 

풀이

1. 연산을 분석해보자.

문제에서 주어진 연산은 "ABC"를 "BCA"로 바꾸는 연산입니다.

이를 다르게 해석하자면, "A" 다음에 "BC"가 온다면 이 "A"를 "BC" 뒤로 미는 연산이라고 볼 수 있겠죠.

 

즉, "A"가 "BC"를 건너뛰어서 이동한다는 것입니다.

 

이 연산을 최대한 많이 하려면, "A"가 최대한 많은 "BC"를 건너뛰어야겠죠.

 

2. 이를 토대로, 간단히 생각해볼 수 있는 풀이는?

글자를 하나씩 읽으면서, 'A'가 나올 때마다 이 뒤에 연속적으로 있는 BC의 개수를 세주면 되죠.

다만, 주의할 점이 AAABCBC라든가, AABCABC라든가, AABCBAC라든가 다양합니다.

// A 뒤에 A가 나와도 이동 가능, 심지어 BC 사이에 껴있어도 가능, 그런데 B랑 C 사이면 이동을 못해서 불가

 

주의할 점이 많은 건 둘째치고, 최악의 경우에 이 방법은 너무 느리죠.

 

3. [2]를 좀 더 빠르게 해볼 수 없을까?

A가 신경써야 할 글자는 이 뒤에 있는 글자들 뿐입니다.

그러니, 문자열을 뒤에서부터 읽어봅시다.

 

이와 동시에, 지금까지 읽은 문자들을 효율적으로 관리하는 스택 하나를 만들어봅시다.

이 스택에는 글자 (A B C)가 들어가거나, 수 (1 2 3 ...)가 들어갑니다.

• 스택에 있는 값이 글자라면, 이는 그냥 그 글자를 의미합니다.
• 스택에 있는 값이 수라면, 이는 연속된 BC의 개수를 의미합니다.

 

이제, 글자를 하나씩 읽어봅시다.

• 특별한 경우가 없으면, 그냥 스택에 그 글자를 넣으면 됩니다.
• 하지만, 이 결과로 BC가 만들어진다면, BC를 pop하고 대신 1을 넣어주면 됩니다.
• 그런데, 만약 수가 연속으로 2개가 나온다면, 이 두 수를 pop하고 이의 합을 넣어줘야 하죠.

 

물론 여기서 끝나는 건 아닙니다. 답도 구해야 하고, A의 이동도 생각해야 하니, 아래 경우를 추가해야 하죠.

• A와 수가 연속으로 나온다면, 답에 그 수만큼 더하고, A를 넣지 않습니다.
  // 사실 엄밀히는 그 수 뒤에 넣어야 하겠지만, 어차피 맨 앞에 있는 거만 볼테니 안 넣어도 답은 동일합니다.
• 아닌 경우, 그냥 글자 A를 넣습니다.
  // 이는 BAC 같은 경우를 처리하기 위함입니다.

 

3. 코드

void Main(){
    string s; cin >> s; int sl = s.size();
    stack<int> stk; ll ans = 0;
    for (int i = sl-1; i >= 0; i--){
        char ch = s[i]; int val = -(ch-64);
        if (stk.empty()){ stk.push(val); }
        else{
            if (val == -1 && stk.top() > 0){ ans += stk.top(); }
            else if (val == -2 && stk.top() == -3){
                stk.pop();
                if (!stk.empty() && stk.top() > 0){ stk.top() += 1; }
                else{ stk.push(1); }
            }
            else{ stk.push(val); }
        }
    }
    cout << ans;
}