[이코테 - 그리디 알고리즘] 숫자 카드 게임

숫자 카드 게임 문제는 2019 국가 교육기관 코딩 테스트 기출문제라고 한다. 사실 그게 중요한 건 아니니까 넘기고, 문제를 설명하도록 하겠다.

 

문제 설명

숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 이 게임에서는 숫자가 쓰인 카드들이 N x M 형태로 놓여있다. 여기서 N은 행이고, M은 열이다. 우선 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택하고, 선택된 행에서 가장 숫자가 낮은 카드를 뽑아야 한다. 따라서 처음에 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다. 입력조건 첫 째 줄은 N과 M의 입력조건(1 <= N, M <= 100)이고, 둘 째 줄부터는 N개의 줄에 걸쳐서 각 카드에 적힌 1이상 10,000 이하의 자연수가 주어진다. 출력 조건은 선택한 카드에 적힌 숫자이다.

 

문제 해결 아이디어

처음에 이게 무슨 말인가 고민을 했었다. 하지만 문제의 예시를 보니 이해가 갔다. 이 글을 읽는 분들도 이해할 수 있도록 문제 예시를 적어보겠다.

입력 예시 1	출력 예시 1
3 3 3 1 2 4 1 4 2 2 2	2

입력 예시 2	출력 예시 2
2 4 7 3 1 8 3 3 3 4	3

문제와 예시를 보면서 떠오른 아이디어는 각 2차원 리스트(배열)을 만들고, 각 행에서 가장 작은 숫자를 고르고, 그 숫자끼리 비교해서 가장 큰 수를 내는 것이다. 즉, 예시 1번을 보면 1, 1, 2를 비교해서 2를 출력하고, 예시 2번을 보면 1과 3을 비교해서 3을 출력한다.

 

내가 푼 소스코드

n, m = map(int, input().split())

array = []
Minimal = [100] * n
for i in range(n):
    array.append(map(int, input().split()))

for i in range(n):
    Minimal[i] = min(array[i])

print(max(Minimal))

 

책의 문제 풀이 방법

# N, M을 공백을 기준으로 구분하여 입력 받기
n, m = map(int, input().split())

result = 0
# 한 줄씩 입력 받아 확인하기
for i in range(n):
    data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = 10001
    for a in data:
        min_value = min(min_value, a)
    # '가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)

print(result) # 최종 답안 출력

책의 문제 풀이 방법은 나랑 살짝 다른 것 같으면서도 아이디어 자체는 같은 것 같다는 생각이 들었다. 이번 문제는 좋은 방법으로 접근 한 것 같다.