[BOJ] 1181번 : 단어 정렬

백준 1181번 : 단어 정렬

🔗 문제 링크

https://www.acmicpc.net/problem/1181

1181번: 단어 정렬

 

---

💬 문제

 정렬 알고리즘 에 대한 이해가 있다면, 충분히 풀 수 있는 문제다.

1. 1번째 줄에 정렬해야 하는 문자열의 개수 N이 주어진다.
2. 2번째 줄부터 총 N개의 문자열이 주어지며, 이를 배열 arr로 받아준다.
3. 길이가 짧은 것 순으로 정렬하고, 길이가 같을 겨우에는 사전 순으로 정렬한다.
4. 중복된 단어가 있을 경우, 하나만 남겨준다.
   
   

 

---

💡 입력값 받아오기

JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.

이 문제에서는 1번째 줄에 N을 주고, 그 다음줄부터 N개의 문자열이 주어진다.

줄바꿈으로 잘라주고 N과 N개의 문자열이 담긴 배열 arr로 나눠준다.

 

 

입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.

https://valueengine.tistory.com/2

[BOJ] Node.js로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅

 

728x90

 

---

🔑 풀이 : sort() 메서드

• 입력값 input에서 문자열 갯수인 N(1번째 줄)과 문자열 배열 arr로 구조분해할당 해준다.
• 먼저, 중복된 문자열을 제거해준다
  
  - 동일한 값을 보유할 수 없는  set 객체 를 생성해 중복값을 제거해준다
  - sort() 메서드로 정렬해줘야 하므로,  Array.from 으로 set 객체를 배열로 전환해준다
  
  
• 알파벳 사전순으로 문자열을 정렬해준다
  
  - sort()는 유니코드값으로 정렬한다
  - a가 b보다 사전상 뒤에 있으면  sort() 메서드는 1을 반환하고, a가 b보다 사전상 앞에 있으면 -1을 반환하며, 두 개가 같을 경우는 0이다
  
  
• 문자열 길이 순으로 정렬해준다
  
  - 사전순으로 정렬할 때는 문자열의 길이를 신경쓰지 않는다. 따라서 사전순으로 정렬한 뒤에 길이 정렬을 해줘야 한다.

// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
[N, ...arr] = input;

console.log(solution(arr).join('\n'));

function solution(arr) {
  // 중복 제거
  arr = Array.from(new Set(arr));
  // 사전순 정렬
  sortedArr = arr.sort((a,b) => a > b ? 1 : (a < b ? -1 : 0));
  // 길이 정렬
  result = sortedArr.sort((a,b) => a.length - b.length);

  return result;
}

 

시간 효율은 다음과 같다.

 

 

---

👣 예제를 참고한 풀이

예제 입력
13
but
i
wont
hesitate
no
more
no
more
it
cannot
wait
im
yours

 

위 예제에서 arr는 ['but', 'i', 'wont', 'hesitate', 'no', 'more', 'no', 'more', 'it', 'cannot', 'wait', 'im', 'yours']가 된다.

 

• no와 more이 중복이 되므로, Array.from(new Set(arr))으로 제거하고 배열로 만들어주면 된다.
  - ['but', 'i', 'wont', 'hesitate', 'no', 'more', 'it', 'cannot', 'wait', 'im', 'yours']가 된다.
  
  
• 반환값에 따라 sort() 메서드로 사전순으로 정렬해준다.
  - ['but', 'cannot', 'hesitate', 'i', 'im', 'it', 'more', 'no', 'wait', 'wont', 'yours']가 된다.
  
  
• 길이순으로 정렬해준다.
  - ['i', 'im', 'it', 'no', 'but', 'more', 'wait', 'wont', 'yours', 'cannot', 'hesitate']

 

만약 아래 코드처럼 사전순 정렬과 길이순 정렬을 바꿔서 출력하면 잘못된 결과과 출력될 것이다.

// input값 처리
const input = require('fs').readFileSync('example.txt').toString().trim().split('\n');
[N, ...arr] = input;

console.log(solution(arr));

function solution(arr) {
  // 중복 제거
  arr = Array.from(new Set(arr));
  // 길이 정렬
  sortedArr = arr.sort((a,b) => a.length - b.length);
  // 사전순 정렬
  result = sortedArr.sort((a,b) => a > b ? 1 : (a < b ? -1 : 0));

  return result;
}

 

결과는 다음과 같이 잘못 출력된다.

[
  'but',
  'cannot',
  'hesitate',
  'i',
  'im',
  'it',
  'more',
  'no',
  'wait',
  'wont',
  'yours'
]

 

---

References

 

• https://velog.io/@jakeseo_me/Javascript-Sort함수에-대한-잡지식
• https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/from