백준 7568번 문제풀이 - 덩치

백준 7568번 문제

 

 

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

7568번: 덩치

 

사람들의 키와 몸무게를 입력받고 그 순위를 출력하는 문제이다. 순위는 키와 몸무게 둘 다 커야 등 수를 유지할 수 있다.

 

모든 사람들의 키와 몸무게를 비교해야 되기 때문에 브루트 포스 알고리즘으로 문제를 풀었다.

 

 

 

 

 

코딩

 

public class Frame {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[50][3];
        
        // 몸무게와 키를 입력받음
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < 2; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        // 등수를 1로 초기화
        for (int i = 0; i < N; i++) {
            arr[i][2] = 1;
        }
        
        int n = 0;
        // 등수 판별
        while (n < N) {
            for (int i = 0; i < N; i++) {
                if (i == n) {
                    continue;
                }
                if (arr[n][0] < arr[i][0] && arr[n][1] < arr[i][1]) {
                    arr[n][2]++;
                } else if (arr[n][0] < arr[i][0] && arr[n][1] < arr[i][1]) {
                    arr[i][2]++;
                }
            }
            n++;
        }
        
        for (int i = 0; i < N; i++) {
            sb.append(arr[i][2]).append(' ');
        }

        System.out.println(sb);
    }
}

 

 

 

 

 

결과

 

 

처음 제출시보다 두 번째 제출 때 시간이 조금 줄었는데 그 이유는

if (i == n) {
  continue;

}

이 부분을 추가하면서 같은 비교를 또 하지 않기 때문에 시간이 줄어들었다.

 

 

 

 

 

느낀 점

 

브루트포스는 모든 경우를 비교하면 되기 때문에 푸는데 어려움은 없지만 더 효율을 증가시키는 방법을 고민해보는 것이 중요한 것 같다. 조금 더 개선할 부분을 항상 고민하는 것이 좋을 것 같다.