[자바] 백준 1148 - 단어 만들기 (java)

 문제 : boj1148

---

 

필요 알고리즘 개념

• 문자열
  • 문자열의 각 character에서 원하는 정보를 뽑아낼 수 있어야 한다.
• 아스키 코드
  
  • 아스키 코드에 대한 이해가 좀 있어야 한다.
• 구현력(?)
  • 사실 로직 자체의 난이도는 실버 중하위수준인데, 구현이 빡쌘편이라 골드로 책정된 문제이다 ㅋㅋ 자신이 생각난걸 구현하는데 평소에 무리가 없었어야 풀만할 것 같다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  로직부터 한번 살펴보자.

 

1. "-" 이전까지 단어를 입력받아둔다. 뭔가 전처리를 해둬서 더 효율적으로 될 것 같다면 전처리를 한다. 단어의 개수를 n이라고 하겠다.

 

2. "#" 이전까지 퍼즐판을 입력받으면서 매번 이하의 로직을 진행한다. 퍼즐판도 전처리가 필요하다면 진행한다.

 

2.1 n개의 단어들 각각에대해 로직을 진행한다. 각 단어를 매칭시켜보면서 각 단어가 해당 퍼즐판으로 표현 가능한지 확인한다(예를들어 퍼즐판에 'B'가 없는데 단어에 'B'가 있다면 불가능하다. 또한 퍼즐판에 'Z'가 2개인데 단어에는 'Z'가 3개라면 불가능하다.).

2.1.1 해당 퍼즐판으로 표현 불가하다면 무시한다.

2.1.2 해당 퍼즐판으로 표현 가능하다면 2.1.3으로 진행한다.

2.1.3 해당 단어에 'A'~'Z'의 존재 여부를 각 단어마다 1번씩만 카운팅 해둔다. 즉, "APPLE"이라면 A, P, L, E를 각각 한번씩만 카운팅한다('중복된 문자는 출력하지 않는다.' 라는 조건 때문에).

 

2.2 모든 문자에 대해 '2.1'의 로직을 진행한 결과, 현재 보고 있는 퍼즐판에 대해 유효한 단어들의 'A'~'Z'가 카운팅 됬을 것이다. 이제 최소 횟수와 최대 횟수를 확인하고 출력해주면 된다.

 

 

---

 

  위 과정이 이해가 됬다면 그대로 구현하면 된다. 혹시 로직 자체를 몰라서 풀이를 본거라면 이제 구현해보러 가면 된다. 이하 내 코드에서 각각의 로직 구현에 대해 써보면 다음과 같다.

 

1. "-" 이전까지 단어를 입력받아둔다. 뭔가 전처리를 해둬서 더 효율적으로 될 것 같다면 전처리를 한다. 단어의 개수를 n이라고 하겠다.

// get words until "-"
while (true) {
    String word = br.readLine();
    if (word.equals("-")) break;
    // counting number of appearances of each alphabet
    for (int i = 0; i < word.length(); i++)
        wordsCnt[n][word.charAt(i)-'A']++;
    n++;
}

 

  내 경우 전처리로 각 단어에서 'A'~'Z'가 나온 횟수를 카운팅해뒀다. 퍼즐판도 동일한 방법으로 전처리를 한다면, 이후 각 단어가 해당 퍼즐판에 유효한지 확인할 때 'A'~'Z'가 나온 횟수들을 비교해서 하나라도 퍼즐판쪽이 적다면 유효하지 않다는걸 알 수 있다. 예를들어 퍼즐판(P)이 "ABBCDEFGH" 이고, 보고 있는 단어(W)가 "ABHH" 라면 다음과 같다. 하나라도 W쪽이 더 큰 값이 있다면 해당 퍼즐판으로 표현할 수 없는 단어이다.

 

  최대 9바이트 짜리를 고정 26바이트 짜리로 변경했으므로 메모리상에선 다소 비효율적이긴 하지만, 각 퍼즐판마다 n개의 문자를 매번 봐야하는데 그냥 String 그대로 두면 매번 처리 후 비교를 해야 하므로 시간복잡도면에서 매우 비효율적이다. 또한 int가 아니라 byte를 사용한 이유는 어차피 카운팅 횟수의 최대치가 9이기 때문이다(예를들어 "ZZZZZZZZZ"인 경우).

 

---

 

2. "#" 이전까지 퍼즐판을 입력받으면서 매번 이하의 로직을 진행한다. 퍼즐판도 전처리가 필요하다면 진행한다.

