글 읽기 - 반례 좀 부탁드립니다.

9oo9leplex 1년 전 0

예제, 질문게시판 반례를 돌려보아도 다 맞는데 어떤 반례가 있는지 궁금합니다.

감사합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		Integer[] arr = new Integer[n];
		for(int i=0;i<n;i++) arr[i] = Integer.parseInt(st.nextToken());
		List<Integer> before = Arrays.asList(arr);
		
		Integer[] brr = arr.clone();
		Arrays.sort(brr, Collections.reverseOrder());
		List<Integer> after = Arrays.asList(brr);
		
		int s = Integer.parseInt(br.readLine());
		
		int arrIdx = 0, curIdx = 0,maxIdx; 
		int maxVal, tmp, dis;
		
		while(true) {
			
			if(s == 0 || curIdx == n) break;
			
			maxVal = after.get(curIdx);
			maxIdx = before.indexOf(maxVal);
			dis = Math.abs(maxIdx - arrIdx);
			
			if(dis > s) {
				curIdx++;
				continue;
			}
			
			for(int j=maxIdx;j>arrIdx;j--) {
				if(arr[j] > arr[j-1]) {
					tmp = arr[j-1];
					arr[j-1] = arr[j];
					arr[j] = tmp;
				}
			}
			
			s -= dis;
			arrIdx++;
			curIdx++;
			before = Arrays.asList(arr);
		}
		
		StringBuilder sb = new StringBuilder();
		for(int cur : arr) sb.append(cur).append(" ");
		System.out.println(sb.deleteCharAt(sb.length()-1));
	}
}

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

문제

문제

출처

ICPC

반례 좀 부탁드립니다.

9oo9leplex 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말