14468 소가 길을 건너간 이유 2

원형의 울타리가 있고 길이 52개가 있다.

소는 총 26마리이고 이 소들이 반드시 한번 들어왔다가 반드시 한번 나간다.

또한 들어오고 나가는 길의 위치는 다르며 같은 위치의 길을 다른 소가 사용하는 경우는 없다.

이 때 생기는 경로상 소끼리 만날 수가 있는데 만나는 소의 쌍이 몇인지 구해야 한다.

원형으로, 그리고 시계방향으로 길을 사용한 소들의 정보를 준다.

해법

문제를 이해하기 힘들 수 있다. 아래의 발로그린 그림을 보자

이런 경우에 A,B소는 만난다고 한다. 

1. 스택을 사용한다.

2. i번째 소가 경로상에 처음으로 나타나면 push해준다.

3. i번째 소가 두번째로 나타났고 stack의 top에 i번째 소가 있으면 그냥 pop해준다.

4. i번째 소가 두번째로 나타났는데 stack의 top이 i번째 소가 아니라면

stack에서 i번째 소가 처음으로 나타났던 지점을 찾고 그 뒤에 몇마리의 소가 있는지 ans에 더해준다.

그다음 i번째 소의 정보를 지우고 stack을 땡겨준다.

#include <iostream>
using namespace std;
 
char s[53], st[53];
int c[26], ans;
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> s;
    for (int i = 0, cur = 0; i < 52; ++i) {
        if (c[s[i] - 'A'] == 0) {
            st[++cur] = s[i];
            c[s[i] - 'A'] = 1;
        }
        else if (st[cur] == s[i]) {
            cur--;
        }
        else {
            int j = 1;
            for (; j < cur && st[j] != s[i]; ++j);
            ans += cur - j;
            for (; j < cur; ++j) st[j] = st[j + 1];
            cur--;
        }
    }
    cout << ans;
    return 0;
}