SWEA 10993. 군주제와 공화제

하나의 도시가 가진 군사력이 각각의 다른 도시들의 영향력보다 크면 군주제, 작으면 가장 영향력이 큰 도시가 1개라면 해당 도시를 따르고, 2개 이상이라면 공화제를 도입할 때, 각 도시들이 군주제인지, 공화제인지, 아니라면 따르게 되는 도시의 번호를 출력하는 문제이다. 하나의 도시가 받는 각각의 영향력은  군사력 / 각각의 도시와의 거리 이다. si / ( (xj - xi)^2+(yj - yi)^2 )

 

2중 반복문을 통해 하나의 도시가 다른 모든 도시에게 받는 영향력을 군사력과 비교했을 때, 군사력이 더 크면 군주제로서 -1로 표시하였고, 영향력이 큰 경우 중 1개만 크면 큰 도시를 따르므로 따르는 도시의 index로 표시하였고, 2 도시 이상이 가장 큰 경우 공화제로 -2를 표시하였다. 표시한 대로 군주제라면 K, 공화제면 D, 다른 도시를 따르게 되면 최종으로 따르게 되는 도시의 번호를 출력하면 된다.

static class City {
    int x, y, s;
        
    public City(int x, int y, int s) {
        this.x = x;
        this.y = y;
        this.s = s;
    }
}

City[] board = new City[n];
for(int i=0; i<n; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken()), s = Integer.parseInt(st.nextToken());
    board[i] = new City(x, y, s);
}
int[] results = new int[n];
for(int i=0; i<n; i++) {
    double maxDiff = 0;
    int index = -1;
    City a = board[i];
    for(int j=0; j<n; j++) {
        if(i == j) continue;
        City b = board[j];
        double diff = (double) board[j].s /((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)) - a.s;
        if(diff > maxDiff) {
            maxDiff = diff;
            index = j;
        } else if(diff == maxDiff) {
            if(diff <= 0) continue;
            index = -2;
        }
    }
    results[i] = index;
}
            
for(int i=0; i<n; i++) {
    if (results[i] == -1) {
        sb.append("K ");
    } else if (results[i] == -2) {
        sb.append("D ");
    } else { 
        int curr = i;
        while (results[curr] >= 0) {
            curr = results[curr];
        }
        sb.append(curr + 1).append(' ');
    }
}

 

 

결과 코드는 다음과 같다.

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

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        
        StringBuilder sb = new StringBuilder();
        for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            int n = Integer.parseInt(br.readLine());
            City[] board = new City[n];
            for(int i=0; i<n; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken()), s = Integer.parseInt(st.nextToken());
                board[i] = new City(x, y, s);
            }
            int[] results = new int[n];
            for(int i=0; i<n; i++) {
                double maxDiff = 0;
                int index = -1;
                City a = board[i];
                for(int j=0; j<n; j++) {
                    if(i == j) continue;
                    City b = board[j];
                    double diff = (double) board[j].s /((a.x-b.x)*(a.x-b.x) + (a.y-b.y)*(a.y-b.y)) - a.s;
                    if(diff > maxDiff) {
                        maxDiff = diff;
                        index = j;
                    } else if(diff == maxDiff) {
                        if(diff <= 0) continue;
                        index = -2;
                    }
                }
                results[i] = index;
            }
            
            for(int i=0; i<n; i++) {
                if (results[i] == -1) {
                    sb.append("K ");
                } else if (results[i] == -2) {
                    sb.append("D ");
                } else { 
                    int curr = i;
                    while (results[curr] >= 0) {
                        curr = results[curr];
                    }
                    sb.append(curr + 1).append(' ');
                }
            }
            sb.append('\n');
        }
        
        br.close();
        System.out.print(sb);
    }
    
    static class City {
        int x, y, s;
        
        public City(int x, int y, int s) {
            this.x = x;
            this.y = y;
            this.s = s;
        }
    }
}