🎲 [백준] 10804번. 카드 역배치(Java) feat.LinkedList

문제

https://www.acmicpc.net/problem/10804

 

 

문제 풀이

 

문제의 풀이 자체는 굉장히 간단하다. 

1 ~ 20까지의 숫자가 주어진 배열이 있고 그 배열에서 원하는 인덱스 범위를 역방향으로 만드는데 그 행위를 총 10번 하는 것이다.

 

그리고 그 결과를 나타나게 한다.

 

처음에 문제를 풀때 그냥 이분법 처럼 lt와 rt를 나눠서 서로 방향을 바꿔서 문제를 풀었다.

하지만 갑자기 번뜩 생각난 것이 "배열의 중간에 있는 값들의 삽입과 삭제가 빈번하게 일어나는 문제" 인것이다

 

그래서 평소에 사용하고 싶었던 LinkedList를 사용해서 문제를 풀어보았다.

 

사용하기 전에 두 배열을 구성하는 방법에서 차이를 알아보자

	Array	LinkedList
메모리 할당	연속적인 메모리 블록에 할당	비연속적인 메모리 블록에 할당
접근 시간	O(1)	O(n)
삽입/삭제 시간	O(n)	O(1)
크기 변경	크기 변경이 쉽지 않다	크기 변경이 용이

 

 

1. Array를 사용한 문제 풀이

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int[] arr = new int[] {
                0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20
        };

        for (int i = 0; i < 10; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int lt = Integer.parseInt(st.nextToken());
            int rt = Integer.parseInt(st.nextToken());
            while (lt < rt) {
                int tmp = arr[lt];
                arr[lt] = arr[rt];
                arr[rt] = tmp;
                lt++;
                rt--;
            }
        }

        for (int i = 1; i < 21; i++) {
            System.out.print(arr[i] + " ");
        }

2. LinkedList를 사용한 문제 풀이

 

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        List<Integer> list = new LinkedList<>(
                Arrays.asList(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20)
        );

        for (int i = 0; i < 10; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int lt = Integer.parseInt(st.nextToken());
            int rt = Integer.parseInt(st.nextToken());
            int count = rt - lt;
            for (int j = 0; j < count; j++) {
            	// 중간에 값을 넣어주는 것이기 때문에
                list.add(lt++, list.get(rt));
                // 밀린 위치에 값을 지워주어야 한다.
                list.remove(rt + 1);
            }
        }

        for (int i = 1; i < list.size(); i++) {
            System.out.print(list.get(i) + " ");
        }​

 

결과

사실 욕심이였다. 그냥 Array로 푸는 것이 훨씬 효율적이다. 데이터를 삭제하는 것도 아니고 사이에 우겨넣는것도 아니라서 LinkedList와 Array를 정확하게 비교하는 문제는 아니였다...

하지만 이번에 두 개의 차이점을 한번 더 복기하는 느낌이였어서 좋았다. 

 

근데 놀랍게도 LinkedList가 더 빨랐다. 그 이유가 뭘까? 사실 모르겠다... 아시는 분 댓글로 알려주시면 너무너무 감사합니다