소는 왜 길을 건넜을까 II

농부 존의 농장 구조는 꽤 독특한데, 소들이 낮 동안 풀을 뜯는 중앙 들판의 둘레를 커다란 원형 도로가 둘러싸고 있다. 매일 아침 소들은 들판으로 가는 길에 이 도로를 건너고, 매일 저녁에는 들판을 떠나 헛간으로 돌아가면서 모두 다시 도로를 건넌다.

알다시피 소는 습관의 동물이라, 매일 같은 방식으로 도로를 건넌다. 각 소는 들판에서 나오는 지점과 다른 지점에서 들판으로 들어가며, 이 모든 건너는 지점은 서로 다르다. 농부 존은 정확히 26마리의 소를 키우는데, 게으르게도 A부터 Z까지로 이름을 지었다(27번째 소가 생기면 어떻게 할지는 그도 잘 모른다...). 따라서 도로에는 정확히 52개의 건너는 지점이 있다. 농부 존은 원을 따라 시계 방향으로 훑으며 각 건너는 지점의 소 이름을 적는 방식으로 이 지점들을 간결하게 기록하고, 결국 알파벳의 각 글자가 정확히 두 번씩 나타나는 52글자의 문자열을 만든다. 그는 어떤 지점이 들어가는 지점이고 어떤 지점이 나오는 지점인지는 기록하지 않는다.

건너는 지점들의 지도를 보며, 농부 존은 여러 소 쌍이 낮 동안 몇 번이나 서로의 길을 가로지를지 궁금해한다. 소 \(a\)가 들어가는 지점에서 나오는 지점까지 가는 경로가 소 \(b\)의 들어가는 지점에서 나오는 지점까지의 경로와 반드시 교차해야 한다면, 소 쌍 \((a,b)\)를 "교차" 쌍이라고 부른다. 농부 존이 교차 쌍의 총수를 세는 것을 도와주자.

문제 출처: Brian Dean

문제 출처: Brian Dean

입력은 52개의 대문자로 이루어진 문자열이 있는 한 줄로 구성된다. 알파벳의 각 글자는 정확히 두 번씩 나타난다.

교차 쌍의 총수를 출력한다.

riseoj 작성

출처 올림피아드 > USACO > 2016-2017 > February > Bronze