// get puzzle board until "#"
while (true) {
    String board = br.readLine();
    if (board.equals("#")) break;
    byte[] boardCnt = new byte[A_TO_Z];
    // counting number of each alphabet
    for (int i = 0; i < board.length(); i++)
        boardCnt[board.charAt(i)-'A']++;
        
...

 

  '1'과 마찬가지 방법으로 전처리를 해줬다. 이유는 '1'의 설명을 참고하자.

 

---

 

2.1 n개의 단어들 각각에대해 로직을 진행한다. 각 단어를 매칭시켜보면서 각 단어가 해당 퍼즐판으로 표현 가능한지 확인한다.

2.1.1 해당 퍼즐판으로 표현 불가하다면 무시한다.

private boolean isValid(byte[] word, byte[] board) {
    for (int i = 0; i < A_TO_Z; i++) {
        if (board[i] < word[i]) return false;
    }
    return true;
}

...
for (int i = 0; i < n; i++) {
    // ignore impossible(invalid) words
    if (!isValid(wordsCnt[i], boardCnt)) continue;

...

 

   isValid 함수가 '1'에서 그림으로 설명했던걸 체크하는 함수이다.

 

---

 

2.1.2 해당 퍼즐판으로 표현 가능하다면 2.1.3으로 진행한다.

2.1.3 해당 단어에 'A'~'Z'의 존재 여부를 각 단어마다 1번씩만 카운팅 해둔다. 즉, "APPLE"이라면 A, P, L, E를 각각 한번씩만 카운팅한다('중복된 문자는 출력하지 않는다.' 라는 조건 때문에).

...
// counting valid word's number of each alphabet
    for (int j = 0; j < A_TO_Z; j++) {
        if (wordsCnt[i][j] != 0)
            result[j]++;
    }
}

 

  유효한 녀석들에서 각 단어가 몇개 나왔든 1개로 카운팅한다('중복된 문자는 출력하지 않는다.' 조건 때문에).

 

---

 

2.2 모든 문자에 대해 '2.1'의 로직을 진행한 결과, 현재 보고 있는 퍼즐판에 대해 유효한 단어들의 'A'~'Z'가 카운팅 됬을 것이다. 이제 최소 횟수와 최대 횟수를 확인하고 출력해주면 된다.

// check min & max count
for (int j = 0; j < A_TO_Z; j++) {
    if (boardCnt[j] == 0) continue;
    if (min > result[j]) min = result[j];
    if (max < result[j]) max = result[j];
}

// print min alphabet
for (int j = 0; j < A_TO_Z; j++) {
    if (boardCnt[j] != 0 && result[j] == min)
        answer.append((char)('A'+j));
}
answer.append(' ').append(min).append(' ');

// print max alphabet
for (int j = 0; j < A_TO_Z; j++) {
    if (boardCnt[j] != 0 && result[j] == max)
        answer.append((char)('A'+j));
}
answer.append(' ').append(max).append('\n');

 

  여기서 boardCnt[j]가 0인지 아닌지 체크하는 부분들은, 최소값이 0일 경우 로직상 퍼즐판(boardCnt)에 나오지 않는 문자도 출력될 수 있어서 그걸 막아주기 위해서이다. 해당 부분 빼고 돌려보면 무슨소린지 이해할 것이다.

 

 

---

 

코드 : github

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

public class Main {
    private static final int A_TO_Z = 'z'-'a'+1;
    private static final int WORD_LIMIT = 200000;

    private boolean isValid(byte[] word, byte[] board) {
        for (int i = 0; i < A_TO_Z; i++) {
            if (board[i] < word[i]) return false;
        }
        return true;
    }

    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        byte[][] wordsCnt = new byte[WORD_LIMIT][A_TO_Z];
        int n = 0;

        // get words until "-"
        while (true) {
            String word = br.readLine();
            if (word.equals("-")) break;
            // counting number of appearances of each alphabet
            for (int i = 0; i < word.length(); i++)
                wordsCnt[n][word.charAt(i)-'A']++;
            n++;
        }

        StringBuilder answer = new StringBuilder();
        // get puzzle board until "#"
        while (true) {
            String board = br.readLine();
            if (board.equals("#")) break;
            byte[] boardCnt = new byte[A_TO_Z];
            // counting number of each alphabet
            for (int i = 0; i < board.length(); i++)
                boardCnt[board.charAt(i)-'A']++;

            int[] result = new int[A_TO_Z];
            int min = WORD_LIMIT+1;
            int max = 0;
            for (int i = 0; i < n; i++) {
                // ignore impossible(invalid) words
                if (!isValid(wordsCnt[i], boardCnt)) continue;

                // counting valid word's number of each alphabet
                for (int j = 0; j < A_TO_Z; j++) {
                    if (wordsCnt[i][j] != 0)
                        result[j]++;
                }
            }

            // check min & max count
            for (int j = 0; j < A_TO_Z; j++) {
                if (boardCnt[j] == 0) continue;
                if (min > result[j]) min = result[j];
                if (max < result[j]) max = result[j];
            }
            
            // print min alphabet
            for (int j = 0; j < A_TO_Z; j++) {
                if (boardCnt[j] != 0 && result[j] == min)
                    answer.append((char)('A'+j));
            }
            answer.append(' ').append(min).append(' ');
            
            // print max alphabet
            for (int j = 0; j < A_TO_Z; j++) {
                if (boardCnt[j] != 0 && result[j] == max)
                    answer.append((char)('A'+j));
            }
            answer.append(' ').append(max).append('\n');
        }
        System.out.print(answer);
    }
    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}