알고리즘 그리디 - 숫자 카드게임(java)

문제 : 여러개의 카드 중에서 가장 높은 숫자가 쓰인 카드 한장을 뽑아야한다.!!!

       

    조건: 카드들이 N X M형태로 있다. N은 행이고 M은 열이다.

             먼저 행을 선택하고 해당 행에 카드들 중 가장 숫자가 낮은 카드를 뽑아야한다.

 

예시

            3  1  2

            4  1  4

            2  2  2

        라고 한다면 세 번째 행을 선택하는 것이 옳다.

 

해결방안 : 각 행 중의 작은 숫자들 중 그나마 큰 숫자를 골라야한다.

                  1. 첫번째 행의 작은 숫자와 두번째 행의 작은 숫자 비교 -> 반복 그 중 큰 수 출력

                  2. 입력받을 때 아예 이중배열로 받기 첫 번째 인덱스와 두 번째 인덱스 비교 -> 반복

//풀이방법
//1. N행과 M열을 입력받아야한다.
//2. N행M열에 해당하는 숫자를 입력받아야한다(2차원배열)
//3. 1)각 행별로 최소값을 뽑아 배열에 저장 후   그 중 최대값을 도출.
//3. 2)처음부터시작해서 끝까지 최소값을 비교하면서 가는방향
//  1)은 2번작업해야하므로 시간이 더 걸릴것으로 예측되어 2로 진행

 

코드 1방안.

Scanner scanner = new Scanner(System.in);

int N = scanner.nextInt();
int M = scanner.nextInt();
//        for (int i=0;i<N;i++) { //행
//            int min_number=100001; //최소값
//            for(int j=0;j<M ;j++){ //열. 열 중에 가장 작은 값을 구한다.
//                int input = scanner.nextInt();
//                min_number = Math.min(min_number,input);
//            }
//            //System.out.println(min_number);
//            result = Math.max(result,min_number); //결과값은 result의값(기존 행의 가장작은값) vs(min_number 새로운 행의 가장 작은값) 중에서 결정.
//            //result의 값이 사실상 최대값임.
//
//        }
//        System.out.println(result);
    }

 

코드 2방안

 Scanner input = new Scanner(System.in);
        int N = input.nextInt(); //N행
        int M = input.nextInt();//M열
        int[][] arr = new int[N][M];// 숫자를 저장할 배열

        for(int i=0;i<N;i++){  //2중배열에다가 숫자를 받기
            for(int j=0;j<N;j++){
                arr[i][j] = input.nextInt();
            }
        }

        int result_num = 0; //결과값

        for(int i=0; i<N; i++) {
            int min_number = arr[i][0]; //새로운 행의 첫값을 최소값으로 일단시작
            for (int j=0; j<N; j++) {
                if(min_number >= arr[i][j]){
                    min_number = arr[i][j]; //해당 행의 최소숫자가 더 크면 해당 행렬의 최소숫자로변환
                }
            }
            //여기까지오면 해당 행의 최소숫자가 min_number일것임.
            //그러면 이제 min_number을 다른행의 최소값과 비교해야함
            if(result_num <=min_number) {
                result_num = min_number; //최종값을 더 큰숫자로 변환
            }
        }
        System.out.println(result_num);