[백준/Java] 25400번 제자리

-Code

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

public class BOJ25400 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int cnt = Integer.parseInt(br.readLine());
        // 숫자 받기
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] nums = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            int num = Integer.parseInt(st.nextToken());
            nums[i] = num;
        }
        // 뺄 숫자 계산
        int answer = 0, now = 1;
        for (int i = 0; i < cnt; i++) {
            // 현재 값과 다르면 넘어감
            if (nums[i] != now) {
                continue;
            }
            // 맞는 수이므로 answer + 1하고 다름 수로 변경
            answer++;
            now++;
        }
        System.out.println(cnt - answer);
    }
}

 

ArrayList로 index를 기준으로 remove하려고 했으나 그러면 O(n^2)나와서 문제가 되었습니다. 그래서 now로 따로 계산하여 비교하라는 힌트를 얻고 다르면 다음 index로 넘어가고 맞으면 now와 answer를 증가하는 식으로 해결했습니다