백준 JAVA 1021 분해합 리뷰

풀이

시간복잡도는 원소 삽입 O(N), indexOf 메서드 사용할때 O(N), 큐 회전 O(N)

시간 복잡도 O(N^3) N이 최대 50이니까 50*50*50=125000 이다

코드

/** 3주차
 * 1.BOJ 1021
 * 2.덱
 * 3.양방향으로 원소를 추가/삭제한다는 점, 끝에 있는 원소들만 추가/삭제하지 중간에 있는 원소들은 건드리지 않는다는점,
 * 덱을 이용했지만 덱의 내장함수로 인덱스를 구할 방법이 없는 것 같아서 링크드리스트 사용함
 * 4.O(N^3)
 */

/** 배운점
 * 1.덱을 STL로 구할거면 Deque<Integer> deque = new LinkedList<>() 만 생각했는데 이번에 내장함수 사용을 위해
 * LinkedList를 사용해서 문제를 푸니 고정된 사고를 벗어날 수 있었다.
 * 2.인덱스를 활용해서 푸는 문제로, 유동적인 부분을 잘 설정했어야했는데 유동적으로 변하는 인덱스, 배열 사이즈에 대한 고려가 좀 부족했다.
 * 유동적으로 변하는 LinkedList의 특징을 기억하면서 변수 설정을 잘 해야겠다.
 */

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        LinkedList<Integer> deque = new LinkedList<Integer>();

        for(int i=1; i<=n; i++){
            deque.add(i);
        }

        int count=0;
        st = new StringTokenizer(br.readLine());

        for(int i=0; i<m; i++){
            int target = Integer.parseInt(st.nextToken());

            while(true) {
                if (deque.getFirst() == target) {
                    deque.removeFirst();
                    break;
                }

                int target_index = deque.indexOf(target);
                int mid = 0;
                if (deque.size() % 2 == 1) { //홀수
                    mid = deque.size() / 2;
                }
                if (deque.size() % 2 == 0) { //짝수
                    mid = (deque.size() / 2)-1;
                }

                if (mid - target_index >= 0) { //mid값보다 왼쪽에 있음 - 2번 실행
                    deque.addLast(deque.removeFirst());
                    count++;
                }

                if (mid - target_index < 0) { //mid값보다 오른쪽에 있음 - 3번 실행
                    deque.addFirst(deque.removeLast());
                    count++;
                }
            }
        }

        System.out.println(count);

    }
}

 

바킹독 정답 코드 보고 개선한 코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        LinkedList<Integer> deque = new LinkedList<Integer>();

        for(int i=1; i<=n; i++){
            deque.add(i);
        }

        int count=0;
        st = new StringTokenizer(br.readLine());

        for(int i=0; i<m; i++){
            int target = Integer.parseInt(st.nextToken());

            while(deque.getFirst() != target) {
                int target_index = deque.indexOf(target);

                if(target_index<deque.size()-target_index){
                    deque.addLast(deque.removeFirst());

                }else{
                    deque.addFirst(deque.removeLast());

                }
                count++;
            }
            deque.removeFirst();
        }

        System.out.println(count);

    }
}

 

참고1

참고2

참고3