본문 바로가기
코딩테스트/JAVA

[백준 JAVA] 회귀한 프로그래머의 순열 문제 다시 풀기

신동운 2025. 7. 31. 17:46

 

다음 순열문제를 다시 풀어보려한다. 

 

다풀고 느낀점1: 시간 계산 철저히하고 아직까진 뭐 괜찮지만 가급적이면 설계 부터 하고 코드짜는 습관 들이기

다풀고 느낀점2: 역시 이거 예전에도 하기 싫어서 대충보고 넘어갔는데 역시나 기억이 안난다. 그래도 다시 보니까 이해는 빠르게 되서 다행이라고 생각한다. 정진하자.

 

다음순열

1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오.

사전 순으로 가장 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다.

 

왠지 이전에도 이렇게 풀어서 틀린것같은데 똑같은 실수를 한것같다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[] arr, arr2, visited;
    public static boolean check;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        arr = new int[N];
        arr2 = new int[N];
        visited = new int[N + 1];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dfs(0);

        if(sb.length() == 0){
            sb.append(-1);
        }

        System.out.println(sb);
    }
    public static void dfs(int depth){
        if(depth == N){
            if(check){
                for(int a : arr2){
                    sb.append(a).append(" ");
                }
                check = false;
                return;
            }
            for(int i = 0; i < N; i++){
                if(arr[i] != arr2[i]) return;
            }
            check = true;

            return;
        }

        for(int i = 1; i <= N; i++){
            if(visited[i] == 1) continue;
            arr2[depth] = i;
            visited[i] = 1;
            dfs(depth + 1);
            visited[i] = 0;
        }
    }
}

 

가장 단순하게 dfs 를 이용해서 비교해서 다음 순열이 있을 경우 다음 dfs 에서 출력하는 식으로 코드를 짰는데 시간초과가 났다.

 

다른 방법으로는 순열이기 때문에 dfs말고 다른방법으로 구하고 출력하는 방법이 있었던거 같은데 우선 기억이 안난다.

 

그리고 체크해볼점은 원래는 문제를 풀기전에 설계를 마치고 시간계산을 한 뒤 코드를 짰던거 같은데 오랜만에 하니까 이 과정을 생략하고 문제부터 푸는 다시 나쁜 버릇이 생겼다. 다시 생각해보면

 

시간 제한은 1초이고 연산은 1억번으로 대충 생각해봤을때

N(1 ≤ N ≤ 10,000) 입력 N의 범위가 다음과 같으므로 최악의 경우 N이 10000일때 dfs 로 계산을 모두 한다면 시간은 O(N!)이 걸리게 되고 정확히 계산해보지 않더라도 N이 12만 되어도 12! = 479001600 이기 때문에 1억을 훌쩍 넘어버린다.

 

즉 이 문제는 처음 봤을때 부터 dfs 순열로는 풀 수 없었던 문제

 

따라서 다음 순열을 계산하기 위해 특별한 알고리즘을 사용해야 하는것을 알 수 있다.

 

다음 순열 계산하는 방법 중 하나는 Next Permutation 을 배웠는데 한번 되새기며 다시 코드를 짜보았다.

 

  • 현 순열에서 사전 순으로 다음 순열 생성 - NextPermutation
  • 알고리즘
    • 배열을 오름차순으로 정렬한 후 시작한다.
    • 아래 과정을 반복하여 사전 순으로 다음으로 큰 순열 생성(가장 큰 내림차순 순열을 만들 때까지 반복한다.)
      1. 뒤쪽부터 탐색하며 교환위치(i-1)찾기(i : 꼭대기)
      2. 뒤쪽부터 탐색하며 교환위치(i-1)와 교환할 큰 값 위치(j) 찾기
      3. 두 위치 값(i-1,j)교환
      4. 꼭대기 위치(i)부터 맨 뒤까지 오름차순 정렬
  • 주의사항
    • NextPermutation 사용 전에 숫자배열을 오름차순으로 정렬하여 가장 작은 순열 한번 처리
		Scanner sc  = new Scanner(System.in);
		int N = sc.nextInt();;
		int[] input = new int[N];;
		
		for(int i =0;i<N;i++) {
			input[i] = sc.nextInt();
		}
		
		Arrays.sort(input); // 오름차순 정렬
		
		do {
			System.out.println(Arrays.toString(input));
		}while(np(input));
		
	}
	static boolean np(int[] p) { // boolean : true(다음순열 존재), false(다음순열 없음)
		
		int N = p.length;
		// step1) 꼭대기 찾기
		int i = N-1;
		while(i>0 && p[i-1] >= p[i]) --i;
		
		if(i==0) return false;
		
		// step2) 꼭대기 앞 교환위치에 교환할 값(i-1위치 값보다 큰 값중 가장 작은 값) 자리 찾기
		int j = N-1;
		while(p[i - 1] >= p[j]) --j;
		
		// step3) 두 위치의 수 교환
		swap(p, i-1, j);
		
		// step4) 꼭대기부터 맨 뒤까지 오름차순의 형태로 만듦
		int k = N-1;
		while(i<k) {
			swap(p, i++, k--);
		}
		return true;
		
	}
	
	static void swap(int[] p, int i, int j) {
		int temp = p[i];
		p[i] = p[j];
		p[j] = temp;
		
	}

 

