[백준 JAVA] 27172. 수 나누기 게임

문제 링크

---

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

접근 방법

---

각 카드 번호를 기준으로 배수 관계에 있는 다른 카드들과의 관계를 탐색합니다.
자신의 배수인 수가 다른 카드에 존재하면 +1점, 자신이 누군가의 배수이면 -1점 처리합니다.
배열 score를 사용해 모든 카드의 점수를 기록한 뒤 출력합니다.

소스 코드

---

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] card = new int[n], sortCard = new int[n];
        for (int i = 0; i < n; i++) {
            card[i] = sortCard[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(sortCard);

        int max = sortCard[n - 1] + 1;
        int[] score = new int[max];
        boolean[] isNum = new boolean[max];

        for (int i = 0; i < sortCard.length; i++) {
            isNum[sortCard[i]] = true;
        }

        for (int i = 0; i < n; i++) {
            for (int j = sortCard[i] * 2; j < max; j += sortCard[i]) {
                if (isNum[j]) {
                    --score[j];
                    ++score[sortCard[i]];
                }
            }
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < n; i++) {
            sb.append(score[card[i]]).append(" ");
        }

        System.out.println(sb);
    }
}

코드 설명

---

isNum[x]는 입력된 카드 중 숫자 x가 있는지를 나타냅니다.
자신이 이기는 경우: score[자신]++
자신이 지는 경우: score[상대]--

 

배수 관계를 빠르게 탐색하여 점수를 기록하고, 각 카드에 대해 최종 점수를 출력합니다.