BAEKJOON 7568번 덩치🙈

👸🏻 덩치문제와 함께 돌아왔습니다^^

덩치문제는 백준의 7568번의 문제로 완전탐색과 관련된 문제입니다.

🤷🏻‍♀️ 완전탐색? 그게뭔데? what?

📌 완전탐색이란? '모든 경우의 수를 전부 찾아서 답을 찾는 알고리즘' 을 뜻한다. 영어로는 Exhaustive Search 라고 한다. 가능한 모든 경우의 수를 다 해보는 것이다. 알고리즘을 풀때 가장 강력하고 확실한 방법이지만 그만큼 시간이 가장 오래 걸리는 탐색 기법이다.

완전탐색 기법의 종류

• Brute Force : for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법
• 비트 마스크 : 이진수 표현을 자료구조로 쓰는 기법 (AND, OR, XOR, SHIFT, NOT)
• 재귀 함수
• 순열 : 서로 다른 n개의 원소에서 r개의 중복을 허용하지 않고 순서대로 늘어 놓은 수
• BFS(너비우선탐색), DFS(깊이우선탐색)
  
  위의 사진은 맨 마지막 방법인 DFS / BFS의 사진이며 이를 이해하기 위해선 재귀함수를 알아야 한다. 이는 다음문제 풀 때 다루어 보자! 지금 포스팅엔 완전 탐색의 이해만 해보자 🙆🏻‍♂️
  
  총 다섯개의 완전탐색의 기법이 있는데 3주차의 문제는 for문과 if문을 이용한 문제였다.

백준 링크 가기
https://www.acmicpc.net/problem/7568

위와 같은 문제이다. Scanner를 이용해 입력받은 뒤 풀이를 진행하였다. 처음 어려움을 느낀 부분은 2차 배열을 까먹어서 .... 생각하는데 10분정도 잡아먹은 것 같다... 나의 머리 금붕어 머리 🐡

Scanner를 이용해서 풀이한 코드는 다음과 같다.

Scanner를 이용한 코드 보기 👀

import java.io.IOException;
import java.util.Scanner;

public class 덩치문제_7568 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		//완전 탐색 문제 (백준-7568번)
//		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		Scanner sc = new Scanner(System.in);//scanner를이용한 문제풀이
		int cnt = sc.nextInt();
		
		int[][] person = new int[cnt][2];//cnt개수만큼 배열 생성 그 안의 배열은 키 몸무게 = 2개
		int rank[] = new int[cnt];//등수를 입력할 배열
		
		for(int i=0;i<person.length;i++) {
			person[i][0] = sc.nextInt();//몸무게
			person[i][1] = sc.nextInt();//키
			rank[i] = 1;//등수를 전부 1등이라고 선언
		}
		
		for(int i=0;i<person.length;i++) {//비교할 기준이 되는 번호
			for(int j=0;j<person.length;j++) {//비교할 대상이 되는 번호
				if(person[i][0] > person[j][0] && person[i][1] > person[j][1]) {
					rank[j]++;
				}
			}
		}
		for(int i=0;i<person.length;i++) {
			System.out.print(rank[i]+" ");
		}
	}
}

입력된 숫자만큼 **int person[][]=new int[입력받은 값만큼][2(키,몸무게)]**을 생성하였고 등수를 저장하는 배열도 따로 만들었다. for문을 이용해 몸무게와 키를 저장 & rank를 전부 1등으로 설정해주었다.

그 다음 2중 for문을 돌려 (Why🤷🏻‍♂️? 2차열 배열이니까~) 비교 기준과 대상을 비교를 해주었고, 만약 비교기준이 대상보다 몸무게랑 키가 모두 크다면 비교 대상에 rank++해주어 등수가 뒤로 밀리도록 코드를 작성했다.

백준 체점에 맞았습니다!! 를 보긴 했지만 전부 작성하고 보니 Scanner는 매우 비효율적인 것 같은 느낌... 그래서 StringBuffer를 사용해서 해봤지만 계속 런타임에러가 났다. 왠지 살펴보고 StringBuffer를 이용해서 다시 작성해봐야겠다..ㅎㅎ 다시 돌아올게용~

Buffer와 (런타임에러와) 컴백한 연재 😎

StringBuffer를 이용한 코드 보기 🧸

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

public class 덩치문제2_7569 {
	public static void main(String[] args) throws IOException {
		//완전 탐색 문제 (백준-7568번)
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int cnt = Integer.parseInt(br.readLine());
		int[][] person = new int[cnt][2];//cnt개수만큼 배열 생성 그 안의 배열은 키 몸무게 = 2개
		int rank[] = new int[cnt];//등수를 입력할 배열
		
		for(int i=0;i<person.length;i++) {
			person[i][0] = Integer.parseInt(br.readLine());//몸무게
			person[i][1] = Integer.parseInt(br.readLine());//키
			rank[i] = 1;//등수를 전부 1등이라고 선언
		}
		
		for(int i=0;i<person.length;i++) {//비교할 기준이 되는 번호
			for(int j=0;j<person.length;j++) {//비교할 대상이 되는 번호
				if(person[i][0] > person[j][0] && person[i][1] > person[j][1]) {
					rank[j]++;
				}
			}
		}
		for(int i=0;i<person.length;i++) {
			System.out.print(rank[i]+" ");
		}
	}
}

음...콘솔에는 답이 나와요..? 근데 백준이 인정을 안해줘 🤬 진짜 화가나~ ^^ 백준 뭐가 그리 까다롭니~~~ 혹시 왜 런타임 에러 나는지 알려주실 분 없나요... ㅎㅎㅎㅎㅎㅎㅎ

백준이 인정을 해줘야 비교를 하던말던 하지 ㅠㅠ 비교도 못하게 해 😥 아무튼 StringBuffer로도 풀었다..