정답 코드는 다음과 같다

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[] arr;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        np(arr);

        System.out.println(sb);
    }

    public static void np(int[] p) {

        int i = N - 1;
        while(i > 0 && p[i-1] >= p[i]) --i;

        if(i == 0) {
            sb.append(-1);
            return;
        }

        int j = N - 1;
        while(p[i - 1] >= p[j]) --j;

        swap(p, i-1, j);

        int k = N - 1;
        while(i < k) {
            swap(p, i++, k--);
        }

        for(int t = 0; t < N; t++){
            sb.append(arr[t]).append(" ");
        }
    }

    public static void swap (int[] p, int i, int j) {
        int temp = p[i];
        p[i] = p[j];
        p[j] = temp;
    }
}

 

이런식으로 사용하면 실행시간은 최대 O(N) 만큼 든다. 

이전순열

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[] arr;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        np(arr);

        System.out.println(sb);
    }

    public static void np(int[] p) {

        int i = N - 1;
        while(i > 0 && p[i-1] <= p[i]) --i;

        if(i == 0) {
            sb.append(-1);
            return;
        }

        int j = N - 1;
        while(p[i - 1] <= p[j]) --j;

        swap(p, i-1, j);

        int k = N - 1;
        while(i < k) {
            swap(p, i++, k--);
        }

        for(int t = 0; t < N; t++){
            sb.append(arr[t]).append(" ");
        }
    }

    public static void swap (int[] p, int i, int j) {
        int temp = p[i];
        p[i] = p[j];
        p[j] = temp;
    }
}

 

 

바뀐부분은 조건문이 달라졌다.

while(i > 0 && p[i-1] <= p[i])

 

while(p[i - 1] <= p[j])

 

기존에는 >= 로 피봇값을 찾을때도 뒤에서부터 이전이 작아지면 종료

 

j 값 즉 뒤에서부터 피봇보다 더 큰값 중 가장 작은 값을 찾으면 종료 이런식으로 했는데

 

이전 수열이니까 두에서부터 이전이 커지면 종료 피봇보다 작은값중 가장 큰 값을 찾으면 종료한다.

 

모든 순열

 

모든 순열은 아까와 같은 것을 반복하면 된다.

 

기존 문제와는 달리 N 이 8까지 이므로 dfs나 반복문을 사용해서 풀어도 괜찮지만 시간이 얼마나 달라지는 것을 확인하기 위해 NextPermutation 을 이용해서도 풀어보고 시간이 얼마나 차이나는지 알아보자.

 

우선 dfs

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[] arr, visited;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        arr = new int[N];
        visited = new int[N + 1];

        dfs(0);

        System.out.println(sb);
    }

    public static void dfs(int depth) {

        if(depth == N){
            for(int a : arr){
                sb.append(a).append(" ");
            }
            sb.append("\n");
        }

        for(int i = 1; i <= N; i++) {
            if(visited[i] == 1) continue;
            arr[depth] = i;
            visited[i] = 1;
            dfs(depth + 1);
            visited[i] = 0;
        }
    }
}

 

 

다음은 NextPermutation

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static int N;
    public static int[] arr;
    public static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        arr = new int[N];
        for(int i = 1; i <= N; i++){
            arr[i - 1] = i;
        }

        do {
            for(int a : arr){
                sb.append(a).append(" ");
            }
            sb.append("\n");
        }while(np(arr));

        System.out.println(sb);
    }

    public static boolean np(int[] p) {
        int i = N - 1;
        while((i > 0) && p[i-1] >= p[i]) --i;
        if(i == 0) return false;

        int j = N - 1;
        while(p[i-1] >= p[j]) --j;
        swap(p, i - 1, j);

        int k = N - 1;
        while(i < k) {
            swap(p, i++, k--);
        }

        return true;
    }
    public static void swap(int[] p, int i, int j){
        int temp = p[i];
        p[i] = p[j];
        p[j] = temp;
    }

}

 

아래가 dfs 로 푼거고 위에가 NP로 푼건데 N 값이 작아서그런지 크게 차이나진 않는 모습 하지만 유의미하게 작긴하다.

 

 

저작자표시 비영리 변경금지 (새창열림)

'코딩테스트 > JAVA' 카테고리의 다른 글

[백준 JAVA] 회귀한 프로그래머의 재귀 다시풀기  (0) 2025.08.14
[백준 JAVA] 회귀한 프로그래머의 순열 응용 문제 다시 풀기  (3) 2025.08.04
[백준 JAVA] 회귀한 프로그래머의 N과 M 다시풀기  (3) 2025.07.30
[백준 JAVA] 1697번: 숨바꼭질  (0) 2025.01.06
[백준 JAVA] 1012번: 유기농 배추  (0) 2025.01.06

'코딩테스트/JAVA' Related Articles

티스토리툴바