[백준] 7568번 : 덩치 - JAVA[자바] - 브루트포스 - 티스토리

오늘의 토픽 : 브루트포스(완전탐색)

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

7568번: 덩치

 

문제 

입력 및 출력

---

---

*별표가 들어간게 저의 생각이고, 나머지는 문제에서 인용한 부분입니다.

 

*몸무게를 일일히 다 비교해야한다 -> 다 돌면서 확인해야함 -> 브루트 포스구나

*브루트포스를 사용하기 전에, 사용해도 되는지 먼저 연산횟수를 확인해보자.

N의 크기가 2~50까지

*1명당 최대 50까지 반복문을 돈다고 하더라도, 50*50이 최대이기에 연산횟수가 적다. 

 

*핵심 : 키, 몸무게 둘 다 커야지 몸집이 큰거라고 할 수 있다.

*주의 : 1. 같은 경우도 안되고 2. 몸무게,키 중 1가지만 커도 안된다.

---> 한 명씩 돌면서 둘 다(키, 몸무게) 큰 학생만 골라내면 되겠다.

 

풀이방법,

1. class 사용하는 방법을 익히고 싶어서 저는 Student클래스를 만들어서 사용했습니다.

2. 2차원배열을 이용해서 푼 사람이 대부분이긴해서 풀어보았습니다. 

 

 

Student클래스

(멤버변수 총 3개)

1. 몸무게 

2. 키 

3. 순위

일부러 멤버변수에 private을 사용해서 직접접근하지않고, get,set메소드를 사용해서 접근하는 것이 좋은 방법입니다.

풀이 1

/* 작성 : 21.07.05 
 * 
 * 
 * 
 * 어차피 다 돌면서 확인을 해야함 -> 브루트포스
 * 얼마나 돌아야함? -> 2<= N <= 50 -> 크기 안커서 브루트포스 가능 
 * 
 * 정렬하고 확인하면 빠르겠다.(잘못된 아이디어)
 * 마지막 출력은 각 학생들의 등수를 출력을 해야한다. 같은 속성이 여러개니 배열로 처리하자.
 *  
 * 핵심 : 키, 몸무게 둘 다 커야지 몸집이 큰거임.(같은 경우도 안됨)    
 * 
 * 원래 내 생각 (실패) 
 * 1.모든 학생이 몇명보다 높은지 갯수를 일일히 다 센다 .
 * 2.이후에 등수를 센다. (근데 여기서 막힘..)
 *  
 * 몰랐던 아이디어 (성공) 
 * 1. 모든 학생들 순위를 모두 1로 초기화한뒤, 비교해서 작은 놈한테 순위를 ++해준다. 
 * 그러면, 한 번에 끝남. 
 *  
 * 
 */
package bruteforce;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class BOJ_7568_clear {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		Student[] students = new Student[n];
		
		
		for(int i=0 ; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int weight = Integer.parseInt(st.nextToken());
			int height = Integer.parseInt(st.nextToken());
			students[i] = new Student(weight,height);			
		}
		
		for(int i=0 ; i<n ;i++) {
			for(int j=0 ;j<n; j++){
				if( j==i || students[i].getWeight() == students[j].getWeight()) continue; 
				//***기준 i 가 j보다 크다고 판정이되면, j의 숫자를 올려줌.*** 이런 생각을 못했음..  				
				if(students[i].getWeight() > students[j].getWeight() && students[i].getHeight() > students[j].getHeight()) {
					int rank = students[j].getRank();
					students[j].setRank(rank+1);  
				}
			}			
		}
		
		for(Student st : students)
			bw.write(st.getRank()+" ");
		
		bw.flush();
		bw.close();
		br.close();
	

	}
	

}
class Student{
	private int weight;
	private int height;
	private int rank;
	public Student(int weight, int height) {
		this.weight = weight;
		this.height = height;	
		this.rank = 1;
	}
	public int getWeight() {
		return this.weight;
	}
	public int getHeight() {
		return this.height;
	}
	public int getRank() {
		return this.rank;
	}
	public int setRank(int rank) {
		return this.rank = rank;
	}
	public int setHeight(int height) {
		return this.height = height;		//여기서는 필요없음 .
	}
	public int settWeight(int weight) {
		return this.weight = weight;		//여기서는 필요없음 .
	}
	
}

풀이 2

이해하기 편하기 위해 배열[n][3]을 시각화해보았습니다. 

배열[n][0] = 몸무게

배열[n][1] = 키

배열[n][2] = 랭킹 

 

 

package bruteforce;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class BOJ_7568_usingArrays {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int n = Integer.parseInt(br.readLine());
		
		int[][] students = new int[n][3];
	
		
		for(int i=0 ; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int weight = Integer.parseInt(st.nextToken());
			int height = Integer.parseInt(st.nextToken());
			students[i][0] = weight;
			students[i][1] = height;
			students[i][2] = 1; //순위 모두 1로 초기화 
		}
		
		for(int i=0 ; i<n ;i++) {
			for(int j=0 ;j<n; j++){
				if( j==i || students[i][0] == students[j][0]) continue; 
				//***기준 i 가 j보다 크다고 판정이되면, j의 숫자를 올려줌.*** 이런 생각을 못했음..  				
				if(students[i][0] > students[j][0] && students[i][1] > students[j][1]){
					students[j][2] = students[j][2]+1;  
				}
			}			
		}
		for(int[] info : students)
			bw.write(info[2]+" ");
		
		bw.flush();
		bw.close();
		br.close();

	}

}

읽어주셔서 감사합니다. 

자유로운 코멘트 환영합니다!!

부족한 점도 지적해주시면 감사하겠습니다.