[백준] 14468 소가 길을 건너간 이유2

문제 출처: https://www.acmicpc.net/problem/14468

14468번: 소가 길을 건너간 이유 2

 

1. 입력

: 첫 줄에 52글자의 문자열이 주어진다. 각 글자는 알파벳 대문자이며, 각 알파벳이 정확히 두 번씩 나타난다.

 

2. 출력

: 경로가 무조건 만나는 소가 몇 쌍인지 출력한다.

 

3. 풀이

: 위와 같이 A와 B의 한 점을 지나 들어오는 것과 나가는 것이 엇갈려 있을 때 서로 만난다는 것을 알 수 있다.

: 이런 경우는 A.시작점 < B.시작점 이고 B.시작점 < A.끝점이고 A.끝점 < B.끝점 임을 만족해야 한다.

: pos1에는 시작점을 pos2에는 끝점을 저장한다.

: 문자열을 순회하며 위 조건을 만족하면 카운트를 증가시킨다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder sb = new StringBuilder();
	static StringTokenizer st;
	public static void main(String[] args) throws IOException {
		String str = br.readLine();
		
		int pos1[] = new int[26];
		int pos2[] = new int[26];
		int cnt = 0;
		for(int i = 0; i < 52; i++) {
			int idx = str.charAt(i)-'A';
			if(pos1[idx] == 0) pos1[idx] = i+1;
			else pos2[idx] = i+1;
		}
		
		for(int i = 0; i < 26; i++) {
			for(int j = 0; j < 26; j++) {
				if(pos1[i] < pos1[j] && pos1[j] < pos2[i] && pos2[i] < pos2[j])cnt++;
			}
		}
		
		System.out.println(cnt);
	}
}