[백준/JAVA] 7568번 덩치 (브루트포스, 구현)

문제 설명

코딩테스트 초보라서.. 맨 처음에 Map으로 해야 하나.. List로 해야 하나 고민했다. (2차원배열을 쓰면 되는데..)
그러다가 그냥 Man이라는 클래스를 하나 만들어서 몸무게, 키, 나보다 큰 사람 수 세개의 필드를 만들고 입력받은 값으로 Man 객체를 생성해서 List에 넣고 for문을 돌며 비교하는 방법을 생각해 냈다. 이후에 다른 사람의 풀이를 찾아보니 간편하게 배열로 푸는 것을 보고 배열로도 풀어봤다.

입, 출력은 BufferedReader, StringTokenizer, StringBuilder를 이용해서 풀었다.

---

풀이 1 전체 코드

public class No7568 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

        //list에 man 넣기
        List<Man> list = new ArrayList<>();
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            int tall = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            Man man = new Man(tall,weight);
            list.add(man);
        }
        //man의 count 설정
        for(int i=0;i<N;i++){
            Man thisMan = list.get(i);
            for(int j=0;j<N;j++){
                if(i == j)continue;
                Man compareMan = list.get(j);
                if(isSmaller(thisMan,compareMan)){
                    thisMan.count();
                }
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<N;i++){
            Man man = list.get(i);
            sb.append(man.count+1).append(" ");
        }
        System.out.println(sb);

    }

    public static boolean isSmaller(Man thisMan, Man compareMan){
        if(thisMan.tall<compareMan.tall && thisMan.weight<compareMan.weight){
            return true;
        }
        return false;
    }
    static class Man{
        int tall;
        int weight;
        int count;

        public Man(int tall, int weight) {
            this.tall = tall;
            this.weight = weight;
            this.count = 0;
        }
        public void count() {
            this.count++;
        }
    }
}

풀이 2 전체 코드

public class No7568_2 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader((System.in)));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());

        //배열에 man 넣기
        int[][] arr = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int tall = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            arr[i][0] = tall;
            arr[i][1] = weight;
        }
        //비교
        for(int i=0;i<N;i++){
            int rank = 1;
            for(int j=0;j<N;j++){
                if(i==j) continue;
                if(isSmaller(arr[i],arr[j])){
                    rank++;
                }
            }
            sb.append(rank).append(" ");
        }
        System.out.println(sb);
    }
    public static boolean isSmaller(int[] thisMan, int[] compareMan){
        if(thisMan[0]<compareMan[0] && thisMan[1]<compareMan[1]){
            return true;
        }
        return false;
    }
}

---

풀이 1

우선 Man 클래스를 하나 만든다.

키, 몸무게, 나보다 큰 사람의 수 세개의 필드와 count를 하나 증가시켜 줄 메서드를 만들었다.

static class Man{
        int tall;//키
        int weight;//몸무게
        int count;//나보다 큰 사람의 수

        public Man(int tall, int weight) {
            this.tall = tall;
            this.weight = weight;
            this.count = 0;
        }
        public void count() {
            this.count++;
        }
    }

값을 입력받아서 Man 객체를 생성하고 List에 넣는다.

        List<Man> list = new ArrayList<>();
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            int tall = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            Man man = new Man(tall,weight);
            list.add(man);
        }

for문을 돌며 각각 자기자신(thisMan)을 제외한 다른 Man(compareMan)들과 비교하여

thisMan이 작을 경우 나보다 더 큰 사람의 수를 증가시킨다.

	for(int i=0;i<N;i++){
            Man thisMan = list.get(i);
            for(int j=0;j<N;j++){
                if(i == j)continue;
                Man compareMan = list.get(j);
                if(isSmaller(thisMan,compareMan)){
                    thisMan.count();
                }
            }
        }
        
//isSmaller 메서드
public static boolean isSmaller(Man thisMan, Man compareMan){
        if(thisMan.tall<compareMan.tall && thisMan.weight<compareMan.weight){
            return true;
        }
        return false;
    }

이후에는 List에서 순서대로 Man 객체를 하나씩 꺼내서 그 Man 객체의 count +1 값을 출력한다.

---

풀이 2

값을 입력받아서 2차원 배열에 넣어준다.

arr[][0]은 키, arr [][1]은 몸무게이다.

 //배열에 값 넣기
        int[][] arr = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int tall = Integer.parseInt(st.nextToken());
            int weight = Integer.parseInt(st.nextToken());
            arr[i][0] = tall;
            arr[i][1] = weight;
        }

rank는 순위이고, 나보다 큰사람이 하나 나올 때마다 1씩 증가시켜 준다.

여기서는 초기화할 때 미리 1로 초기화해서 출력할 때 그대로 출력하면 된다.

//비교
        for(int i=0;i<N;i++){
            int rank = 1;
            for(int j=0;j<N;j++){
                if(i==j) continue;
                if(isSmaller(arr[i],arr[j])){
                    rank++;
                }
            }
            sb.append(rank).append(" ");
        }

이제 StringBuilder sb를 출력하면 된다.

---

결과

위가 2차원 배열을 이용한 방법, 아래가 Man클래스를 이용한 방법이다.

생각보다 메모리, 시간 차이가 크지 않았다!