https://www.acmicpc.net/problem/7568
제출코드
시간초과
모범답안
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 오타 수정됨
int N = Integer.parseInt(br.readLine());
int[][] arr = new int [N][2];
String[] sp;
for(int i=0; i<N; i++) {
sp = br.readLine().split(" ");
arr[i][0] = Integer.parseInt(sp[0]);
arr[i][1] = Integer.parseInt(sp[1]);
}
for (int i = 0; i <N; i++) {
int rank = 1;
for (int j = 0; j < N; j++) {
// 같은 사람은 비교할 필요 없음
if (i == j) continue;
/**
* i번째 사람과 j번째 사람을 비교하여
* i가 j보다 덩치가 작으면 rank를 1 증가시킨다.
*/
if (arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
rank++;
}
}
System.out.print(rank + " ");
}
}
}
-
몸무게, 키가 담긴 2차원배열을 만든다.
-
이중 반복문을 통해 각 배열의 인덱스를 모두 탐색하는 방법이다.
이때 각 비교되는 두 인덱스의 각각의 키와 몸무게를 비교하여 랭크를 지정해주는 방식이다. -
rank = 1 부터 시작하여 해당 사람보다 덩치가 큰 사람이 있을 경우 해당 사람은 순위는 뒤로 밀리기 때문에 rank 값을 증가시킨다.
이렇게 자기 자신을 제외한 나머지 사람들을 모두 비교하여 rank 값을 출력한다.
만약 자기보다 덩치가 큰 사람이 없을 경우 rank 는 1 이 될 것이고, 덩치가 큰 사람이 K 명 있을 경우 rank + K 가 자신의 랭크(순위)가 될 것이다.
배운점
-
머리로는 이해가 됐는데 코드로 어떻게 표현해야 할 지 어려웠다.
특히 비교하면서 rank를 구하는 것이 까다로웠다.
이 부분은 rank를 1로 초기값으로 설정한 뒤, 만약 비교하는 요소가 현재 요소보다 크다면, 1을 증가시키면 해결되는 문제였다. -
이중반복문에 대한 오개념을 찾았다.
나는 원래 n중 반복문을 사용할 때 요소가 커지면서 비교하는 개수도 적어지는 줄 알고 있었다.
그런데 이는 완벽한 오개념이었다. 이중 반복문의 처리 방식은 크게 2개로 나눌 수 있다.
a. 반복을 진행하면서 다른 요소들과 비교 하는 개수가 순차적으로 작아진다.(1,2,3의 경우 3의 차례 때 비교할 요소가 없음)
b. 반복을 진행하면서 다른 요소들과 비교 하는 개수가 모두 동일하다. (1,2,3의 경우 3의 차례 때 3과 1,2를 또다시 비교)
코드로 살펴보자.
- 반복을 진행하면서 다른 요소들과 비교하는 개수가 순차적으로 작아지는 경우.
이 경우, 각 단계에서 비교 대상의 개수를 줄이기 위해 내부 반복문의 범위를 조정한다.
예를 들어, 배열의 각 요소를 다른 모든 요소와 비교하지만, 이미 비교된 요소는 제외하는 방식이다.
public class DecreasingComparisons {
public static void main(String[] args) {
int[][] arr = {{1, 2}, {3, 4}, {5, 6}};
for (int i = 0; i < arr.length; i++) {
// i번째 요소 이후의 요소들과만 비교
for (int j = i + 1; j < arr.length; j++) {
System.out.println("Comparing: " + arr[i][0] + "," + arr[i][1] + " and " + arr[j][0] + "," + arr[j][1]);
}
}
}
}
Comparing: 1,2 with 3,4
Comparing: 1,2 with 5,6
Comparing: 3,4 with 5,6
- 반복을 진행하면서 다른 요소들과 비교하는 개수가 모두 동일한 경우
이 경우, 배열의 모든 요소를 서로 비교한다. 이는 각 요소를 선택하고, 선택된 요소를 배열 내의 모든 다른 요소와 비교하는 방식으로 구현된다. 이때, 자기 자신과의 비교는 제외한다.
public class ConstantComparisons {
public static void main(String[] args) {
int[][] arr = {{1, 2}, {3, 4}, {5, 6}};
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
// 자기 자신과의 비교는 제외
if (i == j) continue;
System.out.println("Comparing: " + arr[i][0] + "," + arr[i][1] + " and " + arr[j][0] + "," + arr[j][1]);
}
}
}
}
Comparing: 1,2 with 3,4
Comparing: 1,2 with 5,6
Comparing: 3,4 with 1,2
Comparing: 3,4 with 5,6
Comparing: 5,6 with 1,2
Comparing: 5,6 with 3,4
