백준 11468 자바 - Concatenation (BOJ 11468 JAVA)

문제 : boj11468

 

 

1. 우선 모든 경우의 수를 생각해보자.

  예제 입력 1의 cat과 dog를 봐보자. 나올 수 있는 모든 경우는 다음과 같다.

(cg, cog, cdog, cag, caog, cadog, catg, catog, catdog의 9가지)

 

  이와같이 A와 B가 입력으로 들어온다면, 모든 경우의 수는 [A의 문자 수 x B의 문자 수] 임을 알 수 있다.

 

 

 

2. 그럼 언제 중복된 경우가 발생할까?

  bbb와 bzz를 확인해보자. 이와 같이 동일한 문자가 존재하는 경우 중복값이 발생한다. 다만 이 때, A 단어의 맨 앞 문자는 무조건 들어가야 하고(non-empty prefix), B 문자의 맨 뒤 글자도 무조건 들어가야 하므로(non-empty suffix) A 문자의 맨 첫문자와, B 문자의 맨 뒤 문자는 제외하고 생각한다.

 

  즉, A='abb', B='cca'의 경우 A와 B에 'a'라는 중복 문자가 있다 하더라도 모든 경우의 수인 9가 답이다.

 

  마찬가지로 예제 입력 2의 tree와 heap의 경우 A문자의 'e' 2개와, B문자의 'e' 1개가 중복이다. 중복된 경우는 어떻게 모든 경우에서 빼낼 수 있을까? [A에서 나온 횟수 x B에서 나온 횟수]가 될 것이다. 따라서 위에서 예시로 든 bbb, bzz는 [모든 경우 3x3 - 중복 경우 2x1 = 7] 이 된다. tree. heap의 경우 [모든 경우 4x4 - 중복 경우 2x1 = 14]가 된다.

 

 

 

3. 전체 로직

  '2'에서는 중복된 문자가 하나였다. 근데 당연하게도 a~z 까지 모든 문자는 중복될 수 있다. 그럼 어떻게 해야할까? 전체 로직을 하나로 표현하자면 다음과 같다.

 

[모든 경우 - (A에서 첫문자 빼고 'a'가 나온 횟수 x B에서 끝문자 빼고 'a'가 나온 횟수) - (A에서 첫문자 빼고 'b'가 나온 횟수 x B에서 끝문자 빼고 'b'가 나온 횟수) - ...... - (A에서 첫문자 빼고 'z'가 나온 횟수 x B에서 끝문자 빼고 어쩌구 'z'가 나온 횟수)]

 

 

알고보면 쉽지만 생각하긴 다소 어려웠던 재밌는 아이디어 문제였다.

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String a = br.readLine();
        String b = br.readLine();

        int[][] cnt = new int['z'-'a'+1][2];
        for (int i = 1; i < a.length(); i++) cnt[a.charAt(i)-'a'][0]++;
        for (int i = 0; i < b.length()-1; i++) cnt[b.charAt(i)-'a'][1]++;

        long answer = 1l*a.length()*b.length();
        for (int i = 0; i < cnt.length; i++) answer-=1l*cnt[i][0]*cnt[i][1];
        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}