[그리디] 숫자 카드 게임

문제 설명

여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 1장을 뽑는 게임이다. 단, 주어진 게임의 룰을 지키며 카드를 뽑아야 한다.

게임 룰 : 

1. 뽑고자 하는 카드가 포함되어 있는 행을 선택함

2. 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 함

3. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 함 

 

1. 사용 알고리즘 

그리디

 

2. 문제 해결 아이디어

주어진 2차원 배열의 각 행마다 최소값을 찾고, 최소값들 중 가장 큰 값이 속한 행을 선택해 해당 값을 반환해주면 된다. 

 

3. 코드

구현방식1)

각 행을 오름차순 정렬시킨 후, 각 행의 첫 번째 원소들을 비교해서 최대값 찾기

import java.util.Scanner;
import java.util.Arrays;

public class q2 {

	public static void main(String[] args) {
		Scanner kbd = new Scanner(System.in);
		int i = 0, j = 0;
		
		//행, 열 값 입력
		int r, c;
		r = kbd.nextInt();
		c = kbd.nextInt();
		
		//2차원 배열 값 입력 
		int arr[][] = new int[r][c];
		for(i = 0; i < r; i++) 
			for(j = 0; j < c; j++)
				arr[i][j] = kbd.nextInt();
		
		for(i = 0; i < r; i++)
			Arrays.sort(arr[i]); //2차원 배열의 각 행을 오름차순 정렬하기 
		
		//각 행의 최소값들 중 최대값 찾기
		int max = 0;
		for(i = 0; i < r; i++) 
			if(max < arr[i][0]) max = arr[i][0];
		
		System.out.println(max);

	}

}

 

구현방식2)

각 행의 최소값을 찾는 함수를 사용해 최소값을 찾고, 각각을 비교하여 최대값 찾기 

import java.util.Arrays;
import java.util.Scanner;

public class q2_Stream {

	public static void main(String[] args) {
		Scanner kbd = new Scanner(System.in);
		int i = 0, j = 0;
		
		//행, 열 값 입력
		int r, c;
		r = kbd.nextInt();
		c = kbd.nextInt();
		
		//2차원 배열 값 입력 
		int arr[][] = new int[r][c];
		for(i = 0; i < r; i++) 
			for(j = 0; j < c; j++)
				arr[i][j] = kbd.nextInt();
		
		//각 행의 최소값 중 최대값 찾기 
		int max = 0;
		for(i = 0; i < r; i++) {
			int num = Arrays.stream(arr[i]).min().getAsInt(); //배열의 원소 중 최소값 찾기 
			if(num > max) max = num;
		}
			
		System.out.println(max);

	}
}

사용 메서드 :

java.util.Arrays의 stream()

java.util.stream 패키지의 IntStream 인터페이스 min() 메서드

java.util.OptinalInt 클래스의 getAsInt() 메서드

Arrays 클래스의 stream()을 사용해 스트림 형태로 만들어 준 뒤, IntStream 인터페이스의 min() 메서드로 해당 배열의 최소값을 구하고,  OptionalInt 클래스의 getAsInt() 메서드로 해당 값을 int 형태로 가져온다.

 

추가 개념 정리)

Stream 찾아보기 !!

 

 

참고

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/Arrays.html

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/stream/IntStream.html

https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/OptionalInt.html