All Permutation

문제 복기

내가 접근한 방식

1. ArrayList를 생성한다.

2. Next Permutation을 응용하여 생성되는 배열을 1의 ArrayList에 저장한다.

3. 입력값은 N이기 때문에 초기 배열을 하나 생성하여 NP함수에 전달해준다.

맞은 부분

3번에서 입력받은 N에 대해 초기배열을 생성하여 기존 함수에 인자로 전달한다.

틀린 부분(틀린 이유)

n=3인 경우, 123 132 213 231 312 321 이 출력되어야하는데 132만 출력되었다. 그 이유는 ap에서 다음 순열을 만들긴하지만 이 ap함수를 한번만 호출했기 때문에 바로 다음인 수열인 132만 출력 되었다. 이것은 1회성 호출이 아닌, Next Permutation에서 구현한 다음 순열 생성함수에서 true 또는 false를 리턴할 때 false가 아닐 때까지(true인 동안) 계속 반복해서 실행되어 다음 순열을 생성, 출력해야한다. 배열 또는 ArrayList를 리턴하도록 하고 싶고, 그리고 반복하는 조건을 걸어주기 위해 리턴 값(true 또는 false)를 이용하고 싶지만 한가지 함수에 대해 다음 순열에 해당하는 일거양득을 이룰 순 없다. 내가 생각한 방법대로 다음 순열을 계속해서 생성하여 ArrayList에 넣고, 출력하고 싶다면 반복하는 조건을 걸어주어야 한다.

public static int[] ap(int[] a) {
		int n = a.length;
		int i=n-1;
		//i를 찾는다.(바꿀 i-1을 찾는 것이다.)
		while(i>0 && a[i-1]>a[i]) {i-=1;}
		if(i<=0) {//전체 순열이 내림차순으로 되어있어 전체 순열이 마지막 순열인경우!
			return null;
		}
		//i를 찾고나서 i-1과 바꿀 j를 찾는다.
		int j=n-1;
		while(a[i-1]>a[j]) {j-=1;}
		int temp = a[i-1];
		a[i-1] = a[j];
		a[j] = temp;
		//i와 n-1 재정렬해서 오름차순으로 만들어준다!
		j = a.length-1;
		while(i<j) {//i==j라면 해줄필요 없음!
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			i+=1;j-=1;
		}
		//mylist.add(a);
		return a;
	}
	public static void main(String[] args) {
		Scanner sc  = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i=0;i<n;i++) {
			a[i] = i+1;
		}
		ap(a);
		for(int i=0;i<mylist.size();i++) {
			for(int j=0;j<mylist.get(i).length;j++) {
				System.out.print(mylist.get(i)[j]+" ");
			}
			System.out.println();
		}
		
	}

1. al.get(i)로 i번째 배열을 0부터 i.lenth까지 출력하는 코드

for(int i=0;i<ans.size();i++) {
		for(int j=0;j<ans.get(i).length;j++) {
				System.out.print(ans.get(i)[j]+" ");
			}
	System.out.println();
}

하지만 ArrayList 사용방법이 미숙하여 132가 출력되는 것이 다였다.

ArrayList 사용법을 익히고 보니, 제대로 사용하고 있었다. 다만 로직의 문제였다.

ArrayList를 쓰면 아무래도 코드가 길어지고 더 복잡해질 것 같기 때문에 이전의 함수를 활용하는 방법을 선택하기로 한다.

정답 코드

import java.util.*;
public class AllPermutation_answer {
	public static boolean np(int[] a) {
		int i=a.length-1;
		while(i>0 && a[i-1]>a[i]) {i-=1;}
		if(i<=0) {//전체 순열이 내림차순으로 되어있어 전체 순열이 마지막 순열인경우!
			return false;
		}
		//i를 찾고나서 i-1과 바꿀 j를 찾는다.
		int j=a.length-1;
		while(a[i-1]>=a[j]) {j-=1;}
		int temp = a[i-1];
		a[i-1] = a[j];
		a[j] = temp;
		//i와 n-1 재정렬해서 오름차순으로 만들어준다!
		j = a.length-1;
		while(i<j) {//i==j라면 해줄필요 없음!
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
			i+=1;j-=1;
		}
		return true;
	}
	public static void main(String[] args) {
		Scanner sc  = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		for(int i=0;i<n;i++) {
			a[i] = i+1;
		}
		do {//일단 첫번째 순열 먼저 출력해주고 다음 순열 함수호출해서 출력.
			for(int i=0;i<n;i++) {
				System.out.print(a[i]+" ");
			}
			System.out.println();
		} while(np(a));
	}

}