백준 21756번 : 지우개 | 자바 풀이

[ Solution ]

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

public class Main {

    public static void main(String[] args) throws IOException {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        ArrayList<Integer> arr = new ArrayList<>();

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

        while(arr.size() >= 2) {
            for(int i = 0; i < arr.size(); i++) {
                arr.remove(i);
            }
        }

        System.out.println(arr.get(0));
    }
}

배열로 풀면 시간초과가 나서 ArrayList로 풀어야한다.
배열과 ArrayList의 차이점은 배열의 크기는 고정이지만 ArrayList의 크기는 변할 수 있다.

이 점을 잘 활용하면 좋은데,
위의 코드의 for문에서 i번째를 지우면 자동으로 앞으로 이동되어 홀수 번째 수를 지울 수 있고,
이를 ArrayList의 사이즈가 2보다 작을 때까지(즉, 1이 될때까지) 해주면 된다.
직접 손으로 써보면 이해가 빠르다.