[백준 1148] 단어 만들기 - JAVA

BOJ Link

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

 

 

 

 

풀이 과정

문자열 + 구현 문제
구현 자체도 까다롭고, 고려할게 많다.

1 시간 복잡도를 제대로 구할 수가 없다.
문제에서 단어의 개수는 20만 이하이나, 정작 퍼즐판은 몇 개를 주는지 명시하지 않았다.

퍼즐판의 크기를 3*3로 준데서 적당히 작겠거니 생각하고 완전탐색해서 풀었다.

2. puzzle에서 α 라는 문자를 중간에 놓았다 가정하면, puzzle로 word를 만들 수 있는 조건은 다음과 같다.
2-1. word에는 α 가 포함되어 있어야 한다.
2-2. word에 있는 모든 알파벳(A-Z)의 개수가 puzzle의 알파벳(A-Z) 개수보다 작거나 같아야 한다.

3. byte를 쓰지 않으면 왠만한 최적화로는 메모리 초과가 난다.
map을 이용한 풀이 / int[20만][9] 배열 풀이 => 둘 다 메모리 초과를 받았다. 이를 파악하기 매우 어렵다.

byte를 쓸 수 있는 이유는, 각 알파벳이 가질 수 있는 최댓값이 9이며, 이는 byte 범위 -128~127 이내이기 때문이다.
byte[20만]['Z' - 'A' + 1] 크기의 배열로 단어마다 알파벳을 몇 개 씩 포함하는 지 셀 수 있다.

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

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

        StringBuilder sb = new StringBuilder();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s;

        int ALPA_LEN = 'Z' - 'A' + 1;
        byte[][] dic = new byte[200000][ALPA_LEN];
        int idx = 0;

        // 단어 별로 알파벳이 나온 횟수 저장
        while (!(s = br.readLine()).equals("-")) {
            for (int i = 0; i < s.length(); i++) {
                dic[idx][s.charAt(i) - 'A']++;
            }
            idx++;
        }

        int COL_LEN = idx;

        while (!(s = br.readLine()).equals("#")) {

            int min = Integer.MAX_VALUE;
            int max = 0;
            Set<Character> minSet = new HashSet<>();
            Set<Character> maxSet = new HashSet<>();

            byte[] puzzle = new byte[ALPA_LEN];
            for (int i = 0; i < s.length(); i++) {
                puzzle[s.charAt(i) - 'A']++;
            }

            // 퍼즐판 중앙 문자를 임의로 지정하며 탐색
            for (int i = 0; i < ALPA_LEN; i++) {

                // 중앙 문자가 퍼즐 판에 없는 경우면 해가 아님
                if (puzzle[i] == 0) continue;
                int cnt = 0;

                // 단어 별로 비교 했을 때
                for (int col = 0; col < COL_LEN; col++) {

                    // 중앙 문자가 단어에 없다면 해가 아님
                    if (dic[col][i] == 0) continue;

                    // 단어의 특정 알파벳 개수보다 퍼즐판의 개수가 적다면 해가 아님
                    boolean isPossible = true;
                    for (int j = 0; j < ALPA_LEN; j++) {
                        if (dic[col][j] > puzzle[j]) {
                            isPossible = false;
                            break;
                        }
                    }

                    if (isPossible) cnt++;
                }

                if (cnt < min) {
                    min = cnt;
                    minSet.clear();
                    minSet.add((char) ('A' + i));
                } else if (cnt == min) {
                    minSet.add((char) ('A' + i));
                }

                if (cnt > max) {
                    max = cnt;
                    maxSet.clear();
                    maxSet.add((char) ('A' + i));
                } else if (cnt == max) {
                    maxSet.add((char) ('A' + i));
                }
            }

            // 중복 제거 및 정렬
            minSet.stream().sorted().forEach(sb::append);
            sb.append(" ").append(min).append(" ");
            maxSet.stream().sorted().forEach(sb::append);
            sb.append(" ").append(max).append("\n");
        }

        System.out.println(sb);
    }
}