자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Sorting and Searching(정렬, 이분검색과 결정알고리즘)_Least Recently Used)

 

 

4. Least Recently Used

 

예시 입력 1 

5 9
1 2 3 2 6 2 3 5 7

예시 출력 1

7 5 3 2 6

 

 

각 문제 풀이에 대한 설명은 주석으로 달아놓음.

list로 풀수도 있지만, 왠만하면 정렬로 푸는 연습을 해라. 왜냐하면 코드 구현력이 어느정도인지 확인하기 위함이다.

문제에 대한 이해도가 중요했음,,

 

내가 푼 풀이 1 (ArrayList) - Time: 164ms Memory: 27MB

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class ListExample {
    public int[] solution(int size, int n, int[] arr) {
        int[] answer = new int[size];
        ArrayList<Integer> list = new ArrayList<>();

        for (int x : arr) {
            if (list.contains(x)) {
                // remove(int idx) 함수라서 indexOf()필요
                list.remove(list.indexOf(x));
                list.add(x);
            } else list.add(x);
        }
        int idx = 0;
        for (int i = list.size()-1; i >= 0; i--) {
            // 뒤에서부터 반복문 돌면서 -n개 만큼일 경우 break
            // 왜냐하면 n개 만큼 answer[] 집어넣어서 더 이상 필요 없음
            if (i == list.size()-1-size ) break;
            answer[idx++] = list.get(i);
        }
        return answer;
    }

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

 

내가 푼 풀이 2 (Stack) - Time: 190ms Memory: 27MB

import java.util.Scanner;
import java.util.Stack;

public class StackExample {
    public int[] solution(int size, int n, int[] arr) {
        int[] answer = new int[size];
        Stack<Integer> stack = new Stack<>();

        for (int x : arr) {
            if (stack.contains(x)) {
                // remove(int idx) 함수라서 indexOf()필요
                stack.remove(stack.indexOf(x));
                stack.push(x);
            } else stack.push(x);
        }
        for (int i = 0; i < n ; i++) {
            // i가 size만큼일 경우 브레이크
            // size가 3일 경우 왜냐하면 0 1 2 번째 인덱스는 answer에 넣고 3번째 인덱스일때 멈추기 위함
            if (i == size) break;
            answer[i] = stack.pop();
        }
        return answer;
    }

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

 

 

강의 풀이 (정렬) - Time: 161ms Memory: 27MB

LRU 알고리즘은 가장 오래 전에 사용되지 않은 데이터를 우선적으로 교체하는 방식으로 동작하는 캐시 교체 알고리즘입니다.

import java.util.Scanner;

public class Main {

    public int[] solution(int size, int n, int[] arr) {
        int[] cache = new int[size];
        for (int x : arr) {
            // x값이 캐시 배열에 있는지 없는지 살피기 위해 pos인덱스 변화 초기화
            int pos = -1;
            // 이미 캐시에 있다면 pos에 i 인덱스 재할당
            for (int i = 0; i < size; i++) {
                if (x == cache[i]) pos = i;
            }
            // 캐시 미스 상황( 값이 캐시배열에 없을때 )
            if (pos == -1) {
                // 뒤에서 부터 1까지 i가 순회한다
                for (int i = size - 1; i >= 1; i--) {
                    // 뒤쪽 부터 오니까 i지점에 i-1을 땡겨준다
                    cache[i] = cache[i - 1];
                }
                // 현재 들어올 작업은 최우선이라 0번에 넣기
                cache[0] = x;
            // 캐시 히트 상황 ( 값이 캐시배열에 없을때 )
            } else {
                // 히트난 지점부터 1까지만 돈다! (0는 히트값 넣어야 하므로)
                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 kb = new Scanner(System.in);
        int k = kb.nextInt();
        int n = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        for (int x : T.solution(k, n, arr)) {
            System.out.print(x + " ");
        }
    }
}