[일일코테 Day15] 문자열 내림차순으로 배치하기(레벨1)

문제

programmers.co.kr/learn/courses/30/lessons/12917

코딩테스트 연습 - 문자열 내림차순으로 배치하기

문제가 짧아서 여기에 적어본다.

문자열 s에 나타나는 문자를 큰것부터 작은 순으로 정렬해 새로운 문자열을 리턴하는 함수, solution을 완성해주세요.
s는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 간주합니다.

• str은 길이 1 이상인 문자열입니다.

문제는 "주어진 문자열을 오름차순으로 정렬한다." 이다 예를들면 "Zbcdefg" -> "gfedcbZ" 이 된다.

풀이

문자열을 정렬하려면 문자열끼리 비교를 해야 한다. 다음의 두가지 방법이 존재 하는데

• 커스텀 비교 함수를 제공하기
• 언어 기본 라이브러리에서 제공하는 문자열 비교함수를 사용하기

우선 문제의 조건부터 확인해 보자.

• 문자열에 나오는 문자를 정렬한다.
• 문자를 큰것부터 작은 순으로 정렬한다.
• 대문자는 소문자보다 작은것으로 간주한다.

그 다음엔 라이브러리에서 제공하는 기능이 어떻게 동작하는지 알아보자. 여기서 a 와 b는 문자를 의미한다.

• 어떤 함수를 사용해야 하는가?
• 언어에서 제공하는 기본 정렬 함수는 어떻게 동작하는가?
• a - b 는 어떻게 동작하는가?
• a > b 는 어떻게 동작하는가?

Javascript

String.prototype.split()

우선 Array.prototype.sort() 함수를 사용하려면 문자열을 정렬이 가능한 문자의 배열로 변경해주어야 한다. 여러가지 방법이 있겠지만 나는 네 splite("") 와 같은 방법을 사용했다.

Array.prototype.sort()

사용 방법은 아래와 같다.

arr.sort([compareFunction])

arr.sort([compareFunction])

sort() 함수는 compareFunction을 옵션으로 제공 하 수 있다.

sort() 메서드는 배열의 요소를 적절한 위치에 정렬한 후 그 배열을 반환합니다. 정렬은 stable sort가 아닐 수 있습니다. 기본 정렬 순서는 문자열의 유니코드 코드 포인트를 따릅니다. 예를들오 "바나나"는 "체리" 앞에 옵니다.

기본 정렬 순서는 문자열의 유니코드 코드 포인트를 따른다. 이게 무슨 말일까?

코드포인트란?
문자열 인코딩 용어에서, 하나의 코드포인트 혹은 코드 포지션은 codespace를 차지하는 어떤 숫자 값을 의미한다. 대부분의 코드포인트들은 문자 한개를 표현하지만, 포매팅과 같은, 간혹 다른 의미를 가질 수도 있다. 

예를들어서 ASCII 문자 인코딩 규약(Scheme)은 16진수 0부터 7F까지의 128개의 코드포인트로 이루어져 있다. 

쉽게 말하면 문자열을 나타내는 숫자값을 의미한다.

즉 기본 동작은 문자값이 가지는 코드포인트를 기준으로 정렬을 하고 코드포인트가 적은 숫자가 앞에오게 정렬을 한다. 예를들면 ['b'', 'a'].sort() 를 호출하면, 결과값을 ['a', 'b'] 가 된다.

 

그럼 ASCII 코드 값은 어떻게 될까? 아래의 표를 보면 대문자는 41 ~ 5A 까지의 코드포인트를 가지고 소문자는 61 ~ 7A까지의 코드 포인트를 가진다. 

문제의 조건에서 문자를 큰것부터 작은것으로 정렬 해야하고, 대문자는 작은것으로 간주한다고 되어 있다. 그렇다면 ['A', 'a', 'b', ] 는 ['b', 'a', 'A']가 되어야 하고 codepoint로 변환해 보면 [62, 61, 41] 가 되고 코드포인트가 큰것이 앞으로 오개 하면된다.

 

compareFunction에서 어떻게 정렬 순서를 결정하는가?

MDN 에서 나온 설명을 보면

compareFunction이 제공되면 배열 요소는 compare 함수의 반환 값에 따라 정렬됩니다. a와 b가 비교되는 두 요소라면,
- compareFunction(a, b)이 0보다 작은 경우 a를 b보다 낮은 색인으로 정렬합니다. 즉, a가 먼저옵니다.
- compareFunction(a, b)이 0을 반환하면 a와 b를 서로에 대해 변경하지 않고 모든 다른 요소에 대해 정렬합니다. 참고 : ECMAscript 표준은 이러한 동작을 보장하지 않으므로 모든 브라우저(예 : Mozilla 버전은 적어도 2003 년 이후 버전 임)가 이를 존중하지는 않습니다.
- compareFunction(a, b)이 0보다 큰 경우, b를 a보다 낮은 인덱스로 소트합니다.
- compareFunction(a, b)은 요소 a와 b의 특정 쌍이 두 개의 인수로 주어질 때 항상 동일한 값을 반환해야합니다. 일치하지 않는 결과가 반환되면 정렬 순서는 정의되지 않습니다

구현 하는 방법은 두 가지 있는데

• 비교 연산을 사용:  a > b ? -1 :  1 
• 빼기 연산을 사용: b.charCodeAt(0) - a.charCodeAt(0)
• 실수: b - a 의 결과는 NaN이므로 사용하면 안된다

빼기 연산을 사용하는것이 코드가 더 짧긴 하지만, 크다면(a > b) a를 앞에(-1) 라는 표현이 더 읽이 쉬운코드인것 같아서 두번째 방법을 사용하였다. 

Code

A가 크면 A가 앞에 온다로 익히는 코드

function solution(s) {
    return s.split('').sort((a, b) => a >= b ? -1 : 1).join('');
}

a 가 커야 앞에(-1) 오니까 a를 빼는 코드. 한번 더 생각해야 이해가 된다.

function solution(s) {
    return s.split('').sort((a, b) => b.charCodeAt(0) - a.charCodeAt(0)).join('');
}

동작하지 않았던 잘못된 코드.

function solution(s) {
    return s.split('').sort((a, b) => b - a).join('');
}

결론

굉장히 쉬운문제 였지만. 조건을 대충 읽거나 sort 함수를 잘 이해지 못하고 있거나, 문자열 코드포인터에대해서 정확히 알고 있지 않으면 한번에 맞추기는 쉽지 않은 문제 였다. 대충 몇 번 조건식만 변경하는 방법으로 문제를 맞출 수도 있지만. 제대로 알고 문제를 푸어야 겠다라는 생각을 했다.

 

나 같은 경우는 처음에 자바스크립트에서 sort((a.b) => b -a) 라고 구현했었는데 게속 테스크가 실패 했었다. 원인은 자바 스크립트에서는 문자하나는 문자열이고 문자열끼리이 뺄샘은 정의되지 않아 NaN의 결과를 나왔다. 그렇게 되면 compareFunction의 결과는 0을 리턴한 경우를 같아지게 되고 결과는 정렬을 하지 않는 결과가 나온다.