백준 1900 - 레슬러 ( JAVA )

출처 - 백준 알고리즘

1900번: 레슬러

---

 

알고리즘 

 

: 그리디 + 정렬 

1:1 경기를 통해 각 선수의 이긴 횟수를 카운트 한다. 

( N명의 선수 중 2명의 조합을 찾아 경기를 하면 되므로 이중 반복문을 통해 구현) 

 

금화의 수를 최소화하기 위해선, 많이 이긴 순대로 금화를 수여해야 한다. 

금화 = 이긴 경기 수 + 자기 보다 앞에 있는 선수 중 이긴 선수 이기 때문에, 앞쪽에서 수여해야 ' 자기보다 앞에 있는 선수 중 이긴 선수 '의 값이 작아진다. 

 

즉, 선수들 마다 경기에서 이긴 횟수를 count 하고, 해당 값을 기준으로 내림차순 정렬하여 출력한다. 

 

 

1.  N명의 선수들이 주어질 때 2차원 배열을 생성하여 [ 선수의 힘 , 마술링의 힘, 승리 횟수, 선수번호 ] 를 저장한다. 

 

2.  이중 for 문을 통해 1:1 경기를 구현한다. 이긴 선수의 승리 횟수를 count ++ 한다.

( 조합 : 1 vs 2 == 2 vs 1 )

 

3.  모든 경기가 끝났을 때, 배열을 ' 승리 횟수 ' 를 기준으로 내림차순 정렬한다. ( 많이 이긴 선수가 앞쪽으로 )

 

4.  순서대로 ' 선수 번호 ' 출력하면 끝 !  

 

---

 

소스 코드 

import java.io.*;
import java.util.*;

public class Solution_BaekJoon_1900{
	public static void main(String[] args) throws Exception{
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine()); //선수의 수 
		int[][] player = new int [N][4];
		dlrls
		for(int i=0; i<N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			
			player[i][0] = Integer.parseInt(st.nextToken());
			player[i][1] = Integer.parseInt(st.nextToken());	
			player[i][2] = i+1; // 선수 번호 
		}// -------------- input ----------------

		for(int i=0; i<N-1; i++) {
			for(int j=i+1; j<N; j++) {
				int power1 = player[i][0] + player[i][1] * player[j][0]; 
				int power2 = player[j][0] + player[j][1] * player[i][0]; 
				
				if(power1 > power2) player[i][3] ++;
				else player[j][3]++; 
			}
		}
		// 이긴횟수 기준 내림차순 정렬 
		Arrays.sort(player, (p1, p2) ->{
			return p2[3] - p1[3]; 
		});
		
		for(int i=0; i<N; i++) {
			System.out.println(player[i][2]);
		}
		
	} // end of main
}// end of class

끗