SWEA - 숫자 카드 [Python]

 문제

 

https://swexpertacademy.com/main/

SW Expert Academy

 

 문제 상황

 

- 0에서 9까지 숫자가 적힌 N장의 카드가 주어진다. 가장 많은 카드에 적힌 숫자와 카드가 몇 장인지 출력하는 프로그램을 만드시오. 카드 장수가 같을 때는 적힌 숫자가 큰 쪽을 출력한다.

 

 

 해결 전략

 

- 0<=Ai<=9 이므로 길이 10인 리스트를 만들어 counting sort처럼 값을 갱신하면서 최대값을 찾는다.

 

 

 코드

 

T = int(input())
result = []
 
# 새로운 코드
# for문 안에서 추가적인 N 이상의 연산이 없으므로 O(N)의 속도가 된다.
for _ in range(T):
    counter = [0] * 10
    N = int(input())
    card_list = list(map(int, list(input())))
    mx = -1
    mxidx = -1
    for i in range(N):
        # 카운터의 개수 늘리기
        counter[card_list[i]] += 1
        # 카드 개수가 최대값으로 같을 경우 더 큰 숫자를 뽑기 위해 저장
        if counter[card_list[i]] == mx and card_list[i] > mxidx:
            mxidx = card_list[i]
        # 갱신된 카드 수가 더 크면 mx 갱신
        if counter[card_list[i]] > mx:
            mx = counter[card_list[i]]
            mxidx = card_list[i]
    result.append((mxidx, mx))
 
for i in range(T):
    print(f"#{i+1} {result[i][0]} {result[i][1]}")
 
 
 
# 예전 코드
 
# for문 안에 또 count를 사용하여 O(n^2)의 시간이 걸린다.
# 속도를 고려하지 않고 편하게 작성한 코드
 
# for i in range(t):
#     n = int(input()) # 카드 수
#     nlist = list(map(int, input())) # 카드 종류
#     nset = sorted(list(set(nlist))) # 중복 제거
#     cnt = 0 # 최대 카드 수
#     card = 0 # 최대개수 카드 번호
#     for j in range(len(nset)):    
#         if nlist.count(nset[j]) >= cnt :
#             card = nset[j]
#             cnt = nlist.count(nset[j])
#     print("#{} {} {}".format(i+1, card, cnt))
 
 

 

 

 해설

 

- for문으로 선형적으로 탐색하며 각각 O(1)인 검사만 시행하므로 속도가 훨씬 빠르다.

 

- 기존의 코드의 경우 더 짧고 편하게 코딩할 수 있지만 만약 범위가 커지면 속도 차이가 커진다.

 

 새로 학습한 것 & 실수 

 

- 빅오(O())를 생각하는 습관을 들여야 한다.

 

 

출처 - https://swexpertacademy.com/main/