백준) 2947 - 나무 조각 JS

📌 문제 링크

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

---

📌 문제 탐색하기

• 5개의 나무조각을 가지고 있을 때 나무조각에는 1~5개의 숫자 중 하나가 쓰여있다. 이때 해당되는 조각의 수가 다음 조각의 수보다 크면 둘의 위치를 바꾸는 과정으로 끝에 있는 조각까지 진행한다. 위치를 바꿀 때마다 조각의 순서를 출력해라. 

시간복잡도

• 이중 for문이 들어가 있어 O(n^2)

알고리즘 선택

• 버블 정렬 

---

📌 코드 설계하기

1. 문제의 input을 공백으로 분리하고 숫자로 변환합니다.
2. 중복을 제외한 배열을 끝까지 조회하는 반복문을 만듭니다.
3. 양 옆만 조회할 반복만을 만듭니다.
4. 만약 왼쪽 요소가 오른쪽 요소보다 크다면 오른쪽 요소에 왼쪽 요소의 값을 대입시키고, 왼쪽 요소에 오른쪽 요소의 값을 대입시킵니다.
5. 해당 배열을 출력합니다.

---

📌 정답 코드

5개의 나무조각이라 반복문을 5번 다 돌아도 문제는 통과했다.

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input2.txt";
const trees = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split(" ")
  .map(Number);

for (let i = 0; i < trees.length; i++) {
  for (let j = 0; j < trees.length - 1; j++) {
    if (trees[j] > trees[j + 1]) {
      const temp = trees[j];
      trees[j] = trees[j + 1];
      trees[j + 1] = temp;
      console.log(trees.join(" "));
    }
  }
}

 

하지만 버블정렬이라 정렬이 되면 오른쪽에 있는 요소는 점점 중복 확인이 되니 굳이 반복문이 돌 필요는 없다는 생각이 들었고,

`for (let i = 0; i < trees.length - 1; i++) {`와 `for (let j = 0; j < trees.length - i - 1; j++) {`를 추가적으로 작성해 주었다.

const fs = require("fs");
const filePath =
  process.platform === "linux" ? "/dev/stdin" : __dirname + "/input1.txt";
const trees = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split(" ")
  .map(Number);

// 버블정렬 최적화
// 마지막 요소 제외
for (let i = 0; i < trees.length - 1; i++) {
  // 이미 정렬된 요소 제외
  for (let j = 0; j < trees.length - i - 1; j++) {
    if (trees[j] > trees[j + 1]) {
      const temp = trees[j];
      trees[j] = trees[j + 1];
      trees[j + 1] = temp;
      console.log(trees.join(" "));
    }
  }
}

 

애초에 배열 크기 자체가 크지 않아서인지 시간에서는 차이가 없었다...🥺