이 영역을 누르면 첫 페이지로 이동
Stranger's LAB 블로그의 첫 페이지로 이동

Stranger's LAB

페이지 맨 위로 올라가기

Stranger's LAB

프로그래밍과 관련하여 다양한 알고리즘 문제를 풀어보고, 프로그래밍 언어를 이해해 볼 수 있도록 돕고자 만든 블로그 입니다.

[백준] 7568번 : 덩치 - JAVA [자바]

  • 2020.05.21 21:32
  • JAVA - 백준 [BAEK JOON]/브루트 포스
글 작성자: ST_
728x90






www.acmicpc.net/problem/7568

 

7568번: 덩치

우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩�

www.acmicpc.net

 








  • 문제



 

 

 

매우 간단한 문제다!

 

 

※ 주의할 점

  1. 키와 몸무게가 모두 클 때에만 '덩치가 크다' 라고 정의하고 있다.

 

 

 

 




  • 알고리즘 [접근 방법]

 

 


이번에도 역시 브루트포스를 이용하여 푸는 문제다.

 

먼저 문제를 보면 '덩치가 크다'는 기준은 키와 몸무게가 모두 비교하려는 대상보다 클 때이다.

즉, 어느 한 쪽이라도 만족 못할 경우 덩치가 크다고 할 수 없다.

 

 

그럼 브루트포스로 어떻게 풀 수 있을까?

 

 

일단 키와 몸무게를 담는 2차원 배열을 생성한 뒤,

이중 반복문을 통해 각 배열의 인덱스를 모두 탐색하는 방법이다.

 

이때 각 비교되는 두 인덱스의 각각의 키와 몸무게를 비교하여 랭크를 지정해주는 방식이다.

 

좀 더 상세하게 말하자면

rank = 1 부터 시작하여 해당 사람보다 덩치가 큰 사람이 있을 경우 해당 사람은 순위는 뒤로 밀리기 때문에 rank 값을 증가시키는 것이다.

이렇게 자기 자신을 제외한 나머지 사람들을 모두 비교하여 rank 값을 출력하면 된다.

 

만약 자기보다 덩치가 큰 사람이 없을 경우 rank 는 1 이 될 것이고, 덩치가 큰 사람이 K 명 있을 경우 rank + K 가 자신의 랭크(순위)가 될 것이다.

 

즉, 기본적인 알고리즘은 다음과 같다.

 

int[][] arr = new int[N][2]; 

// 입력
for(int i = 0; i < N; i++) {
	arr[i][0] = input();	// [i][0] : 몸무게
	arr[i][1] = input();	// [i][1] : 키
}
		
for(int i = 0; i < N; i++) {
	int rank = 1;	// 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++;
		}
	}

	// i 의 랭크값을 출력
	print(rank + " ");

}

 

 

 

 

 

 

 

 




  • 3가지 방법을 이용하여 풀이한다.

 


알고리즘은 앞서 설명 한 것을 그대로 적용 할 것이다.

다만, 입력 방법을 달리하여 Scanner 와 BufferedReader 을 사용하여 풀 것이다.

 

마지막으로 출력 부분에서 매 반복문마다 출력하는 방식이 아닌 StringBuilder 을 사용하여 하나의 문자열로 이어준 뒤, 한 번에 출력해보는 방식을 사용해보려 한다.

 

위 3가지 입출력 방법을 통해 각각의 성능을 비교해보려 한다.

 




  • 풀이




- 방법 1 

 

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {

		Scanner in = new Scanner(System.in);

		int N = in.nextInt();

		int[][] arr = new int[N][2];

		for(int i = 0; i < N; i++) {
			arr[i][0] = in.nextInt();	// [i][0] : 몸무게 
			arr[i][1] = in.nextInt();	// [i][1] : 키 
		}
		
		
		for(int i = 0; i < N; i++) {
			int rank = 1;
			
			for(int j = 0; j < N; j++) {
				if(i == j) continue;
				if (arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
					rank++;
				}
			}

			System.out.print(rank + " ");
		}

	}
}

 

 

가장 기본적인 방법이다.

 

다행이 입력되는 케이스(N)의 최대 개수가 50까지 밖에 안되기 때문에 시간초과가 날 가능성은 매우 적다.

 

 

 










- 방법 2 

 

 

Scanner 대신 BufferedReader 로 입력받는 방법이다.

필자의 다른 포스팅들을 보면 알겠지만, 기본적으로 BufferedReader 입력방식이 좋다는 것을 볼 수 있으니 참고하시길 바란다.

 

그리고 BufferedReader 의 경우 readLine() 입력메소드가 한 줄을 통째로 읽기 때문에 문자열 분리를 해주어야 한다.

이번의 경우 StringTokenizer 가 아닌 split() 메소드를 사용해보기로 한다.

 

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

public 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]);	// [i][0] : 몸무게 
			arr[i][1] = Integer.parseInt(sp[1]);	// [i][1] : 키 
		}
		
				
		for(int i = 0; i < N; i++) {
			int rank = 1;
			
			for(int j = 0; j < N; j++) {
				if(i == j) continue;
				if (arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
					rank++;
				}
			}

			System.out.print(rank + " ");
		}

	}
}

 

 








- 방법 3 

 

 

이번 문제는 워낙 케이스가 적어서 최대 출력 개수가 50개 밖에 안되기 때문에 성능이 매우 차이난다고 할 수는 없다.

그러나 다른 문제들을 풀어보면 알겠지만 출력의 반복 횟수가 많아질 수록 StringBuilder 을 통해 출력 문구들을 하나로 묶어 마지막에 한 번에 출력하는게 성능이 월등히 좋아진다.

 

