[이코테] 숫자 카드 게임 - Python, 그리디

문제

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

게임의 룰은 다음과 같다. 

 

1. 숫자가 쓰인 카드들은 N X M 형태, 이때 N은 행의 개수, M은 열의 개수를 의미
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택
3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 함
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 함

 

카드들이 N x M 형태로 놓여있을 때, 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오. 

 

 

입력 조건

• 첫째 줄에 숫자 카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1 <= N,M <= 100)
• 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1 이상 10,000 이하의 자연수이다.

3 3 
3 1 2 
4 1 4 
2 2 2

 

출력 조건 

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

2

 

내가 푼 답안 

내가 생각해 본 이 문제의 핵심은 

1) 행을 한 줄 씩 입력받아 그 중에서 가장 작은 수를 찾기

2) 그리디 문제의 핵심인 정렬 알고리즘 이용하여 n번째로 작은 수를 찾기

 

따라서 각 행마다의 작은 수를 저장하는 리스트를 선언하여 입력받은 뒤, 해당 리스트를 정렬하여 그 중 가장 큰 수를 찾았다!

n, m = map(int, input().split())
small = []

#행 한 줄 씩 입력받기
for i in range(n):
  data = list(map(int, input().split()))
  #리스트 내에서 가장 작은수 찾기
  smallest = min(data)
  small.append(smallest)

small.sort()
result = small[n-1]

print(result)

올바른 출력 결과가 나온 것을 확인할 수 있었다.

 

정답 코드

• min(),max() 함수를 이용하는 답안

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중 for문을 사용한 답안

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

result = 0
for i in range(n):
  data = list(map(int, input().split()))
  #입력 숫자값 조건 1이상 10000이하
  min_value = 10001
  for a in data :
    min_value = min(min_value, a) # 행 내에서 가장 작은 숫자를 찾기
  # 가장 작은 수들 중 가장 큰 수 찾기
  result = max(result, min_value)

print(result)

 

느낀점

이번 문제는 min() 함수만 안다면 앞의 큰 수의 법칙 문제보다는 훨씬 쉬었던 것 같다. 

실전 코테문제에 비하면 최하하하하하하 수준의 문제지만 20분안에 풀어내서 뿌듯하다 ^^,,

예시 답안과 내 답안을 비교해보면서 느낀 점은 

첫 번째, max()함수를 쓸 생각을 못했다.. 

최소라는 단어에만 너무 초점이 맞춰져서 최소값 중 가장 큰 값 = n번째로 작은 값 이렇게 생각해서 sort()를 사용해서 풀었다. 

max()를 쓰면 코드가 훨씬 간결해지는 것을 알게되었다..!

메서드 사용에 좀 더 익숙해질 것ㅎㅎ..

두 번째, 문제의 조건을 활용해서 코드를 작성하는 것!

2중 for문 사용은 아직은 조금 생각해내기 어려운 것 같긴하다.

입력값이 10000이하라는 조건을 사용해서 코드를 작성해 볼 생각은 전혀 못했는데

이 테크닉도 잘 익혀두면 숫자 값 비교 문제에서 좋은 아이디어로 사용할 수 있을 것 같다. 

 

알고리즘 좀 재밌다 ..? (잘 풀리면⌒‿⌒)