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

문제 설명

• 숫자 카드가 NxM개 존재. 
• 뽑을 카드가 있는 행에서 카드를 한장 선택
• 뽑은 카드는 해당 행에서 가장 작은 수를 가진 카드여야 함
• 최종적으로 가장 높은 수를 뽑는 사람이 이기는 게임

문제 조건

• 첫째줄에 행의 개수 N과 열의 개수 M이 주어지며, 각 자연수는 공백으로 구분한다. (1 ≤ N, M ≤ 100)
• 둘째부터 N개의 줄에 걸쳐 카드의 적힌 숫자가 주어진다. 각 숫자는 1부터 10000까지의 자연수이다.

입력 예시

• 3 3
• 3 1 2
• 4 1 4
• 2 2 2

• 출력 : 2

NxM 배열 형태로 놓여있는 카드들을 각 행별로 하나씩 골라 가장 큰 수를 찾는 문제이다. 단, 각 행에서 가장 작은 수를 골라야 한다. 

• 아이디어 : 각 행별로 최솟값들을 모은 뒤, 그 중에서 최댓값을 구함
• 최솟값 = Math.min()
• 최댓값 = Math.max

나의 답안

입력값이 주어진다는게 내가 직접 입력을 해야 한다는 것인지 몰랐다. 따라서 입력 과정까지 처리할 예정이다.

let answer = 0
let [n, m] = prompt().split(" ")
//n행 m열을 입력받아 공백을 기준으로 나눔
let minArr = []
//각 행의 최솟값을 담을 배열 생성
for (let i = 0; i < n; i++) {
    //행의 개수(n만큼 반복)
    let input = prompt()
    //prompt : i번째 행의 카드들을 입력
    let min = Math.min(...input.split(" ").map(a => Number(a)))
    //Math.min() : 배열의 최솟값을 뽑아냄
    //split(" ") : 공백 기준으로 문자열을 배열로 만듬
    //map(a => Number(a)) : 최솟값을 구할 수 있게 배열을 정수로 만듬
    minArr.push(min)
    //행의 최솟값을 minArr 배열에 넣음
}
answer = Math.max(...minArr)
//minArr 배열의 최댓값 구하기

실행 결과

정당성

뽑은 수는 각 행에서 가장 작은 수들이고, 그 중에서 최댓값을 고르는 것이므로 딱히 반례가 존재할 수가 없다.