숫자 카드 게임

 

문제

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

- 카드는 행, 열로 구성되어 있다.

- 찾는 순서는 행선택,  그 행에서 가장 숫자가 낮은 카드를 뽑는다.

- 행을 선택할때 해당 행에서 가장 낮은 숫자를 뽑는 구조인데 이를 고려해, 행마다 가장 낮은 숫자 중 가장 높은 숫자를 뽑도록 해야한다.

- 용량 : 128MB, 시간 : 1초

 - 1 <= N,M <= 100

- 1 <= 숫자 <= 10000

 

입력 예시

3 3 (행, 열)

3 1 2

4 1 4

2 2 2

 

출력예시

2

 

 

해결

유형 파악

- "가장 높은"이 들어가므로 그리디 알고리즘을 의심한다.

- 또한 이는 다른 알고리즘으로 해결이 불가능해 보인다.

 

아이디어

- 행마다 가장 작은 수를 고르고 그 중 가장 큰 수를 찾는다

 

정당성

- 직관적이므로 굳이 체크안해도 될 것 같다.

 

구현

- 행마다 입력을 받을때마다 제일 작은 수를 리스트에 넣어 놓는다. 문제의 용량이 128MB이기 때문에 용량을 좀 써도 된다.

- 그 중 가장 큰 수를 출력

 

코드

import time
n, m = map(int, input("입력 : ").split())
data = []
result = []
for i in range(n):
    data.append(list(map(int, input("입력 : ").split())))
    result.append(min(data[i]))

start_time = time.time()
print(max(result))
end_time = time.time()
print("time : ", end_time - start_time)

 

 

용량 체크

- 데이터를 담을 리스트는 Int가 4바이트이고, N,M의 최대값이 100이므로 최대 40000바이트 차지

- 결과를 담을 리스트는 최대 400바이트 이므로 둘이 더해도 용량을 넘지 않는다.

 

시간 체크

- 시간을 고려해야할 부분은 오직 max연산 밖에 없다.

- Max, Min  시간 복잡도 : O(N)

- 전체 프로그램 시간 복잡도 : O(N)