[BOJ] 1427번 : 소트인사이드

백준 1427번 : 소트인사이드

🔗 문제 링크

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

1427번: 소트인사이드

 

---

💬 문제

 정렬 알고리즘 에 대한 이해가 있다면, 충분히 풀 수 있는 문제다.

 

1. 1번째 줄에 정수 N이 주어진다.
2. 이 정수의 각 자리수를 내림차순으로 정렬한다.
   
   

 

---

💡 입력값 받아오기

JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.

이 문제에서는 1번째 줄에 정수 N만 주어진다. 정수 N을 받아오기만 하면 된다.

 

 

입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.

https://valueengine.tistory.com/2

[BOJ] Node.js로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅

 

 

---

💻 풀이

이 문제는 여러가지 정렬 알고리즘으로 풀 수 있다.

총 4가지 방식으로 풀어볼 것이다.

 

🔑 풀이1 : sort() 메서드

• 입력값 N의 각 자리수를 잘라 배열 arr로 만들어준다.
• 배열 arr를 내림차순으로 정렬하고, 각 요소를 합쳐 하나의 정수로 만들어준다.

// input값 처리
const arr = require('fs').readFileSync('/dev/stdin').toString().trim().split('');

console.log(solution(arr));

function solution(arr) {
  sorted = arr.sort((a,b) => b - a);  // 내림차순 정렬

  return sorted.join('');
}

 

시간은 다음과 같이 걸렸다.

 

 

---

🔑 풀이2 : sort() 및 reverse() 메서드

• 입력값 N의 각 자리수를 잘라 배열 arr로 만들어준다.
• sort() 메서드로 오름차순 정렬을 해주고, 그걸 역순으로 뒤집어 내림차순으로 바꿔준다.

// input값 처리
const arr = require('fs').readFileSync('/dev/stdin').toString().trim().split('');

console.log(solution(arr));

function solution(arr) {
  sorted = arr.sort().reverse();  // 오름차순 정렬 및 역순 정렬

  return sorted.join('');
}

 

시간은 다음과 같이 걸렸다.

 

 

---

🔑 풀이3 : 병합 정렬

• 입력값 N의 각 자리수를 잘라 배열 arr로 만들어준다.
• 함수 mergreSort()로 크기가 1인 부분 배열로 쪼개주고, 함수 merge()를 통해 각 부분 배열의 요소를 비교해준다.
• merge() 함수를 통해 각 요소의 값을 비교해준다.
  
  - 내림차순이 되어야 하므로, 왼쪽(left[i])의 값이 오른쪽(right[j]) 값보다 더 커야한다

// input값 처리
const arr = require('fs').readFileSync('/dev/stdin').toString().trim().split('');

console.log(mergeSort(arr).join(''));

function merge(left, right) {
  const result = [];
  let [i, j] = [0, 0];

  while (i < left.length && j < right.length) {
    if (left[i] > right[j]) {     // left와 right 요소끼리 비교
      result.push(left[i]);       // 내림차순 정렬이어야 하므로, left가 더 커야한다
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  while (i < left.length) {
    result.push(left[i]);   // left에 남아있는 값을 추가
    i++;
  }
  while (j < right.length) {
    result.push(right[j]);  // right에 남아있는 값을 추가
    j++;
  }
  return result;
}

// 정렬되지 않은 배열 arr를 요소 1개만 가진 배열이 될 때까지 쪼개기
function mergeSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const mid = Math.ceil(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid, arr.length));

  return merge(left, right);
}

 

시간은 다음과 같이 걸렸다.

 

 

병합 정렬에 대한 더 자세한 설명은 아래 링크를 참고하길 바란다.

https://valueengine.tistory.com/9

[알고리즘] 병합 정렬 (merge sort)