백준 1181 단어 정렬 js

 

 

문제 

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

1181번: 단어 정렬

 

틀린코드

 

const fs = require("fs");

const filePath =
  process.platform === "linux" ? "/dev/stdin" : "./준/정렬/1181/input.txt";

const [N, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");

const charCode = arr
  .filter((e, i) => arr.indexOf(e) === i)
  .map((v) => {
    let sum = 0;
    for (let i = 0; i < v.length; i++) {
      sum += v.charCodeAt(i);
    }

    return [v.length, sum, v.charCodeAt(), v];

    // [
    //  글자길이 // 0번째 char 숫자 // 단어 char 합산 // 문자
    //   [1, 105, 105, "i"],
    //   [2, 214, 105, "im"],
    //   [2, 221, 105, "it"],
    //   [2, 221, 110, "no"],
    //   [3, 331, 98, "but"],
    //   [4, 435, 109, "more"],
    //   [4, 437, 119, "wait"],
    //   [4, 456, 119, "wont"],
    //   [5, 578, 121, "yours"],
    //   [6, 643, 99, "cannot"],
    //   [8, 855, 104, "hesitate"],
    // ];
  });

let answer = "";

charCode
  .sort((a, b) => {
    if (a[0] === b[0] && a[2] !== b[2]) {
      // 길이가 같고 첫글자가 겹치지 않을때 오름차순

      return a[2] - b[2];
    } else if (a[2] === b[2]) {
      // 첫번째 글자가 겹칠때 첫 글자 기준으로 사전순서로 나열

      return a[1] - b[1];
    } else {
      // 그냥 오름차순

      return a[0] - b[0];
    }
  })
  .forEach((e) => {
    answer += `${e[3]}\n`;
  });

console.log(charCode);
console.log(answer);

 

항상 백준에 있는 테케는 통과하고 실제 정답하면 틀림.

 

로직설명

 

- 길이가 작은 순서

- 길이가 같으면 사전순서

 

여기서 사전순서란 유니코드 순서다.

 

sort() 에 문자열이 abcdefg 알파벳 순서인줄 알았지 단어도 알아서 사전순서로 정렬 되는 줄은 정말 몰랐다.

그래서 charCodeAt 이라는 함수로 reduce를 돌려서 단어의 유니코드를 모두 더했고

이게 사전순서라고 생각 했다.

 

여기서 틀림

 

반례

 

ababc
ababb
cabba
ababc
ababc
ababc
abaca

 

에서 aaabbbcc 이런 글자를 순서를 바꿔서 교모하게 섞어가면 틀림

물론 무작정 자릿수 상관없이 유니코드를 리듀스로 더하기보다 자릿수마다 비교하면서 큰 순서로 했어야했는데

 

그냥 sort() 함수를 쓰는게 맘 편한거같다.

실제 정답코드들도 sort 함수만 썻다.

 

틀린코드 2

 

const fs = require("fs");

const filePath =
  process.platform === "linux" ? "/dev/stdin" : "./준/정렬/1181/input.txt";

const [N, ...string] = fs.readFileSync(filePath).toString().trim().split("\n");

function mergeSort(arr1, arr2) {
  let result = [];
  let i = 0;
  let j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr2[j].length > arr1[i].length) {
      result.push(arr1[i]);
      i++;
    } else if (arr2[j].length === arr1[i].length) {
      if (arr1[i].charCodeAt() === arr2[j].charCodeAt()) {
        if (charSort(arr1[i]) < charSort(arr2[j])) {
          result.push(arr1[i]);
          i++;
        } else {
          result.push(arr2[j]);
          j++;
        }
      } else if (arr1[i].charCodeAt() < arr2[j].charCodeAt()) {
        result.push(arr1[i]);
        i++;
      } else {
        result.push(arr2[j]);
        j++;
      }
    } else {
      result.push(arr2[j]);
      j++;
    }
  }

  while (i < arr1.length) {
    result.push(arr1[i]);
    i++;
  }

  while (j < arr2.length) {
    result.push(arr2[j]);
    j++;
  }

  // console.log(result, "\n");

  return result;
}

function merge(arr) {
  if (arr.length <= 1) return arr;

  let mid = Math.floor(arr.length / 2);

  let left = merge(arr.slice(0, mid));
  let right = merge(arr.slice(mid));

  // console.log(left, right);

  return mergeSort(left, right);
}

function charSort(char) {
  if (!char) return;

  let sum = 0;
  for (let i = 0; i < char.length; i++) {
    sum += char.charCodeAt(i);
  }
  // console.log(char, sum);

  return sum;
}

const filter = string.filter((v, i) => string.indexOf(v) === i);

const sort = merge(filter);

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

로직설명

 

병합정렬인데

 

반으로 나눌 수 없을 만큼 쪼개서 쪼개진 2개마다 비교비교비교 하는 로직으로 n log n 의 시간 복잡도를 가진다.

게시판을 보니까 시간복잡도 이야기가 있길래 서둘러 배워서 적용 해봤고

 

9%에서 자꾸 틀리다보니 많이 답답해서 정답을 보고 싶은 마음에 일단 덕지덕지 쓰긴했다.

역시 이것도 for문으로 charCode 를 다 더한 로직이다보니 9%에서 틀렸다. 

 

 

정답코드

 

const fs = require("fs");

const filePath =
  process.platform === "linux" ? "/dev/stdin" : "./준/정렬/1181/input.txt";

const [N, ...arr] = fs.readFileSync(filePath).toString().trim().split("\n");

function sort(arr) {
  let answer = [];

  // let setArr = Array.from(new Set(arr));
  let setArr = arr.filter((e, i) => arr.indexOf(e) === i);
  // console.log(setArr);

  let sorted = setArr.sort((a, b) => {
    if (a.length !== b.length) {
      return a.length - b.length;
    }
  });

  for (let i = 1; i <= sorted[sorted.length - 1].length; i++) {
    let temp = sorted.filter((el) => el.length === i);
    answer.push(...temp.sort());
  }

  answer.forEach((e) => console.log(e));
}

sort(arr);

 

나머진 다 똑같다.

answer.push(...temp.sort()) 이 부분에서 알아서 temp의 문자열을 사전순서로 정렬해준다.