[그리디 3] 숫자 카드 게임
숫자 카드 게임은 여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 1장을 뽑는 게임이다. 규칙은 선택된 행 중에서 가장 숫자가 낮은 카드를 뽑아야 한다. 행에서 가장 작은 숫자를 뽑고, 그 뒤에 큰 숫자를 고르는 것이기 때문에 탐욕법 (당장 좋은 것이 좋은 것이라는 관점) 으로 풀이 가능하다. 따라서 이 문제는 그리디로 접근할 수 있다.
미니 예제 1. 숫자 카드 게임
1. 문제 설명하기.
행이 3이고, 열이 3이고, [[3,1,2], [4,1,4], [2,2,2]] 인 경우
2. 문제 풀이하기.
Step 1. 행을 기준으로 반복문 돌리면서 최소값 찾기. (행에서의 최소값 찾는 과정이다.)
Step 2. 그 값들을 리스트에 넣어주기.
Step 3. 그 리스트에서 최대값 찾기.
# 예시 1
N=3
M=3
min_list=[]
array=[[3,1,2], [4,1,4], [2,2,2]]
for row_idx in range(N):
min_val=min(array[row_idx])
min_list.append(min_val)
result=max(min_list)
print(result)미니 예제 2. 숫자 카드 게임
1. 문제 설명하기.
행이 3이고, 열이 3이고, [[7,3,1,8], [3,3,3,4]] 인 경우
2. 문제 풀이하기.
Step 1. 행을 기준으로 반복문 돌리면서 최소값 찾기. (행에서의 최소값 찾는 과정이다.)
Step 2. 그 값들을 리스트에 넣어주기.
Step 3. 그 리스트에서 최대값 찾기.
# 예시 2
N=2
M=4
min_list=[]
array=[[7,3,1,8], [3,3,3,4]]
for row_idx in range(N):
min_val=min(array[row_idx])
min_list.append(min_val)
result=max(min_list)
print(result)최적의 일반화
1. 아이디어 설명하기.
내가 풀이한 방법과는 조금 다르다. 일단 행의 개수만큼 반복문을 돌리는 것은 동일하다. 그 대신 위의 경우처럼 데이터를 받을 때 이중 리스트로 받지 않고, 행 마다 데이터를 받는 구조이다.
위의 예제로 예시를 든다면 [[3,1,2], [4,1,4], [2,2,2]] 경우에는 [3,1,2] > min > append > [4,1,4] > ... > max 의 과정을 거친다. 그리고 [[7,3,1,8], [3,3,3,4]] 인 경우도 [7,3,1,8] > min > append > ... > max 의 과정을 거친다.
| 기준 | 나의 풀이 | 최적의 풀이 |
|---|---|---|
| 데이터 받기 | 반복문 밖에서 | 반복문 내에서 |
| n(행)번 반복문 돌리기 | 인덱스(idx)로 이용하여 최소값 찾기. | 행마다 데이터 받아서 최소값 구하기. |
| 이중 리스트 생성하기 | 빈 리스트 + append 이용 | 이중 리스트를 사용 X |
2. 문제 풀이하기.
Step 1. n,m을 입력받는다.
Step 2. 행이 돌아갈 때마다 데이터의 열을 입력시키고 최소값을 찾고 min_list에 넣어준다.
Step 3. min_list에서 최대값을 찾는다.
# 일반화
n,m=map(int, input().split()) # 꼭 m을 사용할 필요가 없다.
min_list=[]
for row in range(n): # 행의 개수 만큼 데이터를 입력하기.
# 굳이 이중 리스트를 만들 필요가 없어보인다.
data=list(map(int, input().split()))
min_val=min(data)
min_list.append(min_val)
result=max(min_list)
print(result)3. 만일 이중 리스트를 만들어 데이터를 받는 경우에는?
미니 예제처럼 풀이하면 된다. append를 이용하여 빈 리스트에 추가하고 싶은 리스트를 넣어주면 된다. 그리고 행을 기준으로 반복하여 최소값을 찾고, 전체에서 최대값을 찾으면 된다.
# 이중 리스트 만들기
list_2d=[]
for row in range(n): # 행을 먼저 만들어주기.
data=list(map(int, input().split()))
# 한 개의 행에 넣어줄 데이터 생성하기.
list_2d.append(data) # 빈 행에 데이터 넣어주기.
print(list_2d) # 이중 리스트 완성된다.
n,m=map(int, input().split())
min_list=[]
for row_idx in range(n):
min_list.append(min(list_2d[row_idx]))
result=max(min_list)
print(result)