[Node.js,백준]1377 - 버블 소트

목차

 

 

 문제

 

입력

첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

출력

정답을

출력한다.

 

 풀이

24년 3월 28일날 풀었으나 티스토리로 이관

 

정렬을 이용해서 푸는 문제 이다. 실제로 버블 정렬으로 풀면 시간 초과가 일어나기 때문에 다른 방법으로 풀어야 한다.

버블정렬엔 어떠한 규칙이있는데 앞의수가 뒤의수보다 클때 ex)(10 > 5)

앞의수는 뒤의수보다 작을때까지 어디든 이동이 가능하지만 뒤의 수는 앞으로 한번씩만 이동한다는 점이다.

이 점을 이용하기 위해

arrs라는 새로운 배열을 만들껀데 최초 배열의 [값, i(순서)]를 저장하고 값을 오름차순으로 만들어 최종 정렬형태로 만들어준다.

그다음 최대 인덱스 차이를 계산해야하는데 그 부분이 for문이 담당한다.

정렬된 배열을 순회하면서, 원래 배열에서의 인덱스와 정렬된 배열에서의 인덱스 차이(즉, 각 요소가 얼마나 이동했는지)를 계산한다. 이 차이의 최댓값이 정답이됩니다.

ex) 10, 1, 5, 2, 3

이 들어갔다면 각 순서를 포함한 arrs로 다시만들어주고

arrs = [ [10, 0], [1, 1], [5, 2], [2, 3], [3, 4] ]

이후 각 배열의 첫번째인 값으로 정렬 을 시켜준다.

arrs = [ [1, 1], [2, 3], [3, 4], [5, 2], [10, 0] ]

그럼 이제 각 배열을 for문으로 돌면서

재정렬된 배열을 기준으로([1,1]로 시작하는배열)

1인덱스로 시작했던 1이 0으로 이동했으니 1번 이동(1 - 0)이 된다.

2의 경우에는 3번인덱스에 위치했으나 정렬되면 1인덱스기 때문에 3 - 1인 총 2번 이동이 된다.

그다음 변하지 않는 배열이 정답이 되어야하므로 찾은 인덱스에서 +1 을 해준다.

 해결 방법 정리

문제 상황

입력으로 주어진 숫자 배열을 효율적으로 정렬하며, 각 숫자가 최초 위치에서 최종 위치로 이동한 횟수를 구하여 최대 이동 횟수를 찾는 문제입니다.

 

예시 입력

입력 배열: `[10, 1, 5, 2, 3]`

 

해결과정

 1. 배열 초기화

• 배열의 각 요소와 그 요소의 인덱스를 튜플로 만들어 새로운 배열을 생성합니다. 이를 통해 요소가 얼마나 이동했는지 추적할 수 있습니다.
• 초기 배열 : [[10, 0], [1, 1], [5, 2], [2, 3], [3, 4]]
• 여기서 첫 번째 요소는 원래 배열의 값, 두 번째 요소는 원래 배열에서의 인덱스입니다.

 2. 배열 정렬

• 새로운 배열의 첫 번재 요소(값)을 기준으로 오름차순 정렬을 수행합니다.
• 정렬 후 배열 : [[1, 1], [2, 3], [3, 4], [5, 2], [10, 0]]
• 이 배열은 각 숫자가 정렬된 순서대로 나열되어 있으며, 각 숫자가 원래 위치한 인덱스를 함게 보여줍니다.

 3. 최대 이동 거리 계산

• 정렬된 배열을 순회하면서 각 요소가 얼마나 이동했는지 계산합니다. 이동 거리는 원래 인덱스에서 현재 인덱스를 뺀 값의 절대값입니다.
• 계산 예
  • `[1, 1]`: 원래 인덱스 1에서 정렬 후 인덱스 0으로 이동 → 이동 거리: `|1 - 0| = 1`
  • `[2, 3]`: 원래 인덱스 3에서 정렬 후 인덱스 1로 이동 → 이동 거리: `|3 - 1| = 2`
  • `[3, 4]`: 원래 인덱스 4에서 정렬 후 인덱스 2로 이동 → 이동 거리: `|4 - 2| = 2`
  • `[5, 2]`: 원래 인덱스 2에서 정렬 후 인덱스 3로 이동 → 이동 거리: `|2 - 3| = 1`
  • `[10, 0]`: 원래 인덱스 0에서 정렬 후 인덱스 4로 이동 → 이동 거리: `|0 - 4| = 4`
  • 최대 이동 거리: 4 (10이 이동한 거리)

 4. 결과

• 문제에서 실제 이동 횟수를 요구하므로, 최대 이동 거리에 1을 더해야 합니다. 따라서 최종 답은 `4 + 1 = 5`입니다.

 코드

// 버블 소트
var fs = require('fs');
// var input = fs.readFileSync('/dev/stdin').toString();
let input = `5
10
1
5
2
3`

let real = input.trim().split("\n");
let [first, ...rest] = real;
let [N, M] = first.split(" ").map(Number);

async function solution() {
    let arrs = rest.map((r, i) => [Number(r), i]).sort((a, b) => a[0] - b[0]);
    let ans = 0
    for (let i = 0; i < N; i++) {
        if (arrs[i][1] - i > ans) {
            ans = arrs[i][1] - i
        }
    }
    console.log(ans + 1);
}

solution();