글 읽기 - 다음 순열 틀린 이유 조언 부탁드립니다.

kimochi0523 3년 전 0

안녕하십니까!

이번에 다음 순열을 풀다 조건을 다 맞췄다고 생각을 했으나,

결과가 틀려, 이렇게 질문을 올립니다.

조건은 이렇게 생각해봤습니다.

( i - 1의 변수명 : nextChangeNumber, i의 변수명 : changeNumber, j의 변수명 : toChangeNumber)

1) numberArray[i - 1] < numberArray[i]를 만족하는 가장 큰 수를 찾습니다. Line 16.

2) j >= i && numberArray[j] > numberArray[i - 1]을 만족하며, 가장 큰 j를 찾습니다. Line 27.

3) numberArray[i - 1] 과 numberArray[j]를 스왑 합니다. Line 34.

4) 이후, 출력합니다. Line 41.

이 4가지 조건을 가지고 해봤으며, 테스트 결과는 맞게 잘 나오는데, 분명 제가 생각하지 못한 사례가 더 있을겁니다.

그걸 여쭤보고 싶고 어떻게 해결해야 정답으로 돌릴 수 있을지 궁금합니다!

부탁드리겠습니다.

import java.util.Scanner;
public class Main {
    int changeNumber;
    int nextChangeNumber;
    int toChangeNumber;
    int[] numberArray;
    int arrayLength;
    boolean isChangable = false;

    public Main(int[] numberArray){
        this.numberArray = numberArray;
        findChangeableNumber();
        makeNextSequence();
    }

    public void findChangeableNumber(){
        arrayLength = numberArray.length;
        for (int i = arrayLength - 1; i >= 1; i--){
            if (numberArray[i] > numberArray[i - 1]){
                changeNumber = i;
                nextChangeNumber = i - 1;
                isChangable = true;
                break;
            }
        }
    }
    public void findMax(){
        for (int i = nextChangeNumber; i < arrayLength; i++){
            if (numberArray[nextChangeNumber] < numberArray[i] && i >= changeNumber){
                toChangeNumber = i;
            }
        }
    }
    public void makeNextSequence(){
        if (isChangable == true){
            findMax();
            int temp = numberArray[nextChangeNumber];
            numberArray[nextChangeNumber] = numberArray[toChangeNumber];
            numberArray[toChangeNumber] = temp;

            for (int i = 0; i < arrayLength; i++){ System.out.print(numberArray[i] + " "); }
        }
        else { System.out.print("-1"); }
    }

    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int numberRange;
        numberRange = scanner.nextInt();
        int[] numberArray = new int[numberRange];
        for (int i = 0; i < numberRange; i++){ numberArray[i] = scanner.nextInt(); }
        Main main = new Main(numberArray);
    }
}

dldyddlwl 3년 전 2

반례]

4
2 1 4 3

글쓴이님의 코드] 2 3 4 1

실제 답 ] 2 3 1 4

왜 이렇게 나오게 된걸까요?

아래 findMax 메서드에서 저희는, nextChangeNumber보다 크다는 조건을 만족하는 동시에, changeNumber 뒤에 있을 가장 먼 값을 찾고자 합니다.

그렇다면, 위 예시, 2 1 4 3에서는, nextChangeNumber가 1이 됩니다. (changeNumber는 4 ), 그렇게 되면, 아래의 for문을 거친다면,

i는 nextChangeNumber( 1 )부터 끝까지 조사하면서, 가장 마지막에 있는 3을 toChangeNumber에 대입합니다.

그렇게 되면, 1과 3만을 바꿔, 2 3 4 1이 됩니다. 하지만, 2 1 4 3 의 다음 사전순인 2 3 1 4가 옳습니다.

이 부분을 참고해주세요!

public void findMax(){
        for (int i = nextChangeNumber; i < arrayLength; i++){
            if (numberArray[nextChangeNumber] < numberArray[i] && i >= changeNumber){
                toChangeNumber = i;
            }
        }
    }

kimochi0523 3년 전 0

감사합니다...
덕분에 힌트 얻어 풀긴 풀었네요..

감사합니다!

 public boolean checkISAsending(){
        for (int i = changeNumber; i < arrayLength - 1; i++){
            if (numberArray[i] > numberArray[i + 1]) { return false; }
        }
        return true;
    }

    public void sortNumber(){ Arrays.sort(numberArray, changeNumber, arrayLength); }

    public void makeNextSequence(){
        if (isChangable == true){
            findMax();
            int temp = numberArray[nextChangeNumber];
            numberArray[nextChangeNumber] = numberArray[toChangeNumber];
            numberArray[toChangeNumber] = temp;

            if (checkISAsending() == false){ sortNumber(); }

            for (int i = 0; i < arrayLength; i++){ System.out.print(numberArray[i] + " "); }
        }
        else { System.out.print("-1"); }
    }

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

문제

문제

출처

ICPC

다음 순열 틀린 이유 조언 부탁드립니다.

kimochi0523 3년 전 0

dldyddlwl 3년 전 2

kimochi0523 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말