[C++] 삽입정렬 - Least Recently Used(카카오캐시 변형)

삽입정렬 : 이전 값들과 비교하여 한 칸씩 뒤로 옮기고 삽입한다.

#include <iostream>

int main() {
    int S,N,i,j,tmp,idx;
    int cnt[100];
    
    scanf("%d %d",&S,&N);
    
    int mem[S];
    
    mem[0] = 0;
    
    for(i = 0; i < N; i++){
        scanf("%d",&tmp);
        
        if(mem[0] != 0){
            for(j = i; j >= 0; j--){
                if(tmp == mem[j])
                    mem[j] = mem[j-1];
                else
                    mem[j+1] = mem[j];
            }
        }else
            printf("!");
        mem[0] = tmp;
    }
    
    for(i = 0; i < S; i++){
        printf("%d",mem[i]);
    }
    return 0;
}

• 삽입정렬의 특성을 이용하였다.
• 입력값(기준)을 잡아서 한칸씩 인덱스를 뒤로 밀어내는 특성을 이용한다.
• 뿐만 아니라, 배열에서 자신보다 앞의 값들과 비교가 필요한 경우에서도 사용한다.

 

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98/dashboard