백준_3231 카드놀이(자바) / 구현

시간 & 메모리 제한

문제

입력 & 출력

실패 코드....

package com.Back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Back_3231 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int ans=0;
		int num = 1;
		for (int i = 0; i < N; i++) {
			arr[i]=Integer.parseInt(br.readLine());
		}
		
		while(true) {
			if(num==N+1) break;
			for (int i = 0; i < N; i++) {
				if(arr[i]==num) num++;
			}
			ans++;
		}
		System.out.println(ans-1);
	}
}

처음에는 실버 2여서 간단하게 생각하여 완탐으로 문제를 풀었습니다. 그런데 시간초과 문제가 발생했습니다.

 

정수의 갯수가 10만개 이기 때문에 while + for문은 100억개를 처리하다 보니 시간 초과가 발생했습니다.

구현을 통한 문제풀이

package com.Back;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Back_3231 {
	public static void main(String[] args) throws NumberFormatException, IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int ans=0;
		int [] arr = new int[N+1];
		for (int i = 0; i < N; i++) {
			int temp = Integer.parseInt(br.readLine());
			arr[temp] = i;
		}

		for (int i = 1; i <= N; i++) {
			if(arr[i-1]>arr[i]) {
				ans++;
			}
		}
		System.out.println(ans);
	}
}

- 이 문제를 해결 하기 위해서 한번에 돌면서 언제 한번 더 돌게 되는지를 생각해 봐야 합니다.

 

- 앞 뒤 숫자를 비교 해봤을 때, 앞의 숫자가 뒤의 숫자보다 더 큰경우는 다시 앞으로 가야 한다는 사실을 알게 됬습니다.

 

- 따라서 for문을 돌려서 arr[i-1]> arr[i] 인 경우에 대해서 체크를 해줬습니다.