[JAVA] 이.코.테(Greedy) - 숫자 카드 게임

난이도 ●○○ | 시간 제한 1초 | 메모리 제한 128MB | 기출 2019 국가 교육기관 코딩 테스트

 

숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 단, 게임의 룰을 지키며 카드를 뽑아야 하고 룰은 다음과 같다.

1. 숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이 때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

카드들이 N X M 형태로 놓여 있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.

 

 

입출력 조건)

입력 조건	- 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1 ≤ N, M ≤ 100) - 둘째 줄에 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.
출력 조건	첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

입출력 예시)

입력 예시	출력 예시
3 3 3 1 2 4 1 4 2 2 2	2
2 4 7 3 1 8 3 3 3 4	3

 

 

 

풀이

public class NumberCardGame {

	public static int choice(int[][] arr, int n, int m) {
		int[] rowNum = new int[n]; // 각행마다 가장 작은 숫자
		for (int i = 0; i < n; i++) {
			int min = arr[i][0];
			for (int j = 0; j < m; j++) {
				if (arr[i][j] < min) {
					min = arr[i][j];
				}
			}
			rowNum[i] = min;
		}

		int max = rowNum[0];
		for (int i = 0; i < rowNum.length; i++) {
			if (max < rowNum[i]) {  
				max = rowNum[i];    /////각 행마다 작은 숫자에서 가장 큰 수를 리턴
			}
		}
		return max;

	}

	public static void main(String[] args) {
		// int n = 2;
		// int m = 4;
		// int[][] arr = { { 7, 3, 1, 8 }, { 3, 3, 3, 4 } };
			
       ///출력 : 3     
            
		int n = 3;
		int m = 3;
		int[][] arr = { { 3, 1, 2 }, { 4, 1, 4 }, { 2, 2, 2 } };
          
        ////출력 : 2
		System.out.println(choice(arr, n, m));
	}
}

 

아이디어 : 입력을 이차원 배열로 만들고,

               2중포문을 돌려 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를  찾았습니다.