[인프런_정렬] 4. Least Recently Used

<<풀이>>

 

-나의 풀이-

 

시간 복잡도 : O(N^3)

 

이 문제를 푼 핵심은 세 가지가 있다.

 

1. 우선, 어떠한 규칙이 작동하는지를 파악하고 그 원리 대로 코드를 구현하려고 했다.(사용했던 것을 재 사용하게 되면 그것은 히트이고 원래 그값의 위치에서 부터 오른쪽에서 왼쪽으로  값을  오른쪽으로 이동시킨다. 만약 같은 것이 없고 새로운 값이 들어오게 되면 맨 오른쪽부터 시작해서 값을 오른쪽으로 이동시킨다. ), 이전 부터 사용하던 tmp를 임시적으로 사용했다.

 

2. 시간 복잡도가 큰 만큼 어느 상황에서 break를 걸어줬다.

 

3. boolean run을 사용해서 필요할 때만 코드가 돌아가게 설정했다.

 

 

import java.util.Scanner;

class Main {
    private int[] solution(int n, int[] arr) {
        int[] brr = new int[n];
        int tmp = 0;

        for(int i = 0; i < arr.length; i++) {
            tmp = arr[i];
            boolean run = true;
            for (int j = 0; j < brr.length; j++) {
                if (brr[j] == tmp) {
                    for (int k = j - 1; k >= 0; k--) {
                        brr[k + 1] = brr[k];
                    }
                    brr[0] = tmp;
                    run = false;
                    break;
                }
            }
            if (run) {
                for (int z = brr.length - 1; z >= 1; z--) {
                    brr[z] = brr[z - 1];
                }
                brr[0] = tmp;

            }
        }
        return brr;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[m];
        for(int i = 0; i < m; i++) {
            arr[i] = in.nextInt();
        }
        for(int x : T.solution(n, arr)) System.out.print(x + " ");
    }
}

 

-강사님 풀이-

 

import java.util.Scanner;

class Main {
    private int[] solution(int size, int n, int[] arr) {
       int[] cache = new int[size];
       for(int x : arr) {
           int pos = -1;
           for(int i = 0; i < size; i++) if(x == cache[i]) pos = i;
           if(pos == -1) {
               for(int i = size - 1; i >= i; i--) {
                   cache[i] = cache[i - 1];
               }
               cache[0] = x;
           } else {
               for(int i = pos; i >= 1; i--) {
                   cache[i] = cache[i - 1];
               }
               cache[0] = x;
           }
       }
       return cache;
    }


    public static void main(String[] args) {
        Main T = new Main();
        Scanner in = new Scanner(System.in);
        int s = in.nextInt();
        int n = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        for(int x : T.solution(s, n, arr)) System.out.print(x + " ");
    }
}

 

나랑 전체적인 풀이 방식은 같지만 강사님은 if else 를 사용해서 코드를 구성했다.

 

큰 차이는 없지만 또 다른 풀이 방식을 보며 오늘도 배워간다 ~~!!