알고리즘(주말)

당연하지만 배열의 push, pop은 O(1)의 시간복잡도를 가지고 있고
shift, unshift, concat, slice, splice, forEach, map, filter, reduce등은 O(N)의 시간복잡도를 가지고 있다.

하지만 sort는 O(Nlog N)의 시간복잡도를 가지고 있다는 사실은 새로 알게 됐다.
sort의 시간복잡도는 O(Nlog N)이기 때문에 버블, 선택정렬등을
경우에 맞게 사용하면 O(N)의 시간복잡도가 나올 수 있지 않을까 생각하며
어떤 정렬이 더 알맞을지 고민해보다가

문득 sort의 시간복잡도가 O(N*log N)라는 사실은 알지만
최적이 어떤지는 모르고 있다는 사실이 떠올랐고

JS에서 기본적으로 제공하는 sort 함수는 어떤 알고리즘으로 구성되어있는지에 대해 생각해본적은 없다는 사실을 알게 되었다.

간단하게 말하자면 하나의 언어에서 제공되는 함수 또는 기능들은 당연히 최적화가 되어있다는 것이다..

삽입(insert)정렬과 합병(merge)정렬을 결합하여 merge정렬의 최적, 최악, 평균 모두 O(Nlog N)인 것과는 다르게 최악의 경우 O(Nlog N), 최적의 경우 O(N)의 결과를 보이는 정렬법이다. merge정렬의 최악(O(N*log N))과 삽입정렬의 최선(O(N))이 합쳐졌다고 볼 수 있다. (삽입정렬의 평균과 최악은 O(N^2)이다)

간단한 복습을 진행하면서도 전에는 학습에 급급해서 지나쳤던 부분들이 눈에 보이는 것 같다.

또한 문제를 단순히 해결하고 만족하며 넘어가는 것이 아닌 다음과 같은 단계를 걸쳐
발전할 수 있는 기회를 놓치지 않는 것이 중요하다는 사실도 다시 한번 깨달았다.

1.결과가 확인 가능한가
2.다른 방식으로 결과를 도출할 수 있는가
3.가독성이 좋게 구성되어있는가
4.다른 문제에도 적용할 수 있는가
5.성능을 향상시킬 수 있는가
6.리팩토링이 가능한가
7.다른사람은 이 문제를 어떻게 해결하였는가

또한 정규표현식보다 55% 더 빠르다고 하는 charCodeAt 비교 또한 주목할만하다.
비록 특수문자에 대해서는 약세(다양하기 때문에)를 보이고 있지만 숫자, 대소문자 및 자주 사용되는 기호들의 체크에는 편하게 사용할 수 있다.
//내부 체크 예시(55% 더 빠름)
code = str.charCodeAt(i)
if(!(code > 47 && code < 58) && !(code > 64 && code < 91) && !(code > 96 && code < 123)) return false

CT(1).백준 2443 별찍기는 for문을 input-1부터 역순으로 내려가며 공백을 추가하고 별을 줄이는 방식으로 진행했다.

let input = 5
let result = []
for(let i = input-1 ; i >= 0 ; i--){
    result.push(`${` `.repeat(input-i-1)}${'**'.repeat(i)}*`)
}

console.log(result.join('\n'))

CT(2).프로그래머스 큰 수 만들기는 순서는 건드리지 않은 채로 가장 큰 숫자를 만들어야 하는문제였다. 확실히 2단계라서 그런지 의사코드를 작성해야 수월하게 풀 수 있었다.
간단하게 시작점과 다음을 비교해 현재가 다음보다 작으면 버리는 방식으로 진행했지만
3,2,1,4,3,2,1같은 형태에 3개를 제거하는 문제라면 앞의 3,2,1으로 내림차순이라도 그 다음이 더 크기 때문에 버려야 하는 상황이었다.
결국 이전에 작성한 코드를 다 버리고 수도코드를 작성했다.
1.남은 횟수만큼 체크해 현재값이 가장 크면 값 추가
2.아닌 경우 현재 값 버리고(그냥 통과) 남은 제거횟수 1감소
3.체크할 함수 만들어 조건으로 넣고 stop이 0이 된 경우 나머지 값은 바로 넣어주고 종료

하지만 12번 테스트케이스에거 걸렸는데 문제는 stop이 0이 아닌 경우로도 그냥 끝나버리는 것이었다.
예를 들어 5,4,3,2,1인 경우 내림차순이기 때문에 걸리는 조건이 없어 3개를 제거하라고 해도 54321로 출력이 되어버린다.
이 부분을 방지하기 위해 isMax체크와 &&를 사용해 남은 길이(arr.length)가 현재 위치(i)와 남은 제거 횟수(stop)보다 큰 경우만 진행하고 아닌 경우는 제거하는 쪽으로 넘기기로 변경했다.

function solution(number, k) {
    let answer = ''
    let arr = number.split('').map(Number)
    let stop = k
    for(let i = 0 ; i < arr.length ; i++){
        if(stop === 0){
            answer += arr[i]
            continue
        }
        if(isMax(i,stop,arr) && arr.length > i+stop){
            answer += arr[i]
        }
        else{
            stop--
        }
    }
    return answer;
}

function isMax(a,num,arr){
    for(let i = a+1 ; i <= a+num ; i++){
        if(arr[a] < arr[i]){
            return false
        }
    }
    return true
}