[이.코.테] Chapter 03 그리디 - 숫자 카드 게임 (Java)

알고리즘숫자 카드 게임 문제 (교재 96p)

난이도 ●○○ | 시간 제한 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

 

문제 이해가 너무 어려웠다....

👉 처음 카드를 선택할 때 가장 높은 숫자의 카드를 뽑을 수 있도록 하며 (단, 뽑을 수 있는 숫자는 각 행의 가장 낮은 숫자), 그 높은 숫자를 출력

 => 즉, 각 행의 가장 작은 숫자 중에서 가장 큰 수를 출력

---

문제 풀이 방법

• 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 것

 

소스 코드 1

• Arrays.sort 사용

package exam03_greedy;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Q3_NumberCardGame {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int row = Integer.parseInt(st.nextToken()); // 행
        int col = Integer.parseInt(st.nextToken()); // 열
        int[][] arr = new int[row][col];

        // 배열 입력
        for (int i = 0; i < row; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < col; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 각 행 정렬
        for (int i = 0; i < row; i++) {
            Arrays.sort(arr[i]);
        }

        int max = 0;
        // 각 행의 0번 index 값과 max를 비교하여 최댓값 구하기
        for (int i = 0; i < row; i++) {
            if(arr[i][0] > max)
                max = arr[i][0];
        }

        bw.write(max+"\n");

        br.close();
        bw.close();
    }
}

 

 

소스코드 2

• 행 원소를 하나씩 다 보면서 그중에 최소값 구하기

package exam03_greedy;

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Q3_NumberCardGame2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int row = Integer.parseInt(st.nextToken()); // 행
        int col = Integer.parseInt(st.nextToken()); // 열
        int[][] arr = new int[row][col];

        // 배열 입력
        for (int i = 0; i < row; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < col; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // 각 행에서 최솟값 min 배열에 저장
        int[] min = new int[row];
        for (int i = 0; i < row; i++) {
            min[i] = arr[i][0];
            for (int j = 1; j < col; j++) {
                if(arr[i][j] < min[i])
                    min[i] = arr[i][j];
            }
        }

        int max = 0;
        // 구해진 min 배열에서 최댓값 구하기
        for (int i = 0; i < row; i++) {
            if(min[i] > max)
                max = min[i];
        }

        bw.write(max+"\n");

        br.close();
        bw.close();
    }
}