[백준] 1622번: 공통 순열

문제

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

 

풀이

처음에 문제를 제대로 안 읽고 안일하게 생각하고 접근했다가 틀렸다.. 

 

a문자열 내에도 존재하고 b문자열 내에도 존재하는 부분 수열을 구해야 하는데, a문자열을 반복문으로 돌면서 알파벳이 문자열 b에도 존재하기만 하면 부분 순열로 처리한 후 Set에 넣어버렸다.. abcc, deccc와 같은 경우 부분 수열이 cc인데 위의 방법으로 코드를 짤 경우 부분 수열이 c로 처리되기에 당연히 틀릴 수 밖에 없다.

// 틀린 답안

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input;
        while((input = br.readLine()) != null) {
            
            char[] a = input.toCharArray();
            String b = br.readLine();
            Set<Character> set = new TreeSet<>();
            
            for(char chr : a) {
                if(b.contains(String.valueOf(chr))) {
                    set.add(chr);
                }
            }

            StringBuilder sb = new StringBuilder();
            
            for(char chr : set) {
                sb.append(chr);
            }
            
            System.out.println(sb);
        }
        br.close();
    }
}

 

문제를 다시 읽고 코드를 고쳤다. 각 문자열의 알파벳 빈도 수 저장을 위한 Map, 정렬을 위해 TreeMap을 사용하였다! A 해시와 B 해시에 동시에 존재하는 알파벳일 경우 더 작은 값을 뽑아서 두 문자열에 부합하는 부분수열을 완성하였다.

import java.util.*;
import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input;
        // input이 없을 때까지 계속 받기
        while((input = br.readLine()) != null) {
            
            char[] a = input.toCharArray();
            char[] b = br.readLine().toCharArray();
            Map<Character, Integer> hashA = new TreeMap<>();
            Map<Character, Integer> hashB = new TreeMap<>();
            
            for(char chr : a) {
                hashA.put(chr, hashA.getOrDefault(chr, 0) + 1);
            }
            for(char chr : b) {
                hashB.put(chr, hashB.getOrDefault(chr, 0) + 1);
            }

            StringBuilder sb = new StringBuilder();
            
            for(char key : hashA.keySet()) {
                if(hashB.keySet().contains(key)) {
                    int cnt = Math.min(hashA.get(key), hashB.get(key));

                    for(int i = 0; i < cnt; i++) {
                        sb.append(key);
                    }
                }
            }
            System.out.println(sb);
        }
        br.close();
    }
}