[js, node.js]백준 2947: 나무 조각

문제 요약

백준 2947:나무조각

• 두 조각의 순서가 바뀔때 마다 조각의 순서를 출력한다.

입력 1

2 1 5 3 4

입력 2

2 3 4 5 1

출력 1

1 2 5 3 4
1 2 3 5 4
1 2 3 4 5

출력 2

2 3 4 1 5
2 3 1 4 5
2 1 3 4 5
1 2 3 4 5

문제 분석

• 정렬의 결과뿐만 아닌 과정을 표현해야한다.
• 정렬이 시작되는 기준을 명확하게 세워야한다.
• 반복문을 사용할 때 단순하게 자리수만 비교해서 a > b로 조건을 건다면 입력 2에서 통과를 못할 것이다.

문제 설계

• 버블 정렬 알고리즘을 사용하여 배열을 정렬

1. 정렬을 준비하는 변수 선언

let sorted = false;

처음에는 정렬되지 않았으므로 false로 설정한다.

2. 버블 정렬 반복문

while (!sorted) {
  sorted = true;  
  arr.forEach((v, i, a) => {
    if (i < a.length - 1 && a[i] > a[i + 1]) {
      [a[i], a[i + 1]] = [a[i + 1], a[i]];  
      sorted = false;
      console.log(a.join(' '));
    }
  });
}

while (!sorted)
배열이 완전히 정렬될 때까지 루프를 반복한다.
sorted가 true가 될 때 루프 종료한다.

sorted = true;
각 루프 시작 시, 배열이 정렬되었다고 가정한다.
정렬 과정에서 요소가 교환되면 sorted를 다시 false로 설정한다.

arr.forEach
배열의 모든 요소를 순회하며 인접한 두 요소를 비교한다.

a[i] > a[i + 1]
현재 요소가 다음 요소보다 크다면,
ES6의 비구조화 할당을 사용하여 두 값을 교환한다.

sorted = false;
교환이 일어났으므로 배열이 완전히 정렬되지 않았음을 표시한다.

console.log(a.join(' '))
배열을 다시 문자열로 변환하여 현재 상태를 출력한다.

결론

시간 복잡도

최악의 경우 $𝑂(𝑛^2)$ , $n$은 배열의 길이
루프와 비교 연산이 중첩되기 때문이다.