The Full Counting Sort

Problem Link
https://www.hackerrank.com/challenges/countingsort4/problem?isFullScreen=true

✅ Problem Summary

문자와 함께 주어진 인덱스(index)를 가지고 분류하여 순서대로 나열하는 문제 (전체 문자의 반절은 -로 변환하여 출력)

---

📑 My Answer

• 모든 테스트 케이스 통과

def countSort(arr):
    maxVal = max([int(i) for i, _ in arr])

    result = [[] for _ in range(maxVal+1)]
    for idx, (i, s) in enumerate(arr):
        if idx < len(arr) // 2:
            result[int(i)].append('-')
        else:
            result[int(i)].append(s)
    print(' '.join([y for x in result for y in x]))

📌 코드 구현 설명

• 주어진 인덱스(index)값 중 최댓값을 찾은 후, 최댓값 만큼의 빈 리스트가 들어있는 이중 리스트 생성
• 입력 문자가 들어 있는 배열을 차례대로 탐색하여 처음 반절은 -로 치환, 나머지는 문자열 그대로 사용
• 처음에 생성해둔 이중 리스트에서, 문자열 인덱스(index)에 해당하는 리스트에 앞 단계에서 만든 문자열을 넣어줌
• 탐색이 끝나면 이중 리스트를 분해하여 문자들을 출력

---

💼 Takeaway

• 인덱스 혹은 클래스가 포함된 데이터를 계수 정렬(counting sort)의 개념을 적용해서 정렬할 수 있음을 배울 수 있었음

---