(물론 StringBuilder 대신 BufferedWriter 을 사용해도 된다)

 

또한 입력방법은 직전 코드와 같이 BufferedReader 을 쓴다.

 

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

public 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[] str;
		for(int i = 0; i < N; i++) {
			str = br.readLine().split(" ");
			arr[i][0] = Integer.parseInt(str[0]);	// [i][0] : 몸무게 
			arr[i][1] = Integer.parseInt(str[1]);	// [i][1] : 키 
		}
			
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < N; i++) {
			int rank = 1;
			
			for(int j = 0; j < N; j++) {
				if(i == j) continue;
				if (arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
					rank++;
				}
			}

			sb.append(rank).append(' ');
		}
		System.out.println(sb);
	}
}

 

 

 

 

 

 

 

 

 

 

 




  • 성능



 


위에서 부터 순서대로

 

채점 번호 : 19939338  -  방법 3 : BufferedReader + StringBuilder

채점 번호 : 19939253  -  방법 2 : BufferedReader 

채점 번호 : 19939243  -  방법 1 : Scanner

 

 

입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.

출력 부분에서는 그리 차이는 안나는듯 하다.. (워낙 출력할 케이스가 적어서..)

 

 

 

 

 






  • 정리

 


이 문제는 크게 설명할 내용이 없을 정도로 매우 쉬운 문제다.

(문제 출처를 보니 초등부 문제더라...)

 

또한 브루트포스 알고리즘 자체가 완전탐색만 하면 되기 때문에 구현하는 것도 크게 어려운 부분은 없을 것이다.

불필요한 탐색을 줄이는 방법을 고민하는 것이 이번 카테고리의 가장 중요한 포인트가 될 것이다.

 

 




저작자표시 비영리 변경금지 (새창열림)

'JAVA - 백준 [BAEK JOON] > 브루트 포스' 카테고리의 다른 글

[백준] 1436번 : 영화감독 숌 - JAVA [자바]  (89) 2020.05.27
[백준] 1018번 : 체스판 다시 칠하기 - JAVA [자바]  (52) 2020.05.26
[백준] 2231번 : 분해합 - JAVA [자바]  (27) 2020.05.20
[백준] 2798번 : 블랙잭 - JAVA [자바]  (15) 2020.05.19

댓글

이 글 공유하기

  • 구독하기

    구독하기

  • 카카오톡

    카카오톡

  • 라인

    라인

  • 트위터

    트위터

  • Facebook

    Facebook

  • 카카오스토리

    카카오스토리

  • 밴드

    밴드

  • 네이버 블로그

    네이버 블로그

  • Pocket

    Pocket

  • Evernote

    Evernote

다른 글

  • [백준] 1436번 : 영화감독 숌 - JAVA [자바]

    [백준] 1436번 : 영화감독 숌 - JAVA [자바]

    2020.05.27
  • [백준] 1018번 : 체스판 다시 칠하기 - JAVA [자바]

    [백준] 1018번 : 체스판 다시 칠하기 - JAVA [자바]

    2020.05.26
  • [백준] 2231번 : 분해합 - JAVA [자바]

    [백준] 2231번 : 분해합 - JAVA [자바]

    2020.05.20
  • [백준] 2798번 : 블랙잭 - JAVA [자바]

    [백준] 2798번 : 블랙잭 - JAVA [자바]

    2020.05.19
다른 글 더 둘러보기

정보

Stranger's LAB 블로그의 첫 페이지로 이동

Stranger's LAB

  • Stranger's LAB의 첫 페이지로 이동

검색

나의 외부 링크

  • st-github

공지사항

  • 공지 - 블로그 사용 설명서

메뉴

  • 홈
  • 방명록

카테고리

  • 전체 카테고리 (267)
    • Java (5)
    • JAVA - 백준 [BAEK JOON] (177)
      • 입출력과 사칙연산 (14)
      • 조건문 (7)
      • 반복문 (11)
      • 1차원 배열 (7)
      • 함수 (3)
      • 문자열 (10)
      • 기본 수학 1 (8)
      • 기본 수학 2 (6)
      • 2차원 배열 (0)
      • 정렬 (10)
      • 재귀 (4)
      • 브루트 포스 (5)
      • 집합과 맵 (0)
      • 기하 1 (5)
      • 정수론 및 조합론 (12)
      • 백트래킹 (8)
      • 동적 계획법 1 (15)
      • 누적 합 (0)
      • 그리디 알고리즘 (5)
      • 스택 (5)
      • 큐, 덱 (7)
      • 분할 정복 (9)
      • 이분 탐색 (7)
      • 기타 문제 (17)
      • 별 찍기 문제 모음 (2)
    • C++ - 백준 [BAEK JOON] (46)
      • 입출력과 사칙연산 (14)
      • 조건문 (7)
      • 반복문 (11)
      • 1차원 배열 (7)
      • 함수 (3)
      • 문자열 (0)
      • 기타 문제 (4)
    • 자료구조 (18)
      • Java (18)
    • 알고리즘 (11)
      • Java (11)
    • 프로그래밍 기초 (6)
    • 이모저모 (2)
    • 일상의 글 (2)

최근 글

정보

ST_의 Stranger's LAB

Stranger's LAB

ST_

블로그 구독하기

  • 구독하기
  • 네이버 이웃 맺기
  • RSS 피드

방문자

  • 전체 방문자
  • 오늘
  • 어제

티스토리

  • 티스토리 홈
  • 이 블로그 관리하기
  • 글쓰기
Powered by Tistory / Kakao. Copyright © ST_.

티스토리툴바