[10974] 모든 순열

import java.io.IOException;

import java.util.*;

class Swap {

int depth;

int changeIndex;

public Swap(int depth, int changeIndex) {

this.depth = depth;

this.changeIndex = changeIndex;

}

public int getDepth() {

return depth;

}

public void setDepth(int depth) {

this.depth = depth;

}

public int getChangeIndex() {

return changeIndex;

}

public void setChangeIndex(int changeIndex) {

this.changeIndex = changeIndex;

}

}

public class 모든수열 {

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

int[] zeroToInputNumberList = InputValueMakeArrAndReturn();

zeroToInputNumberList = InsertValueZeroToInputNumberListAndReturnList(zeroToInputNumberList);

calcRecursionZeroToInputNumberList(zeroToInputNumberList, 0);

}

public static int[] InputValueMakeArrAndReturn(){

Scanner scan = new Scanner(System.in);

return new int[scan.nextInt()];

}

public static int[] InsertValueZeroToInputNumberListAndReturnList(int[] zeroToInputNumberList){

for(int i = 0; i < zeroToInputNumberList.length; i++){

zeroToInputNumberList[i] = i + 1;

}

return zeroToInputNumberList;

}

public static void calcRecursionZeroToInputNumberList(int[] zeroToInputNumberList, int paramDepth){

// 끝까지 다돌았으면 출력

if( paramDepth == zeroToInputNumberList.length){

printZeroToInputNumberList(zeroToInputNumberList);

}

for(int changeIndex = paramDepth; changeIndex < zeroToInputNumberList.length; changeIndex++){

// clean code에서 함수 인자 3개 이상이면 클래스 변수를 생각해보라해서 클래스변수 사용

calcRecursionZeroToInputNumberList( swapAndReturnDeepCopy( zeroToInputNumberList, new Swap(paramDepth, changeIndex) ),

paramDepth + 1 );

}

}

public static int[] swapAndReturnDeepCopy(int[] zeroToInputNumberList, Swap swapInstanceDepthAndChangeIndex){

int depth = swapInstanceDepthAndChangeIndex.getDepth();

int changeIndex = swapInstanceDepthAndChangeIndex.getChangeIndex();

int temp = zeroToInputNumberList[depth];

zeroToInputNumberList[depth] = zeroToInputNumberList[changeIndex];

zeroToInputNumberList[changeIndex] = temp;

// 다른 사람들의 코드를 보면 원래대로 다시 swap을 시켜주지만 오름차순이 되지않아서 그냥 deep copy로 새로운 배열 생성후 리턴

return deepCopy(zeroToInputNumberList);

}

public static void printZeroToInputNumberList(int[] zeroToInputNumberList){

for(int i = 0; i < zeroToInputNumberList.length; i++){

System.out.print(zeroToInputNumberList[i] + " ");

}

System.out.println();

}

public static int[] deepCopy(int[] arr){

if( arr == null) return null;

int[] copyArr = new int[arr.length];

System.arraycopy(arr, 0, copyArr, 0, arr.length);

return copyArr;

}

}

클린 코드에 맞게 이름은 서술적으로 작성하고 클래스 변수를 사용하는 등 

조금 노력을해서 작성해보았다 

이거 푸는데 약 2일.. 정도 걸린듯

import java.io.BufferedWriter;

import java.io.IOException;

import java.io.OutputStreamWriter;

import java.util.*;

class Swap {

int depth;

int changeIndex;

public Swap(int depth, int changeIndex) {

this.depth = depth;

this.changeIndex = changeIndex;

}

public int getDepth() {

return depth;

}

public void setDepth(int depth) {

this.depth = depth;

}

public int getChangeIndex() {

return changeIndex;

}

public void setChangeIndex(int changeIndex) {

this.changeIndex = changeIndex;

}

}

public class Main {

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

int[] zeroToInputNumberList = InputValueMakeArrAndReturn();

zeroToInputNumberList = InsertValueZeroToInputNumberListAndReturnList(zeroToInputNumberList);

ArrayList<Object> noOverlapZeroToInputNumberList = new ArrayList<>();

calcRecursionZeroToInputNumberList(zeroToInputNumberList, noOverlapZeroToInputNumberList, 0);

//printNoOverlapZeroToInputNumberList(noOverlapZeroToInputNumberList);

}

