[그리디] 숫자 카드 게임

[문제]

 

- m x n 의 2차행렬의 숫자카드가 주어진다.

- 각 행마다 가장 작은숫자를 뽑는다

- 뽑은 작은숫자중에서 가장 큰 숫자를 뽑는다.

 

3 1 2

4 1 4

2 2 2

 

숫자카드에서는 1 / 1 / 2 중에 2가 뽑히게된다.  

 

[코드] 

n=3
m=3
map = [
  [3, 1, 2], 
  [4, 1, 4], 
  [2, 2, 2]
]
result = 0

for i in range(m):
  min_value = min(map[i])
  result = max(result, min_value)

print(result)

[해설]

- 단순하게 배열을 하나씩 탐색하면서 풀어간다.

- min() 함수는 인자에있는 값중 가장 작은값을 리턴한다.

- 배열의 1열, 2열, 3열 ... 을 하나씩 탐색하면서 최소값 min_value 를 정한다.

- min_value 중에 가장 큰값을 max 로 획득한다.

- 시간복잡도는 행의 갯수 O(n) 이 된다.

 

 

[코드2]

n=3
m=3
map = [
  [3, 1, 2], 
  [4, 1, 4], 
  [2, 2, 2]
]
result = 0

for i in range(n):
  min_value = 99999
  for j in map[i]:
    # map[i] 행의 최솟값이 min_value 로 저장
    min_value = min(min_value, j)  
  result = max(result, min_value)

print(result)

[해설2]

- 이 역시 단순하게 배열을 하나씩 탐색했다.

- min 함수를 사용해버리기보단, 특정 배열의 열을 모두 탐색하여 min_value 를 정한다.

- 그리고 행마다 존재하는 min_value 중에 가장 큰 max 를 result 로 저장한다.