[백준 01622] 공통 순열 [Java]

문제

http://boj.ma/1622

1622번: 공통 순열

 

---

풀이

문제 요약

두 문자열의 가장 긴 공통 부분 수열의 순열이면서, 사전순으로 정렬된 문자열을 구하자.

아이디어

어떤 문자열이 두 문자열의 부분 수열의 순열이 되기 위해선, 공통으로 등장하는 문자이여야 하며, 두 문자열에서의 빈도가 가장 적은 갯수로 구성될 수 있다.

즉 두 문자열의 알파벳 빈도를 세고, 사전 순으로 만들어질 수 있는 가장 긴 공통 부분 수열의 순열을 생성하면 된다.

    private static int[] getCnt(String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) {
            ++cnt[c - 'a'];
        }
        return cnt;
    }

        while ((A = br.readLine()) != null && (B = br.readLine()) != null) {
            // Solve
            int[] cntA = getCnt(A);
            int[] cntB = getCnt(B);

            for (int i = 0; i < 26; ++i) {
                final int common = Math.min(cntA[i], cntB[i]);
                if (common > 0) {
                    sb.append(String.valueOf((char) ('a' + i)).repeat(common));
                }
            }

풀이 시간

5분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/01662.java

problem-solving/baekjoon-online-judge/easy/01662.java at main · rogi-rogi/problem-solving