[코드트리] 알파벳 X 2 - 자바(Java)

문제

https://www.codetree.ai/training-field/search/problems/alphabet-X-2?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

 

대문자 알파벳 A부터 Z까지 각각 2번씩 나오는 52개의 문자로 이루어진 문자열이 하나 주어졌을 때, 1차원 직선상에 각 알파벳을 균등한 거리를 두고 놓았다고 생각하고 각각의 동일한 알파벳끼리 연결되도록 26개의 선분을 그었을 때, 서로 다른 알파벳 선분끼리 몇 번 어중간하게 겹치는지를 구하는 프로그램을 작성해 보세요. 두 선분이 서로 포함관계에 있는 경우는 완벽하게 겹치는 경우이며, 두 선분이 겹치기는 하나 서로 포함관계에 있지 않은 경우를 어중간하게 겹치는 경우로 봅니다.

 

입력 예시

ABCCABDDEEFFGGHHIIJJKKLLMMNNOOPPQQRRSSTTUUVVWWXXYYZZ

 

출력 예시

1

 

 

코드

첫 번째 줄에 길이가 52인 문자열이 주어집니다.

• 모든 문자는 알파벳 대문자로 이루어져 있습니다.
• 각 문자는 2번씩 주어집니다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String alphabets = br.readLine();
        br.close();

        boolean[] checkList = new boolean[26]; // 각 알파벳의 체크 여부
        int result = 0; // 어중간하게 겹치는 횟수

        // 입력 문자열 순회
        for (int i = 0; i < alphabets.length(); i++) {
            char current = alphabets.charAt(i); // 현재 문자
            if (checkList[current - 'A']) { // 현재 문자가 체크된 상태면 continue
                continue;
            }
            checkList[current - 'A'] = true; // 현재 문자 체크
            int[] count = new int[26]; // 어중간하게 겹치는 경우를 체크하기 위한 배열 생성
            
            // 현재 문자의 사이에 있는 부분 문자열
            String substring = alphabets.substring(i + 1, alphabets.lastIndexOf(current));
            
            // 부분 문자열의 알파벳 등장 횟수 카운트
            for (int j = 0; j < substring.length(); j++) {
                count[substring.charAt(j) - 'A']++;
            }
            
            // count 배열 순회
            for (int j = 0; j < count.length; j++) {
                if (count[j] == 1) { // 부분 문자열에 1번만 등장한 알파벳이 있는 경우
                    result++; // result 증가
                }
            }
        }

        // 어중간하게 겹치는 경우의 쌍 수 = result / 2
        bw.write(String.valueOf(result / 2));
        bw.flush();
        bw.close();
    }
}