BOJ_27172 : 수 나누기 게임

👉 문제링크

27172번: 수 나누기 게임

---

🔸 문제 분석 🔸

• 최대 10만개의 서로 다른 수가 적힌 카드가 있다. 이때 수는 1~100만 사이의 정수이다.
• 카드들을 서로 결투를 벌여서 나누어 떨어지면, 나누는 수는 +1, 나누어진 수는 -1 점을 받는다.
• 모든 카드들을 결투시켜 최종 점수를 출력한다.

🔸 문제 풀이 🔸

• N이 10만이므로 O(NlogN)로 비교하면, 100억번으로 제한 시간인 1초를 초과하게 된다.
• 에라토스테네스의 체를 활용해서 소수가 아닌, 카드 숫자의 배수 인덱스만 확인해서 결투를 진행하는 방식으로 풀이하면 된다.
  • 이때, 현재 게임에 등장한 카드 번호인지 확인이 필요하다.

🔸 코드 🔸

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

public class Main {

    public static void main(String[] args) throws IOException {
        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int[] cards = new int[N];
        boolean[] isNum = new boolean[1_000_001];
        int max = -1;

        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
            max = Math.max(cards[i], max);
            isNum[cards[i]] = true;
        }

        int[] points = new int[max + 1];

        // 수 나누기 게임
        for (int i = 0; i < N; i++) {
            for (int j = 2; cards[i] * j <= max; j++) {
                if (isNum[cards[i] * j]) {
                    points[cards[i]]++;
                    points[cards[i] * j]--;
                }
            }
        }

        // 출력
        for (int i = 0; i < N; i++) {
            sb.append(points[cards[i]]).append(' ');
        }

        bw.write(sb.toString());
        bw.flush();
    }
}

🔸 코드 해석 🔸

• N개의 카드 숫자를 담은 int배열 cards가 있다.
• 현재 게임에 등장한 카드인지 확인하기 위한 boolean 배열 isNum에 카드 인덱스에 따라 true를 저장하고, 불필요한 계산을 줄이고자 최대값을 max에 저장하기도 했다.
• 한 카드를 max까지 배수 확인으로 수 나누기 게임을 진행한다.
  • 배수로 나온 인덱스의 번호가 현재 게임에 등장한 카드 번호이면, 나누어 떨어지는 수라는 것이므로 점수를 계산한다.
• 카드 번호에 따라 점수 배열 points의 인덱스에 접근해 점수를 출력한다.

---

🔸 end 🔸

•  처음엔 시간 초과가 날 것임을 알았지만, 혹시 연산이 그렇게 무겁지 않아서 괜찮을까 하고 O(nlogn)으로 중첩 반복문으로 모두 검사하는 방식으로 해봤지만 시간초과가 났다.
  • 태그에 에라토스테네스의 체가 있길래 소수는 나누어떨어지지 않으니까, 소수를 모두 찾고 그 수들은 게임에서 제외한다는 건가? 했는데 아니나 다를까 틀렸다.
• 질문 게시판을 조금 뒤져보니 에라토스테네스의 체를 소수로만 이해하지 말고, 그와 같은 방식으로 배수 접근을 하면 된다는걸 알았다.
• boolean 배열 isNum의 크기를 1_000_000으로 주었더니 딱 맞게 1_000_000가 나오는 경우가 있는지, 런타임 에러가 나서 수정했다.