[BOJ/백준] 16677번 - 악마 게임(Java 풀이/해답)

문제 바로가기: https://www.acmicpc.net/problem/16677

게임 관련 문제라고 생각했는데, 문자열 문제였다

처음에 Map, Priority Queue 등으로 구현하려다가 단순 비교로 변경해서 해결했다

풀이 과정에서의 삽질이 있기 때문에 정답을 바로 보고 싶으신 분들은 풀이와 정답코드로 건너뛰어 주세요

 

문제

악마 게임은 프로스트 엔터테인먼트에서 제작한 RPG 게임으로 3번째 시리즈까지 나왔다. 악마 게임은 출중한 게임성으로 인해 두터운 팬층을 갖고 있다.

며칠 전에 악마 게임 개발발표회가 있었다. 제작진들은 전부터 계속 신작 떡밥을 뿌려왔기 때문에 팬들은 엄청난 기대를 하고 있었다. 팬들은 다 같이 ‘Devil IV’의 출시를 목놓아 외치고 있었다.

마침내 개발발표회가 있던 날이 다가왔다. 사회자가 화면에 ‘Devil IV’를 띄우자 관중은 환호했다. 그러나 그 환호는 잠깐이었다. ‘Devil IV’의 뒤에 작대기가 하나 그어져 ‘Devil IVI’가 된 순간, 발표회 분위기가 순식간에 싸늘해졌다. 팬들은 갑작스러운 상황 변화를 받아들이지 못하여 분노하기 시작했다. 그때 분위기는 어느 팬이 외쳤던 ‘이거 철 지난 만우절 장난이죠?’라는 질문 하나로 설명할 수 있을 것이다.

악마 게임의 오랜 팬인 동엽이는 그 때의 일에 충격받아 이걸 팀플 발표에 써먹으려고 한다. 동엽이는 우선 재밌는 단어를 ppt에 띄워서 청중의 관심을 유발한 다음에 단어 처음, 끝, 중간에 몇 글자를 끼워넣어 분위기를 싸하게 만들 것이다.

동엽이는 ‘갑분싸 사전’을 갖고 있다. 그는 원래 단어로부터 사전에 있는 단어를 만들어 분위기를 얼어붙게 할 것이다. 사전에 있는 단어들은 단어별로 갑분싸의 정도가 다른데, 동엽이는 최대한 갑분싸의 정도가 큰 단어를 만들려고 한다. 그러나 글자를 너무 많이 끼워 넣으면 재미없기 때문에 동엽이는 추가한 글자 수 대비 갑분싸의 정도가 가장 큰 단어를 선택하려고 한다. 동엽이를 도와 단어를 선택하는 프로그램을 작성하여라.

입력

첫 번째 줄에 동엽이가 재밌다고 생각하는 원래 단어 m이 주어진다.

두 번째 줄에 갑분싸 사전에 있는 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)

이후 N 개의 줄에 걸쳐 갑분싸 사전에 있는 단어들이 주어지며, 각 줄에 단어 w와 그 단어의 갑분싸 정도 g가 공백으로 구분되어 주어진다. (1 ≤ g ≤ 10,000)

모든 단어는 알파벳 대문자로만 이루어져 있으며 길이는 1 이상 100 이하이다.

원래 단어와 사전에 있는 단어들은 서로 다르다.

 

출력

첫 번째 줄에 넣은 글자 수 대비 갑분싸의 정도가 가장 큰 단어를 출력한다.

만약 그런 단어가 여러 개라면, 갑분싸 사전에서 가장 먼저 등장하는 단어를 출력한다.

만약 만들 수 있는 단어가 없다면, "No Jam"을 쌍따옴표를 제외하고 출력한다.

 

예제 입력 1

DEVILIV
4
DEVILIVI 10
DEVILM 11
DEVILIVCONFIRMED 66
DENVERVILLAINV 70

 

예제 출력 1

DEVILIVI

 

예제 입력 2

SUBINIUM
3
INSSADANCINGMACHINE 12
SOULLESSDANCINGMACHINE 345
ALGORITHMDANCINGMACHINE 6789

 

예제 출력 2

No Jam

 

조건

시간제한: 1초
메모리 제한: 256MB

 

접근

1차 접근

Map<Integer, Node> 형식으로 정보를 저장한 다음 진행하려고 했다

그리고 Priority Queue에 값을 저장하며 출력하려고 했더니, Map이 사실상 필요가 없는 상황이 되었다

 

그래서 Map을 지우고 Priority Queue에 Node를 집어넣은 다음 값이 큰 순위로, 같으면 index가 작은 순으로 출력하고자 했다

 

그러나 8퍼에서 계속 틀렸습니다가 떴고 문제를 찾기 시작했다

예상으로는 실수 형태의 "갑분싸"지수가 나올 경우 비교가 제대로 안 되는 것이었다

 

따라서 코드를 수정하기 시작했다

