[Java] 알고리즘 문제풀기 1번문제

4자리 정수 가장 작은 값 구하기 알고리즘

import java.util.*;
public class AlgoFirstTask {
	List<Integer> myNumber=new LinkedList<Integer>();
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		AlgoFirstTask af=new AlgoFirstTask();
		System.out.println("4자리 수를 입력하시오");
		int num=sc.nextInt();
		af.splitNum(num);
		af.sortNum();
		System.out.println();
	}
	public void splitNum(int num) {
		if(num>0) {
			splitNum(num/10);
			myNumber.add(num%10);
		}		
	}
	
	public void sortNum() {
		Collections.sort(myNumber);// 오름차순 정렬
		Integer[] myN=myNumber.toArray(new Integer[3]);//배열 생성		
		if(myN[0]==0) {//첫번쨰 자리가 0일경우
			for(int i=1;i<myN.length;i++) {
				if(myN[i]!=0) {//다음자리가 0이 아닐경우 swap
					myN[0]=myN[i];
					myN[i]=0;
					break;
				}					
			}
		}
		int min=printNum(myN);
		Collections.reverse(myNumber);//내림차순
		Integer[] maxArr=myNumber.toArray(new Integer[3]);
		int max=printNum(maxArr);
		checkN(min,max,myN);
	}
	public void checkN(int min,int max,Integer[] myNum){
		myNumber.clear();
		while(min<=max) {
			int flag=0;
			splitNum(min);
			if(myNumber.contains(myNum[0])&&myNumber.contains(myNum[1])&&myNumber.contains(myNum[2])&&myNumber.contains(myNum[3])) {				
					System.out.print(min+"\t");					
			}
			min++;
			myNumber.clear();
		}
	}
	
	
	
	public int printNum(Integer[] num) {
		int pNum=num[0]*1000+num[1]*100+num[2]*10+num[3]*1;
		//System.out.println(pNum);
		return pNum;
	}
}

문제가 있다 내가 만약 입력한 수중에 중복된 숫자가 있다면 제대로 출력되지 않는다... 아직 이유를 모르겠다.

if(myNumber.contains(myNum[0])&&myNumber.contains(myNum[1])&&myNumber.contains(myNum[2])&&myNumber.contains(myNum[3])) {				
					System.out.print(min+"\t");					
			}

이 코드 상 하나가 false가 돼야 하는데 중복된 값을 넣으면 이상하게 같지 않는데도 불구하고 모든 값이 true로 반환한다..

생각해보면 contains함수에서 문제가 있는 거 같다...

이유를 알아냈다... 중복된 값을 입력하게 돼도 true가 반환되는 이유는 간단했다.. 말 그대로 그 중복된 수도 myNumber가 contains 하고 있기 때문에 true반환이 당연하다.. 수정해야겠다.

수정 방법은 역시 swap을 이용한 순열을 사용하는 것이다.

참고:https://bcp0109.tistory.com/14 

순열 Permutation (Java)

위 알고리즘을 토대로 이 문제에 적용시켜보았다.

코드가 많이 수정되고 오히려 더 짧아진 거 같다. 주말에 순열에 대한 공부를 더 열심히 해놓아야겠다.

import java.util.*;
public class AlgoFirstTask {
	List<Integer> myNumber=new LinkedList<Integer>();
	TreeSet<Integer> set=new TreeSet<Integer>();
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		AlgoFirstTask af=new AlgoFirstTask();
		System.out.println("4자리 수를 입력하시오");
		int num=sc.nextInt();
		af.splitNum(num);
		af.sortNum();
		System.out.println();
	}
	public void splitNum(int num) {
		if(num>0) {
			splitNum(num/10);
			myNumber.add(num%10);
		}		
	}
	
	public void sortNum() {
		Collections.sort(myNumber);// 오름차순 정렬
		Integer[] myN=myNumber.toArray(new Integer[3]);//배열 생성		
		perm(myN,0);
		for(Integer t:set) {
			if(t!=0) {
				System.out.print(t+"\t");
			}
			
		}
	}
	public void perm(Integer[] arr,int depth) {
		if(depth==4) {
			for(int i=0;i<4;i++) {
				if(arr[0]==0) {
					continue;
				}else {
					//System.out.print(arr[i]);
				}
			}
			set.add(printNum(arr));
			return;
		}
		
		for(int i=depth;i<4;i++) {
			swap(arr,depth,i);
			perm(arr,depth+1);
			swap(arr,depth,i);			
		}
	}
	public void swap(Integer[] arr,int depth,int i) {
		int temp=arr[depth];
		arr[depth]=arr[i];
		arr[i]=temp;
		
	}
	
	public int printNum(Integer[] num) {
		if(num[0]==0) {
			return 0;
		}
		int pNum=num[0]*1000+num[1]*100+num[2]*10+num[3]*1;
		return pNum;
	}
}