[백준] 20949번: 효정과 새 모니터_Java

 

제목: 효정과 새 모니터

실버5

 

---

 

 

 

---

입력

첫 번째 줄에 모니터의 개수 N이 주어진다.

이후 N개의 줄 중 i(1 ≤ i ≤ N)번째 줄에는 i번 모니터의 가로 픽셀 수 Wi와 세로 픽셀 수 Hi가 주어진다.

모든 입력은 정수이며 공백으로 구분되어 주어진다.

출력

N개의 줄에 걸쳐 모니터의 번호를 PPI가 높은 순으로 한 줄에 하나씩 출력한다.

PPI가 동일한 경우 번호가 더 작은 모니터를 먼저 출력한다.

제한

• 1 ≤ N ≤ 1,000
• 1 ≤ Wi, Hi ≤ 30,000

예제 입력 1 복사

2
10 10
20 20

예제 출력 1 복사

 

2
1

 

 

 

---

 

 

 

  문제는 어렵지 않다. 입력받은 모니터 가로와 세로 값들을 PPI 공식에 대입해 계산결과로 값을 받게 된다. PPI 공식으로부터 가장 큰 모니터의 번호부터 출력하면 된다. 번호는 모니터의 생성 순서와 같다. (1번으로 입력한 모니터는 1번, 2번으로 입력한 모니터는 2번 . . . )  시간복잡도가 O(n^2) 까지는 풀 수 있을 것 같아 쉬운 문제이다. 

 

 

🔑 내가 작성한 코드

 

import java.io.*;
import java.util.StringTokenizer;
import java.util.ArrayList;
import java.util.Collections;

public class Main {

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

		ArrayList<Float> list = new ArrayList<>();

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int width = Integer.parseInt(st.nextToken());
			int height = Integer.parseInt(st.nextToken());
			float ppi =(float)Math.sqrt(width * width + height * height) / 24;
			list.add(ppi);
		}

		ArrayList<Float> copyList = new ArrayList<>(list);
		Collections.sort(list);
		StringBuilder sb = new StringBuilder();

		for (int i = list.size() - 1; i >= 0; i--) {
			float key = list.get(i);
			int index = copyList.indexOf(key);
			copyList.set(index, null);
			sb.append(index + 1 + "\n");
		}
		System.out.println(sb);
	}
}

 

 

 

 

 

알고리즘 분류

• 정렬

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

20949번: 효정과 새 모니터