public static int[] InputValueMakeArrAndReturn(){

Scanner scan = new Scanner(System.in);

return new int[scan.nextInt()];

}

public static int[] InsertValueZeroToInputNumberListAndReturnList(int[] zeroToInputNumberList){

for(int i = 0; i < zeroToInputNumberList.length; i++){

zeroToInputNumberList[i] = i + 1;

}

return zeroToInputNumberList;

}

public static void calcRecursionZeroToInputNumberList(int[] zeroToInputNumberList, ArrayList<Object> noOverlapZeroToInputNumberList,  int paramDepth){

if(checkOverlapZeroToInputNumberList(zeroToInputNumberList, noOverlapZeroToInputNumberList)){

noOverlapZeroToInputNumberList.add( deepCopy(zeroToInputNumberList) );

}

for(int changeIndex = paramDepth; changeIndex < zeroToInputNumberList.length; changeIndex++){

calcRecursionZeroToInputNumberList( swapAndReturnDeepCopy( zeroToInputNumberList, new Swap(paramDepth, changeIndex) ), noOverlapZeroToInputNumberList, paramDepth + 1 );

}

}

public static int[] swapAndReturnDeepCopy(int[] zeroToInputNumberList, Swap swapInstanceDepthAndChangeIndex){

int depth = swapInstanceDepthAndChangeIndex.getDepth();

int changeIndex = swapInstanceDepthAndChangeIndex.getChangeIndex();

int temp = zeroToInputNumberList[depth];

zeroToInputNumberList[depth] = zeroToInputNumberList[changeIndex];

zeroToInputNumberList[changeIndex] = temp;

return deepCopy(zeroToInputNumberList);

}

public static boolean checkOverlapZeroToInputNumberList(int[] zeroToInputNumberList, ArrayList<Object> noOverlapZeroToInputNumberList){

int noOverlapZeroToInputNumberListSize = noOverlapZeroToInputNumberList.size();

for(int i = 0; i < noOverlapZeroToInputNumberListSize; i++){

if( Arrays.equals(zeroToInputNumberList, (int[]) noOverlapZeroToInputNumberList.get(i))){

return false;

}

}

printZeroToInputNumberList(zeroToInputNumberList);

return true;

}

public static void printNoOverlapZeroToInputNumberList(ArrayList<Object> noOverlapZeroToInputNumberList) throws IOException{

BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int noOverlapZeroToInputNumberListSize = noOverlapZeroToInputNumberList.size();

for(int i = 0; i < noOverlapZeroToInputNumberListSize; i++){

int[] noOverlapZeroToInputNumberListGetIndexI = (int[])noOverlapZeroToInputNumberList.get(i);

for(int j = 0; j < noOverlapZeroToInputNumberListGetIndexI.length; j++){

bw.write(noOverlapZeroToInputNumberListGetIndexI[j] + " ");

bw.flush();

}

System.out.println();

}

bw.close();

}

public static void printZeroToInputNumberList(int[] zeroToInputNumberList){

for(int i = 0; i < zeroToInputNumberList.length; i++){

System.out.print(zeroToInputNumberList[i] + " ");

}

System.out.println();

}

public static int[] deepCopy(int[] arr){

if( arr == null) return null;

int[] copyArr = new int[arr.length];

System.arraycopy(arr, 0, copyArr, 0, arr.length);

return copyArr;

}

}

위 코드는 최초로 짰던 코드  순열 알고리즘을 이해하고는있었으나

중복으로 출력되는경우를 막기위해서 지나친 deep copy를 이용하여 했기때문에 속도가 나오지않았음

새로운 arrayList에다 하나씩 넣고 중복되었는지 체크하면서 했기때문에

위 사진하나면 순열 알고리즘을 이해할수있다

최초 A를 기준으로 A -> A ,  A -> B,  A -> C 순으로 바꾸면 2번째줄처럼 되고

첫번째를 기준으로 다 바꿨으니 그다음은 두번째를 기준으로 

B -> B, B -> C    

A -> A, A -> C

B -> B, B -> A

이런식으로 바꾸면 된다

쉬운줄 알고 접근했다가 존나 어렵게 느껴진 문제다