글 읽기 - 예외 케이스가 궁금합니다

citizen 7년 전 0

arr의 제일 뒤에서 한단계 전 부분부터 시작해서

해당 위치 뒤쪽에 있는 숫자중 현재자리값보다 작은 값을 가진 자리가 있으면

두 개의 값을 바꿔준뒤 현재 자리 뒤쪽부터 내림차순으로 정렬을 시켰습니다.

글로는 어려우니 예시를 들자면

5 3 4 1 2 5 라는 배열이 있을 때

제일 뒤쪽에서부터 시작하여 자기보다 뒤에 있는 수가

자신보다 작은 경우가 최초로 발견되는 경우는 4입니다.(1, 2, 5는 그렇지 않으니까요)

특히 작은 숫자들 중에서도 제일 뒤쪽에 위치한 수는 '2'이므로

2와 4를 서로 바꾸어 5 3 2 1 4 5 라는 배열을 만들고

4가 발견된 자리가 index상으로는 2번이니 3번자리부터 끝부붙까지만 내림차순으로 정렬하면

5 3 2 5 4 1이 됩니다.

이 방법을 역으로 이용하여 10972번인 '다음수열' 문제는 해결했는데요.

이 문제는 잘 넘어가질 않더군요..

어디가 문제일까요?

import java.util.*;

import java.awt.List;
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 void main(String args[]) throws IOException{
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(br.readLine());
        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for(int i = 0; i < n; i++){
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        int max = -1;
        int place = -1;
        for(int i = n-2; i >= 0; i--){
        	for(int j = n-1; j >= i+1; j--){
        		if(arr[j] < arr[i]){
        			if(max < j){
        				max = j;
        				place = i;
        			}
        		}
        	}
        }
        if(place == -1) bw.write("-1\n");
        else{
        	int temp = arr[max];
        	arr[max] = arr[place];
        	arr[place] = temp;
        	for(int i = place+2; i < n; i++){
        		for(int j = i; j > place+1; j--){
        			if(arr[j] < arr[j-1]) break;
        			else{
        				int tp = arr[j];
        				arr[j] = arr[j-1];
        				arr[j-1] = tp;
        			}
        		}
        	}
        	for(int i = 0; i < n; i++){
        		bw.write(arr[i]+" ");
        	}
        }
        bw.close();
    }
 
}

zlzmsrhak 7년 전 1

반례입니다. 분석해보세요.

4
4 2 1 3

citizen 7년 전 0

단순 알고리즘 오류였더군요

제가 설명해놓고 그대로 소스를 짜지 않았다니..

아무튼 도움주신 덕분에 해결됬습니다.

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