숫자 카드 게임 ( 2019 국가 교육기관 코딩 테스트 )

1. 문제 설명

여러 개의 숫자 카드가 주어질 때, 다음 조건을 만족하면서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다.

 

     - 숫자가 쓰인 카드가 N * M 형태로 존재하며, N은 행의 개수, M은 열의 개수를 의미한다.

     - 뽑을 카드가 있는 행을 선택한다.

     - 선택된 행에 포함된 카드 중 가장 숫자가 낮은 카드를 뽑는다.

     - 여러 행을 선택 하고, 위의 조건에 따라 낮은 카드를 또 가져온다. 그 중 가장 큰 숫자의 카드를 뽑는다.

 

예를 들어,

 

3, 1, 2

4, 2, 1

5, 3, 3

 

순서의 3 * 3 형태의 카드 배열이 있다고 존재하면,

 

1 째 행은 가장 낮은 숫자의 카드는 1,

2 째 행의 가장 낮은 숫자 카드는 1,

마지막 3 째 행의 가장 낮은 숫자 카드는 3 이다.

 

여기서 가장 큰 숫자의 카드를 뽑으면 3을 뽑게 된다.

 

해당 조건을 만족하면서, 가장 큰 숫자의 카드를 뽑을 수 있도록 알고리즘을 구현하면 된다.

2. 문제 해결

각 행마다 가장 작은 수를 찾은 뒤, 그 수 중에서 가장 큰 수를 뽑으면 되는 Greedy 알고리즘 문제 중 하나이다.

이중 반복문을 통해 각 행에서 가장 작은 수를 찾은 뒤, 그 수 중에서 가장 큰 수를 뽑으면 된다.

 

각 배열의 원소를 돌면서 비교를 해도 되지만, 이 경우는 시간 복잡도를 만족하지 못하므로, min() 함수를 이용할 수 있도록 구현해본다.

 

코드를 구현하면 다음과 같다.

각 행에 가장 작은 숫자의 카드를 뽑으면서, 이전에 뽑혔던 res 변수에 저장된 값과 비교해서 클 경우 res 변수를 갱신한다.

 

3. 느낀 점

구현 자체는 어렵지 않으나, 다양한 Python의 내장 라이브러리, 함수를 잘 적용하는 데에 어려움을 느꼈다. 잘 공부하여 익숙해지도록 노력하자.