카운팅 정렬 | 1221. [S/W 문제해결 기본] 5일차 - GNS

문제

SW Expert Academy

 

숫자 체계가 "ZRO", "ONE", "TWO", "THR", "FOR", "FIV", "SIX", "SVN", "EGT", "NIN" 일 때

이 단어들이 섞여 있는 문자열을 받아 작은 수부터 차례로 정렬하여 출력하는 프로그램을 작성하라.

 

"TWO NIN TWO TWO FIV FOR"  ==>  "TWO TWO TWO FOR FIV NIN"

 

입력

• 첫 줄: 테스트 케이스의 개수
• 둘째 줄: #기호와 함께 테스틐 케이스의 번호와 테스트 케이스 길이
• 셋째 줄: 테스트 케이스

10
#1 7041
SVN FOR ZRO NIN FOR EGT EGT TWO FOR FIV FIV ONE SVN ...

 

출력

 

• #테스트 케이스의 번호 공백 문자 후 정렬된 문자열을 출력

#1
ZRO ZRO ZRO ZRO ZRO ZRO ZRO TWO TWO TWO FOR FIV ...

 

풀이

 

(처음 풀이)

N = int(input().strip())

c = ["ZRO", "ONE", "TWO", "THR", "FOR", "FIV", "SIX", "SVN", "EGT", "NIN"]
for _ in range(N):
    case_num, cnt = input().split()
    words = input().split()
    sorted_words = sorted(words, key = lambda k: c.index(k))
    print(case_num)
    print(sorted_words)

 

처음에는 정렬을 이용해 c의 순서대로 입력받은 배열을 정렬했다.

 

(최종 풀이)

N = int(input().strip())
c = ["ZRO", "ONE", "TWO", "THR", "FOR", "FIV", "SIX", "SVN", "EGT", "NIN"]

for _ in range(N):
    dic = {c[i]:0 for i in range(10)}
    case_num, cnt = input().split()
    words = input().split()

    for word in words:
        dic[word] += 1

    result = []
    for word in c:
        result.append((word + " ")*dic[word])
    print(case_num)
    print(" ".join(result))

 

카운팅 정렬을 이용하여 다시 푼 코드.

1. c의 각 요소들을 key로 하는 딕셔너리를 생성하고

2. 입력받은 배열에서 개수를 세서 딕셔너리의 value에 업데이트한다.

3. value만큼 반복하여 각 요소를 출력한다.

 

 

최종 풀이가 코드 길이는 길지만 실행시간과 메모리 사용량 모두 줄일 수 있다.