백준 - 03

1181번 - 단어 정렬 (정렬)

• 입력

  첫째 줄에 단어의 개수 N이 주어진다.

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

  13
  but
  i
  wont
  hesitate
  no
  more
  no
  more
  it
  cannot
  wait
  im
  yours
  

• 출력

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

  i
  im
  it
  no
  but
  more
  wait
  wont
  yours
  cannot
  hesitate
  

---

solution

• 중복 제거 : Set 객체 활용
• 알파벳 정렬 : Array.sort 와 String.localeCompare 활용

const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let input = require("fs").readFileSync(filePath).toString().trim().split("\n");

input.shift();

// 단어들의 배열로 Set 객체를 생성 (중복 제거)
let newSet = new Set(input);

// Set객체로 다시 배열을 만들어 sort(정렬) => 문자열 길이 순서로 오름차순, localeCompare함수로 알파벳 정렬
let arr = Array.from(newSet).sort((a, b) =>
  a.length - b.length !== 0 ? a.length - b.length : a.localeCompare(b)
);

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

---

String.localeCompare()

참조 문자열이 정렬 순으로 지정된 문자열 앞 혹은 뒤에 오는지 또는 동일한 문자열인지 나타내는 수치를 반환합니다.

referenceStr.localeCompare(compareString, locales, options)

• compareString : referenceStr과 비교할 문자열
• locales

const a = "apple";
const b = "banana";

// 'a' 는 'b' 보다 앞에 옵니다
console.log(a.localeCompare(b)); // 음수 값 반환
console.log(b.localeCompare(a)); // 양수 값 반환

---

18870번 - 좌표 압축 (정렬)

Xi를 좌표 압축한 결과 X’i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수 출력

• 입력

  첫째 줄에 N이 주어진다.

  둘째 줄에는 공백 한 칸으로 구분된 X1, X2, …, XN이 주어진다.

  5
  2 4 -10 4 -9
  

• 출력

  첫째 줄에 X’1, X’2, …, X’N을 공백 한 칸으로 구분해서 출력한다.

  2 3 0 3 1
  

---

solution

• 중복 제거 필요 : Set 객체 활용
• 제한 시간 2초 : Map 객체 활용

// 방법 1 : 반복문 중첩
// 시간초과 발생
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let input = require("fs").readFileSync(filePath).toString().trim().split("\n");

let arr = input[1].split(" ");
let setArr = [...new Set(arr)].sort((a, b) => a - b);
let answer = [];

// for of와 reduce로 시간 복잡도 O(n^2)
for (let x of arr) {
  answer.push(setArr.reduce((acc, y) => (x > y ? acc + 1 : acc), 0));
}

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

// 방법 2 : Map 객체 활용
const filePath = process.platform !== "linux" ? "./test.txt" : "dev/stdin";
let input = require("fs").readFileSync(filePath).toString().trim().split("\n");

let arr = input[1].split(" ");
let setArr = [...new Set(arr)];
let map = new Map();

setArr
  .sort((a, b) => a - b)
  .forEach((x, index) => {
    map.set(x, index);
  });

let answer = [];

arr.forEach((x) => {
  answer.push(map.get(x));
});

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

• 반복문을 중첩해서 사용하면 시간 복잡도 O(n^2)이지만 Map 객체 활용으로 시간 복잡도 O(n)으로 줄일 수 있습니다.