글 읽기 - 데이터 중 잘못된게 있는것 같습니다.

citizen 7년 전 0

아래 두 코드의 결과가 다릅니다.

22번째 줄처럼 n개의 인풋을 받는 방식을 사용하면 런타임에러가 생기는데

74번째 줄처럼 버퍼에 입력이 남아있을때까지 인풋을 계속 받는 방식으로 바꾸었더니 통과가 되었습니다.

즉, 인풋으로 들어오는 순열의 원소가 주어진 순열 길이 N 보다 더 적거나 많이 들어오는 데이터가 있는 것 같습니다.

//////////////////////////////////////////////////// 1번 코드
import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main{
    public static BufferedReader br = 
            new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = 
            new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static int[] Visited, arr;
    public static int n, place, max, p, size = 1;
    
    public static void main(String args[]) throws IOException{
        // Scanner sc = new Scanner(System.in);
        StringTokenizer st;
    	n = Integer.parseInt(br.readLine());
    	Visited = new int[200001];
    	arr = new int[200001];
    	st = new StringTokenizer(br.readLine(), " ");
    	for(place = 0; place < n; place++) arr[place] = Integer.parseInt(st.nextToken());
		max = arr[0];
		Visited[1] = arr[0];
		for(place = 1; place < n; place++){
        	if(arr[place] > max) {
        		max = arr[place];
        		size++;
        		Visited[size] = arr[place];
        	}else if(arr[place] == max) continue;
        	else if(arr[place] < Visited[1]) Visited[1] = arr[place];
        	else{
        		p = find(1, size);
        		if(p == -1) continue;
        		if(p == size-1) max = arr[place];
        		Visited[p+1] = arr[place];
        	}
        }
        bw.write(n-size+"\n");
        bw.close();
    }
    
    public static int find(int start, int end){
    	int middle = (start+end)/2;
    	if(Visited[middle] == arr[place]) return -1;
    	else if(middle == start) return middle;
    	else if(Visited[middle] < arr[place]) return find(middle, end);
    	else return find(start, middle);
    }
}

///////////////////////////////////////////////////////// 2번 코드
import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main{
    public static BufferedReader br = 
            new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter bw = 
            new BufferedWriter(new OutputStreamWriter(System.out));
    
    public static int[] Visited, arr;
    public static int n, place, max, p, size = 1;
    
    public static void main(String args[]) throws IOException{
        // Scanner sc = new Scanner(System.in);
        StringTokenizer st;
    	n = Integer.parseInt(br.readLine());
    	Visited = new int[200001];
    	arr = new int[200001];
    	st = new StringTokenizer(br.readLine(), " ");
    	place = 0;
    	while(st.hasMoreTokens()) arr[place++] = Integer.parseInt(st.nextToken());
		max = arr[0];
		Visited[1] = arr[0];
		for(place = 1; place < n; place++){
        	if(arr[place] > max) {
        		max = arr[place];
        		size++;
        		Visited[size] = arr[place];
        	}else if(arr[place] == max) continue;
        	else if(arr[place] < Visited[1]) Visited[1] = arr[place];
        	else{
        		p = find(1, size);
        		if(p == -1) continue;
        		if(p == size-1) max = arr[place];
        		Visited[p+1] = arr[place];
        	}
        }
        bw.write(n-size+"\n");
        bw.close();
    }
    
    public static int find(int start, int end){
    	int middle = (start+end)/2;
    	if(Visited[middle] == arr[place]) return -1;
    	else if(middle == start) return middle;
    	else if(Visited[middle] < arr[place]) return find(middle, end);
    	else return find(start, middle);
    }
}

baekjoon 7년 전 0

수정했습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

데이터 중 잘못된게 있는것 같습니다.

citizen 7년 전 0

baekjoon 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말