[SWEA] 9611 명진이와 동휘의 숫자 맞추기 (Java)

1.  문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AXBbOcTav0QDFAVg&categoryId=AXBbOcTav0QDFAVg&categoryType=CODE&problemTitle=&orderBy=PASS_RATE&selectCodeLang=ALL&select-1=3&pageSize=10&pageIndex=17#none

2.  소스코드

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

public class Main {
    static final int SIZE = 10;
    static final int TURN_SIZE = 4;
    static final String IMPOSSIBLE = "NO";

    static StringBuilder answer = new StringBuilder();
    static Reader scanner = new Reader();

    static int questionCount;
    static int[] candidate;

    static void input() {
        questionCount = scanner.nextInt();
        candidate = new int[SIZE];
        Arrays.fill(candidate, 1);

        int[] numbers = new int[TURN_SIZE];
        for(int question = 0; question < questionCount; question++) {
            for(int idx = 0; idx < TURN_SIZE; idx++) {
                numbers[idx] = scanner.nextInt();
            }
            String status = scanner.next();

            updateCandidate(status, numbers);
        }
    }

    static void updateCandidate(String status, int[] numbers) {
        if(status.equals(IMPOSSIBLE)) {
            Arrays.stream(numbers).forEach(number -> candidate[number] = 0);
            return;
        }
        Arrays.stream(numbers).forEach(number -> candidate[number] *= 2);
    }

    static void solution() {
        int max = Integer.MIN_VALUE;
        int maxIdx = 0;
        for(int idx = 0; idx < SIZE; idx++) {
            if(candidate[idx] > max) {
                max = candidate[idx];
                maxIdx = idx;
            }
        }
        answer.append(maxIdx).append('\n');
    }

    public static void main(String args[]) {
        int T = scanner.nextInt();
        for(int test = 1; test <= T; test++) {
            answer.append('#').append(test).append(' ');
            input();
            solution();
        }
        System.out.print(answer);
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

3.  접근

• 0부터 9까지 가중치를 나타내는 배열을 하나 생성하여 YES로 답해준 4개의 숫자에는 2를 곱하고, NO로 답해준 4개의 숫자는 0으로 값을 변경한다.
  • NO로 답해준 4개의 숫자는 더이상 생각한 숫자가 될 수 있는 가능성이 없기 때문에 가중치는 가장 낮아야 한다.
  • YES로 답해준 4개의 숫자는 생각한 숫자가 될 수 있는 가능성이 존재하기 때문에 가중치를 높여야 한다.
  • 문제에서는 명진이가 생각한 숫자는 언제나 유일하게 결정됨이 보장되는 경우만 입력으로 주어진다고 하였으니 위와 같은 방식으로 진행하다보면 가중치가 가장 높은 숫자 하나가 존재할 것이고, 그 숫자가 명진이가 생각한 숫자가 된다.
  • 위에서 말했듯 NO로 답해준 숫자에 대해서는 가중치가 가장 낮아야 하고 이후에 YES로 답해준 4개의 숫자에 해당 숫자가 포함되더라도 해당 숫자의 가중치는 가장 낮아야 한다.
  • 그러므로 가중치를 높일 때 곱셈을 이용한다.
    • 더이상 생각한 숫자가 될 수 없는 숫자들의 가중치를 0으로 만든다면 YES로 답해준 4개의 숫자에 해당 숫자가 포함되어 있어 같이 가중치를 높이려고 해도 가중치를 높일 수 없다.