[이코테 with Java] 숫자 카드 게임(그리디 알고리즘)

이 문제를 한 마디로 정의하자면, 각 줄마다 가장 작은 수를 찾고, 그 작은 수들 중에서 가장 큰 수를 찾는 것이다. 

첫 번째 행에는 N(행의 수), M(열의 수)를 입력받는다.

그리고 해당 행의 수만큼 숫자들(열의 수만큼의)을 입력받는다. 

 

---

예를 들어보겠다. 

3 3 
3 1 2 
4 1 4 
2 2 2

 

이렇게 입력이 들어왔다면,

첫 번째 행인 3 1 2 중에서 가장 작은 수인 1과,

두 번째 행인 4 1 4 중에서 가장 작은 수인 1과,

마지막 행인 2 2 2 중에서 가장 작은 수인 2를 비교해 가장 큰 수인 2를 출력하는 것이다.

 

1. 내가 푼 풀이

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
        
        int[] arr = new int[a];
        int[] arr2 = new int[b];
        for( int i=0 ; i<b ; i++){
            for( int j=0 ; j<a ; j++){
                arr[j] = scanner.nextInt();
            }
            Arrays.sort(arr);
            arr2[i] = arr[0];
          
        }
        Arrays.sort(arr2);
        System.out.print(arr2[b-1]);
    }
}

 

우선 내가 푼 방식을 설명해보겠다.

나는 사용자가 입력한 값을 넣을 배열과, 가장 작은 값들을 모아줄 배열을 선언했다.

그리고 a(열의 수)만큼 값을 입력받고, 정렬을 한 다음 가장 작은 수(첫 번째 인덱스의 값)을 작은 수 배열에 넣어준다. 

이 과정을 b(행의 수)만큼 반복한 후에 작은 수 배열을 정렬하여, arr2[b-1](가장 큰 수, 배열은 0부터 시작하기 때문에 -1을 해줬음)을 출력해준다. 

 

2. 동빈님이 푼 방식

import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);

        // N, M을 공백을 기준으로 구분하여 입력 받기
        int n = sc.nextInt();
        int m = sc.nextInt();
        int result = 0;

        //한 줄씩 입력 받아 확인하기
        for(int i = 0; i < n; i++){
            // 현재 줄에서 '가장 작은 수' 찾기
            int min_value = 10001;
            for(int j = 0; j < m; j++){
                int x = sc.nextInt();
                min_value = Math.min(min_value, x);
            }
            // '가장 작은 수'들 중에서 가장 큰 수 찾기
            result = Math.max(result, min_value);
        }

        System.out.println(result); // 최종 답안 출력 
    }
}

 

나와 동빈님이 푼 방식의 차이 중 가장 큰 것은 바로 '배열 선언 유무'이다.

동빈님은 최대 10,000이라는 숫자까지 입력할 수 있기 때문에 min_value에 10001(10000보다 큰 값)을 넣어주고, 입력받은 값들과 min_value를 비교해 더 작은 수를 min_value에 넣어줬다.

 

그리고 마지막에는 result(0이 들어가있음, 1부터 입력할 수 있기 때문에 항상 작음)에 더 큰 수를 넣어주었다. 

 

배열을 선언하지 않아 공간 복잡도를 줄여주었다.