백준/ Gold 4 문제 , 백준 Node.js 자바스크립트 23883 알고리즘 수업 - 선택 정렬 3 [ 정렬 ]

백준/ Gold 4 문제 , 백준 Node.js 자바스크립트 23883 알고리즘 수업 - 선택 정렬 3 [ 정렬 ]

 

 

✔️Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함

 

 

문제 출처 🏠

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

23883번: 알고리즘 수업 - 선택 정렬 3

 

 

문제풀이 소감 🧑‍💻

 

의외로 단순하게 풀린다. 

 

선택 정렬은 최악의 상황에 O(N^2) 의 시간 복잡도를 가지는데

 

이 방법으로 풀면 O(N log N)으로 줄일 수 있다.

 

 

 

요구사항 📋

• 뒤에서 부터 선택정렬을 한다.
• 서로 스왑할때 카운트를 하나씩 한다.
• K번째 스왑을 할 경우 서로 교환한 숫자를 작은 순서대로 출력한다.
• 스왑이 K번 이내로 정렬이 완료되었을때는 -1을 출력한다. 

 

주의 ❗

 

배열의 크기가  최대 50만이므로 O(N^2) 풀이로 풀리지 않는다.

 

좀 더 효율적인 방법을 생각해보자. 

 

 

 

 

해결 전략 📝

 

해당 숫자를 정렬해야할지 말지는 어떻게 알 수 있을까?

 

바로, 정렬된 배열과 위치를 비교해서 같은 위치의 값이 같다면 할 필요가 없고 다르다면 정렬을 해야합니다.

 

되게 단순하죠?

 

 

sort를 사용해 우선 정렬된 배열을 만듭니다. (원본값 손상을 막기 위해 spread 문법을 사용합시다)

 

이후 주어진 배열을 뒤에서부터 비교하면서 정렬을 할지말지 확인합니다.

 

만약, 값이 같다면 정렬을 할 필요가 없으니 다음 인덱스로 넘어가고 

 

위치가 다르다면 이제 스왑을 해줄 차례입니다.

 

 

5 2
3 1 2 5 4

 

이 예시로 보자면

 

정렬된 배열은 1 2 3 4 5 입니다.

 

 

근데 원본 배열의 맨 뒤는 4 , 정렬된 배열의 맨 뒤는 5이니까 서로 값이 다르죠?

 

그럼 이 4자리에 5가 들어오게 바꿔줘야합니다.

 

 

여기서 그럼 필요한 정보가 무엇일까요?

 

5가 들어온다는건 정렬된 배열을 보고 알았으니

 

이제 원본 배열에서 4가 어디에 있는지를 알아야겠죠? 그래야 서로 스왑을 할테니.

 

이것을 위해서 원본 배열을 한 번 순회해서 각 숫자의 지금 위치들을 dict에 담아줍니다.

 

 

이 순회를 마치게 되면, position 이라는 객체에는 각 숫자들이 원본 배열에서 현재 몇번 인덱스에 있는지에 대한 정보가 모두 담겨져 있을 겁니다.

 

 

 

그럼 이제 서로 스왑을 해줍니다.

 

 

 

당연히, 동일 인덱스에서 정렬되어있는 배열에 있는 값이 큰값이고 원본 배열에 있는 값이 작은 값이겠죠?

 

그러므로 각각 MIN, MAX에 담아준 뒤

 

큰 값을 원본배열의 인덱스 위치에 넣어줍니다.

 

이후 작은 값은 원래 큰값이 있었던 위치로 넣어주고요.

 

 

놓치지 말아야할 게 서로 위치가 바뀌었으므로 position 객체에 있는 각 숫자의 현재 위치 값도 변경시켜줘야합니다.

 

또한 스왑이 한 번 이루어졌으므로 cnt값도 세주고요.

 

 

이 과정을 계속 하다보면 cnt 값이 K 값이랑 같아질 수 있습니다. 

 

이때의 스왑 숫자들을 알맞게 출력해줍니다.

 

만약 정렬이 다 되었는데 스왑 횟수가 K보다 작다면 -1을 출력해주면 됩니다.

 

 

 

 

정답 💯

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const [input_N, input_K] = input[0].split(" ").map(Number);
input.shift();
const [...input_nums] = input[0].split(" ").map(Number);

function solution(N, K, nums) {
  const sortedNums = [...nums].sort((a, b) => a - b);
  const position = {};
  nums.forEach((v, i) => {
    position[v] = i;
  });
  let cnt = 0;
  for (let j = N - 1; j >= 0; j--) {
    if (nums[j] !== sortedNums[j]) {
      const MIN = nums[j];
      const MAX = sortedNums[j];
      nums[j] = MAX;
      nums[position[MAX]] = MIN;
      position[MIN] = position[MAX];
      position[MAX] = j;
      cnt += 1;
      if (cnt === K) {
        console.log(MIN, MAX);
        break;
      }
    }
  }
  if (cnt < K) console.log(-1);
}

solution(input_N, input_K, input_nums);