Greedy : 숫자 카드 게임
문제
문제 정의
- 숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임 이다.
- 단, 아래 규칙을 지키며 카드를 뽑아야 한다.
- 게임 규칙
- 숫자가 쓰인 카드들이 N * M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.
- 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
- 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
- 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.
- 예시
-
3 * 3 형태로 카드들이 놓여있다고 가정하자. 즉, N=3, M=3 이다.
3 1 2 4 1 4 2 2 2 - 여기서 카드를 골라낼 행을 고를 때 첫 번째 혹은 두 번째 행을 선택하는 경우, 최종적으로 뽑는 카드는 1이다.
- 하지만 세번째 행을 선택하는 경우, 최종적으로 뽑는 카드는 2이다.
- 따라서 세 번째 행을 선택하여 숫자 2가 쓰여진 카드를 뽑는 것이 정답이다.
게임 규칙에 따라 카드를 뽑을 때, 가장 큰 수를 뽑아야 하므로
-
입력조건
- 첫째줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 주어지고, 각 수는 공백으로 구분된다.
- N: 1 이상
- M: 100 이하
- 둘째줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다.
- 각 카드의 수: 1 이상, 10000 이하
출력조건
- 첫째줄에 게임의 규칙에 맞게 선택한 카드에 적힌 숫자를 출력한다.
입·출력 예시
- 입력
3 3 3 1 2 4 1 4 2 2 2 - 출력
2
풀이
문제 해설
- 각 행마다 가장 작은 숫자를 뽑아내고, 그 중 가장 큰 숫자를 출력하면 해결되는 단순한 문제이다.
소스코드
public class 숫자_카드_게임 {
public static int solution1(int n, int m, int[][] arr) {
int answer = 0;
int temp = 0;
for (int i = 0; i < n; i++) {
temp = Arrays.stream(arr[i]).min().getAsInt();
// Arrays.sort(arr[i]);
// temp = arr[i][0];
if (answer < temp) {
answer = temp;
}
}
return answer;
}
}
시간복잡도
solution1의 경우- 각 행별로 가장 작은 수 구하기
- 방법1:
Arrays.sort()메서드를 사용하여, 배열 중 가장 작은 원소의 값을 구하기- 이때 시간복잡도는
O(mlogm)이다.
- 이때 시간복잡도는
- 방법2:
IntStream에서 제공하는min()메서드를 사용하여, 배열 중 가장 작은 원소의 값을 구하기- 방법1과 성능상 큰 차이는 없다.
- 방법1:
- 정답 구하기
- 행(n)마다 최소값을 비교하여, 그 중 가장 큰 수를 출력한다.
- 이때 시간복잡도는
O(n)이다.
- 따라서 총 시간복잡도는
O(n) + O(mlogm)이다. - 이때 m은 100 이하이므로, 시간복잡도는
O(n)이라고 말할 수 있다.
- 각 행별로 가장 작은 수 구하기
- 나동빈, 『이것이 코딩 테스트다』