The Full Counting Sort

사이트: HackerRank
난이도: 미디움
분류: Sorting

문제

정수와 연관된 문자열 배열이 주어졌을 때 계수정렬(counting sort) 하고 하나의 문자열로 출력하라. 이 때 배열의 전반부에 해당되는 요소들은 -로 대체한다.

A = [[0, 'a'], [1, 'b'], [0, 'c'], [1, 'd']];

위 배열이 주어졌을 때 아래와 같이 출력한다.

- c - d

1. 나의 풀이

문제 자체에서 계수정렬(counting sort)을 사용하라고 말해줬기 때문에 그다지 어렵지 않은 문제였다.

function countSort(arr) {
    // Write your code here
    const length = arr.length;
    const counting = new Array(11);
    const addString = (idx, str) => {
        if (!counting[idx]) {
            counting[idx] = str;
        } else {
            counting[idx] += ` ${str}`;
        }
    }
    
    for (let i = 0; i < arr.length; i++) {
        const [idx, str] = arr[i];
        
        if (i < (length / 2)) {
          	// 배열에 전반부에 해댱되면 '-'로 대체
            addString(idx, '-');
        } else {
            addString(idx, str);
        }
    }
    
  	// 특정 인덱스에 문자열이 없는 경우도 고려해야 한다.
    console.log(counting.filter(v => v).join(' '));
}

2. 다른사람의 풀이

바로 풀 수 있었던 문제들은 지금은 생략하고 추후 더 효율적인 문제 풀이법을 찾아보도록 하겠다.