[코딩 테스트 공부] 카드 뽑기

출처 : https://www.acmicpc.net/problem/11652

들어가기에 앞서 문제부터 분석해볼까요

우선 문제부터 분석을 해 볼 필요가 있습니다.

문제의 조건을 먼저 분석을 해보면, 시간 제한은 1초인데 비해서 N의 범위는 10만까지 주어져있습니다. 여기서 깨달아야 하는 것이, 주어진 N의 범위가 10^5이기 때문에, N^2의 복잡도를 가지게 알고리즘을 구성하면 망.한.다 입니다.

따라서 문제의 풀이를 작성할 때, 최대한 복잡도가 안 나오도록 구현을 잘해줘야합니다.

코드부터 볼까요

import sys

input = sys.stdin.readline

N = int(input())
result = {} # 입력 결과를 저장할 dict 변수

for _ in range(N):
    number = int(input()) # 입력
    if number not in result.keys(): # 기존에 입력된 정수가 아닌 경우
        result[number] = 1
    else: # 기존에 입력된 정수인 경우 -> result[number]에 1을 더한다
        result[number] = result[number] + 1
        
maxv = max(result.values()) # result에 저장된 value의 값들 중 가장 큰 값을 고른다

for key in sorted(result.keys()): # key의 리스트가 정렬된 상태에서 key를 순회한다 (작은 key값을 우선으로 골라내기 위함)
    if result[key] == maxv:
        print(key)
        break

우선, 어느 정수가 얼마만큼 담겼는지 저장을 하기 위해서 result라는 dict형 변수를 선언하였습니다.

그리고 숫자를 하나씩 입력을 받으면서 result에 변수를 할당하는 방식을 채택하였습니다.

for _ in range(N):
    number = int(input())
    if number not in result.keys():
        result[number] = 1
    else:
        result[number] = result[number] + 1

위의 코드를 분석하면, 2가지의 분기로 나뉘어졌는데, 이유는 다음과 같습니다:

• number가 한 번도 입력이 되지 않았다면, dict의 새로운 key로 number를 할당하고, result[number]에는 최초에 1을 할당한다
• number가 이미 key로 존재한다면, result[number]를 1을 증가시켜서, 가진 개수가 늘어났음을 표현합니다

입력이 모두 끝난 후에는, 가장 많은 정수가 무엇인지를 골라내야합니다. 저는 다음의 구현 방식을 채택했습니다:

• 우선, result.values()를 통해서 정수 카드들의 개수 리스트를 뽑아와서 최댓값을 고릅니다.

maxv = max(result.values())

• key를 오름차순으로 정렬하여서, 가장 큰 수를 가진 key 중에서, key가 가장 작은 경우를 출력해주고 프로세스를 종료합니다

for key in sorted(result.keys()): 
    if result[key] == maxv:
        print(key)
        break