The Full Counting Sort

Eunseo·2022년 5월 19일
0

HackerRank

목록 보기
7/18
post-thumbnail

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)의 개념을 적용해서 정렬할 수 있음을 배울 수 있었음

profile
내가 공부한 것들

0개의 댓글