#50. Algorithm50_python) 그리디 문제2_숫자 카드 게임

<그리디 : 당장 좋은 것만 선택하는 알고리즘>

문제) 숫자 카드 게임

- 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임

    1. 숫자가 쓰인 카드들이 N x M 형태로 놓여 있다. 이때 N은 행의 개수를 의미하며, M은 열의 개수를 의미한다.

    2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.

    3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.

    4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다.

 

입력)

- 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1 ≤ N, M ≤ 100)

- 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.

 

출력)

- 첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

 

 

 

문제 출처) 이것이 취업을 위한 코딩 테스트다 with 파이썬(나동빈, 한빛미디어) p96

 

---

 

 

 

---

 

Step1) 테스트 : 이중 리스트 입력

n, m = map(int, input().split())
data = []
for i in range(n):
    data.append(list(map(int, input().split())))

print(data)

print(data[0])

>>>
2 2
34 3
3 1
[[34, 3], [3, 1]]
[34, 3]

 

Step2) 성공

n, m = map(int, input().split())   # n, m 입력
data = []                          # 데이터 받을 빈 리스트

# 데이터 입력 : 이중 리스트
for i in range(n):                 
    data.append(list(map(int, input().split())))

# 정답으로 출력할 변수 max
answer = min(data[0])

for i in range(1, n):        # data[1]서부터 data[n-1]까지 반복
    # 최대값 로직
    if answer < min(data[i]):
        answer = min(data[i])

print(answer)


>>>
2 2
5 2
6 9
6

 

교재 답안1) min() 함수 이용

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

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

print(result) # 최종 답안 출력

 

교재 답안2) 2중 반복문 이용

# 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) # 최종 답안 출력

 

---

# 배운 점

• 이중 리스트 데이터 입력
• 입력 받는 동시에 로직을 돌리면서 정답 출력하는 방법(교재 답안)

# 소회

• 쉬운 문제라 해결(오랜만에ㅜㅠ)
• 여전히 '그리디 알고리즘'의 정체성을 잘 모르겠음...
  • 그냥 정규화된 로직 없이 고민해서 푸는 문제로 이해하려고 함

---

<참조>

• 이것이 취업을 위한 코딩 테스트다 with 파이썬(나동빈, 한빛미디어)