[백준 1622] 공통 순열 - JAVA

BOJ Link

https://www.acmicpc.net/problem/1622

 

 

 

풀이 과정

1.  a의 부분 수열의 순열이자 b의 부분 수열의 순열이 되는 가장 긴 문자열 x의 사전 순으로 가장 앞에 오는 것을 출력?

 

한마디로 a와 b가 공통으로 가진 원소 집합을 찾아 정렬하면 된다.

 

map으로 a와 b의 <원소, 개수>를 저장한 뒤 공통 원소만 뽑는다.

둘 다 어떤 원소를 가지고 있다면, 둘 중 더 적은 개수가 공통 원소가 된다.

 

2. 입력에는 빈 문자열이 올 수 있으며, EOF 처리를 해야함

 

전자의 조건은 놀랍게도 명시되어 있지 않다. 유추해서 처리해야 한다.

if ("".equals(A) || "".equals(B)) {
    System.out.println();
    continue;
}

while ((A = br.readLine()) != null) {

 

 

제출 코드

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

class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String A = "";
        String B = "";

        while ((A = br.readLine()) != null) {
            B = br.readLine();

            if ("".equals(A) || "".equals(B)) {
                System.out.println();
                continue;
            }

            Map<Character, Integer> aMap = new HashMap<>();
            Map<Character, Integer> bMap = new HashMap<>();

            Arrays.stream(A.split("")).forEach(s -> aMap.merge(s.charAt(0), 1, (ov, nv) -> ov + 1));
            Arrays.stream(B.split("")).forEach(s -> bMap.merge(s.charAt(0), 1, (ov, nv) -> ov + 1));

            List<Character> output = new ArrayList<>();

            for (Map.Entry<Character, Integer> aEntry : aMap.entrySet()) {

                char aKey = aEntry.getKey();

                if (bMap.containsKey(aKey)) {
                    int total = Math.min(aEntry.getValue(), bMap.get(aKey));

                    while (total > 0) {
                        output.add(aKey);
                        total--;
                    }
                }
            }

            output.stream().sorted().forEach(System.out::print);
            System.out.println();
        }
    }
}