다음은 오류 코드다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
  static class Node {
    String word;
    int index;
    int value;

    public Node(String word, int index, int value) {
      this.word = word;
      this.index = index;
      this.value = value;
    }
  }

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

    String base = br.readLine();
    int N = Integer.parseInt(br.readLine());

    // 정답 단어들은 PQ에 넣을건데, 그럼 Map은 필요가 없다
    // pq에 노드를 넣고, 갑분싸 정도도 넣어야겠다
    // 갑분싸 정도는 지수 / 단어 갭으로 구하는데, 몫만 쓰면 되나?
    PriorityQueue<Node> pq =
        new PriorityQueue<>(
            new Comparator<Node>() {
              @Override
              public int compare(Node o1, Node o2) {
                if (o1.value == o2.value) {
                  return o1.index - o2.index;
                }

                return o2.value - o1.value;
              }
            });

    for (int i = 0; i < N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      String word = st.nextToken();
      int value = Integer.parseInt(st.nextToken());
      int idx = 0;

      for (int j = 0; j < word.length(); j++) {
        if (base.charAt(idx) == word.charAt(j)) {
          idx++;
          if (idx >= base.length()) break;
        }
      }

      if (idx >= base.length())
        pq.offer(new Node(word, i, (int) ((word.length() - base.length()) / value)));
    }

    if (pq.isEmpty()) System.out.println("No Jam");
    else System.out.println(pq.poll().word);
  }
}

 

생각해 보니 pq에 넣을 필요 없이, 정답 값을 계속 수정하면서 반복문 한 번만 진행하면 되지 않을까 싶었다

그래서 전략을 조금 수정했다

 

double 값을 쉽게 비교하기 위해 반복문 단계에서 값을 비교한 다음 정답을 수정해 나가는 것으로 진행했다

그랬더니... 50 퍼쯤에서 틀렸다

 

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

public class Main {

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

    String base = br.readLine();
    String answer = "";
    double maxValue = 0;
    int N = Integer.parseInt(br.readLine());

    for (int i = 0; i < N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      String word = st.nextToken(); // 받아온 단어
      int diff = word.length() - base.length(); // 해당 단어의 길이
      double value = Double.parseDouble(st.nextToken()) / diff; // 나눈 값
      int idx = 0;

      for (int j = 0; j < word.length(); j++) {
        if (base.charAt(idx) == word.charAt(j)) {
          idx++;
          if (idx >= base.length()) break;
        }
      }
      if (maxValue == value) continue;

      maxValue = Math.max(maxValue, value);

      if (idx >= base.length() & maxValue == value) {
        answer = word;
      }
    }

    if (answer.isEmpty()) System.out.println("No Jam");
    else System.out.println(answer);
  }
}

 

예상으로는 반복문에서 maxValue와 value를 비교하고 수정하는 부분에서 문제가 되는 테스트 케이스가 있을 것 같았다

그래서 조금 더 직관적으로 바꿨더니 해결되었다

 

풀이

1. 기본 단어를 base라는 변수에 담는다

2. 갑분싸 지수를 담을 maxValue를 초기화한다

3. 단어 사전의 수 N을 입력받고 반복문을 수행한다

   3-1. 단어 사전의 단어를 입력받는다

   3-2. 해당 단어의 갑분싸 지수를 받는다

4. double 형태의 value 값을 base 단어와 현재 단어 word의 길이 차이로 나눈다

 

5. base 단어가 들어가는지 확인하기 위한 idx를 사용한다

 

6. 현재 사전의 단어를 반복문으로 돌며 base단어와 비교, 일치하는 경우 idx를 늘려 base 단어의 다음 철자를 비교해 준다

 

7. base 단어만큼 돌았으면 반복문을 종료한다

 

8. base 단어가 포함되어 있고(idx가 base 단어의 길이보다 같거나 크고), 최대 값보다 현재의 값이 더 큰 경우만 정답 초기화를 진행한다

   8-1. 최댓값을 현재 value로 설정한다

   8-2. 단어를 현재의 word로 설정한다

 

9. 만약 정답 단어가 비어있다면(answer = "")에서 변경이 안되었다면 "No Jam"을 출력하고, 아닌 경우에는 answer를 그대로 출력해 준다

정답 코드

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

public class Main {

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

    String base = br.readLine();
    String answer = "";
    double maxValue = 0;
    int N = Integer.parseInt(br.readLine());

    for (int i = 0; i < N; i++) {
      StringTokenizer st = new StringTokenizer(br.readLine());
      String word = st.nextToken(); // 받아온 단어
      int diff = word.length() - base.length(); // 해당 단어의 길이
      double value = Double.parseDouble(st.nextToken()) / diff; // 나눈 값
      int idx = 0;

      for (int j = 0; j < word.length(); j++) {
        if (base.charAt(idx) == word.charAt(j)) {
          idx++;
          if (idx >= base.length()) break;
        }
      }

      if (idx >= base.length() & maxValue < value) {
        maxValue = value;
        answer = word;
      }
    }

    if (answer.isEmpty()) System.out.println("No Jam");
    else System.out.println(answer);
  }
}