[Javascript] 백준 1181 : 단어 정렬

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

알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오.

1. 길이가 짧은 것부터
2. 길이가 같으면 사전 순으로

단, 중복된 단어는 하나만 남기고 제거해야 한다.

입력

첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다.

출력

조건에 따라 정렬하여 단어들을 출력한다.

---

📌 문제 탐색하기

또다시 정렬 문제이다. sort()를 이용한 길이 오름차순 나열과, 사전 순 정렬을 해야 하는거 같다.

 

1. 먼저 for 문으로 N 만큼 반복하여 단어 길이 비교 -> sort()

2. 길이가 같으면 사전 순으로 나열

    -> 근데 단어 길이를 비교하여 짧은 순으로 나열을 끝낸 후에 사전 순으로 나열을 진행해야 하는지

    -> 아니면 단어 길이를 비교하는 과정에서, 길이가 같으면 바로 사전 순으로 나열하게끔 해야하는지

    -> 근데 첫 번째 방법으로 비교하게 되면, 2N만큼 비교를 하게 되니까 불필요한 횟수가 늘어날거 같다.

3. 중복 제거

     -> 사전 순으로 나열이 끝난 다음 다시 비교하면서 같은 경우 filter()로 제거

     -> 근데 이러면 또다시 N번을 렌더링하는거라 효율적인 방법인지는 고민이 필요해 보인다.

---

📌 코드 설계하기

[1회차]

1. 입력값 가져오기

    -> [N, ...arr]=input

2. 오름차순 길이 비교

     -> 길이 N인 for문

     -> arr.sort((a,b)=>{아래 조건문})

     -> if(a.length===b.length){사전순 비교 로직}

     -> else{a.length-b.length} 

3. 사전순 비교 로직 

     -> if(a===b) return a;

     -> else { [a,b].sort() }  : 기본적으로 사전순으로 정렬된다

4. 줄바꿈 구조로 배열 분해

     -> join(" "), join("\n")을 이용하여 배열 분해

 

[2회차]

1. 입력값 가져오기

    -> [N, ...arr]=input

2. 중복 제거

    -> 전체 배열에서 일단 중복부터 제거하고 시작하는게 나중에 불필요한 반복을 줄이고 더 깔끔할거 같다.

    -> 찾아보니 JS의 Set() 함수를 사용하면 중복을 제거할 수 있는 것 같다.

    -> [...new Set(arr)]

//배열의 중복값 제거
const arr = [1, 2, 2, 3, 4, 4, 5];
const uniqueArr = [...new Set(arr)];

console.log(uniqueArr); // [1, 2, 3, 4, 5]

 

3. 사전순 비교

    -> localeCompare() 함수 사용

//기본형
참조문자열.localeCompare(비교문자열);

//반환값
-1: 참조문자열이 비교문자열보다 앞에 있는 경우.
1: 참조문자열이 비교문자열보다 뒤에 있는 경우.
0: 두 문자열이 동일한 경우.

 

4. 문자열 변환

   -> 제출하기 전 요구하는 형식으로 배열을 문자열로 풀어야 한다.

  -> 

cf) Array.prototype.sort()

• Array.prototype.sort()는 내부적으로 숫자를 기반으로 요소의 순서를 정하기 때문에, 문자열 비교도 숫자(-1, 0, 1)를 반환하는 함수가 필요하다.
• [a,b].sort() 함수는 단순히 배열을 정렬할 뿐이며, 그 결과를 비교 함수에서 사용할 수 없다.

---

📌 시도 회차 수정 사항

[1회차]

• 위에 설계한 방식으로 코드를 짜봤는데 실패했다...ㅎ
• 다시 보니 불필요한 이중 루프도 포함되어 있는거 같고

    1. push 구문을 잘못 사용한거 같다.

    2. Array.prototype.sort() 함수에 대해 잘못 이해하고 있었던거 같다.

        -> Array.prototype.sort()는 숫자를 반화해야하는 함수이기 때문에, 문자열을 반환하는 [a,b].sort() 함수는 그 안에서 사용할 수                 없다.

    3. sort() 함수의 경우 배열의 모든 요소를 처음부터 끝까지 순차적으로 비교하기 때문에, for문으로 감쌀 필요가 없다!

    4. 잘못된 문자열 변환 방식

        -> join()은 배열 내부를 다시 하나의 문자열로 합치는 함수이다.

        -> 문제에서 주어진건 1차원 배열이기 때문에 이미 배열 내부는 문자열이기 때문에 굳이 join(" ")를 사용할 필요가 없었다.

        -> 2차원 배열의 경우 배열 안에 또 배열이 있기 때문에 join(" ") 함수를 사용할 수 있다.

//실패한 코드
const input = require("fs").readFileSync(0, "utf-8").trim().split("\n");
  [N, ...arr] = input;
  const newArray = [];
  const answer = [];

  for (let i = 0; i < N; i++) {
    newArray.push = arr.sort((a, b) => {
      if (a.length === b.length) {
        if (a === b) {
          return a;
        } else {
          [a, b].sort();
        }
      } else {
        a.length - b.length;
      }
    });
  }

  for (let i = 0; i < N; i++) {
    answer.push(newArray[i].join(" "));
  }

  console.log(answer.join("\n"));

---

📌 정답 코드

  const input = require("fs").readFileSync(0, "utf-8").trim().split("\n");
  [N, ...arr] = input;
  const newArray = [...new Set(arr)];

  newArray.sort((a, b) => {
    if (a.length === b.length) {
      return a.localeCompare(b);
    } else {
      return a.length - b.length;
    }
  });

  console.log(newArray.join("\n"));

 

해설: https://whydevsaysno.notion.site/1312bcf9b1854c91b1947f85263f6142