[Algorithm] 그리디 알고리즘 문제 풀이 - 숫자 카드 게임

'이것이 취업을 위한 코딩 테스트다 with 파이썬' 이라는 책을 공부 중입니다. 이 글은 해당 책에서 그리디 알고리즘 문제 중 ' 숫자 카드 게임' 문제와 풀이를 설명합니다.

문제

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

1. 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.

2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.

3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.

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

 

여기서 카드를 고를 때 첫 번째 혹은 두 번째 행을 선택하는 경우, 최적적으로 뽑는 카드는 1이다. 하지만 세 번째 행을 선택하는 경우 최종적으로 뽑는 카드는 2이다. 따라서 이 예제에서 세 번째 행을 선택하여 숫자 2가 쓰여진 카드를 뽑는 것이 정답이다. 

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

 

🎁입력 조건

 

첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1 <= N, M <= 100)

둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어짐 각 숫자는 1이상 10000이하의 자연수이다.

🎊출력 조건

 

첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

 

🎁입력 예시1

3 3

3 1 2

4 1 4

2 2 2

 

🎊출력 예시1

2

 

🎁입력 예시2

2 4

7 3 1 8

3 3 3 4

 

🎊출력 예시2

3

 

문제 해설

문제를 해결하기 위한 아디이어는 ‘각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수’를 찾는 것이다.

 

내가 작성한 자바 코드

 

import java.util.Scanner;

public class 숫자카드게임 {

   public static void main(String[] args){

       Scanner scanner = new Scanner(System.in);
       int N = scanner.nextInt(); // 열 개수 1과 100 사이
       int M = scanner.nextInt(); // 행 개수 1과 100 사이

       //카드 숫자 입력
       int [][] cards = new int[N][M];
       for(int i=0;i<N;i++)
           for(int j=0; j<M;j++){
               cards[i][j] = scanner.nextInt();

           }

	   scanner.close();

       int largestNum = 0;  // 결과 저장(각 행에서 가장 작은 숫자 중 가장 큰 숫자)
       int selectedNum = 0; // 각 행에서 가장 작은 숫자 저장

       for(int i=0;i<N;i++) {
           for (int j = 0; j < M; j++) {
               if(j == 0){ // 각 행의 첫 열의 숫자는 무조건 저장
                   selectedNum = cards[i][j];
               }else if (selectedNum > cards[i][j]){ // 첫 열 이후 더 작은 숫자가 나오면 저장
                   selectedNum = cards[i][j];
               }
           }



           // 현재 행의 가장 작은 숫자가 이전 행 들의 가장 작은 숫자 보다 크면 저장
           
           if(largestNum < selectedNum) {
               largestNum = selectedNum;
           }
       }

       System.out.println(largestNum); // 결과 출력

   }
}

 

저자 풀이

github.com/ndb796/python-for-coding-test/blob/master/3/4.java