2021.8.21 TIL (정렬 3가지 알고리즘 문제)

목차

Special sort

삽입 정렬

Least Recently Used Cash

---

Special sort (버블 정렬 응용)

배열의 제시된 순서를 지킨 채로 왼쪽으로, 양의 정수는 오른쪽으로 배열한다.

 

function solution(num) {
  // code here
  return num;
}

let arr = [1, 2, 3, -3, -2, 5, 6, -6];
console.log(solution(arr)); // [-3, -2, -6, 1, 2, 3, 5, 6]

 

 

답)

 

function solution(num) {
  for(let i = 0; i < num.length - 1; i++) {
    for(leg j = 0; j < num.length - 1 - i; j++) {
      if(num[j] > 0 && num[j+1] < 0) {
        [num[j], num[j+1]] = [num[j+1], num[j]]
      }
    }
  }
  return num;
}

 

 

삽입 정렬 (insertion sort)

삽입정렬은 자료의 배열을 앞에서 차례대로 정리하면서, 정리된 배열과 비교하여 자기의 위치를 찾아 삽입하는 방법이다.

 

• 10 5 6 8 2
• 10 5 6 8 2
• 5 10 6 8 2
• 5 6 10 8 2
• 5 6 8 10 2
• 2 5 6 8 10

 

function solution(num) {
  // code here
  return num;
}

let arr = [10, 5, 6, 8 2];
console.log(solution(arr)); // [2, 5, 6, 8, 10]

 

 

답)

 

function solution(num) {
  for(let i = 1; i < num.length; i++) {
    for(let j = 0; j < i; j++) {
      if(num[j] > num[i]) {
        [num[j], num[i]] = [num[i], num[j]];
        continue;
      }
    }
  }
  return num;
}

 

 

답2)

 

function solution(num) {
  for (let i = 1; i < num.length; i++) {
    let ist = num[i];
    for (let j = i - 1; j >= 0; j--) {
      if (num[j] > ist) {
        num[j + 1] = num[j];
      } else {
        arr[j + 1] = ist;
        break;
      }
    }
  }
  return num;
}

 

 

Least Recently Used Cash

캐쉬의 용량이 정해져 있는 상황에서, 여러 작업이 배열로 주어진다. 캐쉬 안에 이미 작업된 내용이 있을 경우, 그 작업을 캐쉬에서 빼내어 캐쉬의 최상단으로 옮긴다. 캐쉬에 없을 경우 캐쉬의 최상단으로 옮기며, 캐쉬의 용량을 초과할 경우 캐쉬의 가장 오래된 데이터는 지워진다.

만약, 캐쉬의 용량이 5고 [1, 2, 3, 2, 6, 2, 3, 5, 7]의 작업이 주어질 경우 캐쉬의 변화는 다음과 같다.

 

[ 1, 0, 0, 0, 0 ]
[ 2, 1, 0, 0, 0 ]
[ 3, 2, 1, 0, 0 ]
[ 2, 3, 1, 0, 0 ]
[ 6, 2, 3, 1, 0 ]
[ 2, 6, 3, 1, 0 ]
[ 3, 2, 6, 1, 0 ]
[ 5, 3, 2, 6, 1 ]
[ 7, 5, 3, 2, 6 ]
[ 7, 5, 3, 2, 6 ]

 

function solution(size, data) {
  let answer;
  // code here
  return answer;
}

let arr = [1, 2, 3, 2, 6, 2, 3, 5, 7];
console.log(solution(5, arr)); // [7, 5, 3, 2, 6]

 

 

답) 내장 함수 이용이 가능할 때 (.splice(), .concat())

 

function solution(size, data) {
  let answer = Array.from({length: size}, ()=>0);

  for(let el of data) {
    let idx = answer.indexOf(idx);

    if(idx >= 0) {
      let omit = answer.splice(idx, 1); // [1]
      answer = omit.concat(answer);
    } else {
      answer.pop();
      answer.unshift(el);
    }
  }

  return answer;
}

 

 

답 2) 내장 함수 이용이 불가능할 때

 

function solution(size, data) {
  let answer = Array.from({ length: size }, () => 0);
  for (let i = 0; i < data.length; i++) {
    for (let j = 0; j < size; j++) {
      let cnt = -1;

      for (let k = 0; k < size; k++) {
        if (answer[k] === data[i]) {
          cnt = k;
        }
      }

      if (cnt === -1) {
        for (let k = size - 1; k >= 1; k--) {
          answer[k] = answer[k - 1];
        }
      } else {
        for (let k = cnt; k >= 1; k--) {
          answer[k] = answer[k - 1];
        }
      }
      answer[0] = data[i];
    }
  }
  return answer;
}