입력한 어떤 숫자보다 작은 수 중 만들 수 있는 최대값

이 문제는 알고리즘 공부를 하다가 도전해본 문제이다. 따로 백준 코드에 있는 문제가 아니라서 수기로 적어보려고 한다. 

N,x,y를 입력했을 때

 

x,y로 만들 수 있는 수 중에서 N보다 작지만 제일 큰 수 를 출력하는 것이고 , 만약에 제일 큰 수 를 만들 수 없을 때 -1을 출력하는 것이었다. 

 

예를 들면 N이 13 이고 x,y 가 각각 2, 3일때 결과값은 3이고, 

N이 6 일때 x,y가 각각 7,8 일 때 결과값은 6 이다. 

package sw_samsung;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
//import java.io.FileInputStream;
import java.util.LinkedList;
import java.util.Queue;


 class Solution {
	int MM_print(int N, int x, int y) {
		
		

		String Number = Integer.toString(N);
		//ArrayList<Integer> Numarr = new ArrayList<>();
		Queue<Integer> Numarr = new LinkedList<>(); 
		
		for (int i = 0;i<Number.length(); i++) {
					
					Numarr.add(Number.charAt(i)-'0');
					
				}
		
		
		ArrayList<Integer> MM = new ArrayList<>();
		
		
		
		
		int MAX;
		int MIN;
		if(x>y) {
			MAX  = x ;
			MIN = y;}
		else {
			MAX = y;
			MIN = x;
		}
		
		int j=0;
		while(j<Numarr.size()) {
			if(Numarr.get(j)>MAX) {
				for(;j<Numarr.size();j++) {
					MM.add(MAX);
					
					
				}
				break;
				
			}
			else if(Numarr.get(j)==MAX) {
				MM.add(MAX);
				j++;
				
			}
			else if(Numarr.get(j)<MAX && Numarr.get(j)>MIN) {
				
					MM.add(MIN);
					j++;
					for(;j< Numarr.size();j++) {
						MM.add(MAX);
						
						
					}

					break;
				}
				
					
			
			else if( Numarr.get(j)==MIN) {
				
				MM.add(MIN);
				j++;
				

				
			}
			else if(Numarr.get(j) < MIN) {
				int k;
				k = j;
				if(k>0) {
					MM.remove(--k);
					MM.add(MIN);
					for(;k< Numarr.size();k++) {
						MM.add(MAX);
					
					}

					break;
				}
				
				
				else if(k==0) {
					
					
					for(;k+1<Numarr.size();k++) {
						MM.add(MAX);
					
					}
					break;
				}
				
				
			}
		}
		
		int [] arr = new int[MM.size()];
		
		
		if(MM.size()==0) {
			
			return -1;
		}
		else if(MM.get(0)==0) {
			if( MM.size() ==1) {
				
				return -1;
		}
			else {
				
				
				for(int i=1; i< MM.size(); i++) {
					arr[i-1] = MM.get(i);
					
					}
				String str = Arrays.toString(arr);
		        str = str.substring(1,str.length()-2).replace(", ","");
		        
		        int result =Integer.parseInt(str);
		        
		        
				return result;
					
		}
			
	}
		
		else {
			
			
			for(int i=0; i< MM.size(); i++) {
				arr[i] = MM.get(i);
			
			}
			String str = Arrays.toString(arr);
	        str = str.substring(1,str.length()-1).replace(", ","");
	        int result =Integer.parseInt(str);
	       
			return result;
		}
		
	
	
	}
	
	
	public static void main(String[] args) {
		
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		
		
		Queue<Integer> queue = new LinkedList<Integer>();
		//int[] testarr;
		//testarr = new int[T];
		
		for(int i=0; i<T;i++) {
			Solution test = new Solution();
			
			
			int N = sc.nextInt();
			int x = sc.nextInt();
			int y = sc.nextInt();
			
			queue.offer(test.MM_print(N, x, y));
			//testarr[i] = test.MM_print(N,x,y);
			
		}
		sc.close();
		for(int test_case=1; test_case<=T;test_case++) {
			
			System.out.print("#"+test_case+"  ");
			System.out.println(queue.poll());
			//System.out.println(testarr[test_case-1]);
			
		}
		
	}

}

 

               처음에는 이걸 배열로 풀려고 했다. 만약에 N값이 245678라고 하면 각 자리수를 배열에 집어넣어서 각 배열의 인덱스 처음부터 x y 중 제일 큰값과 비교해서 새로운 배열에 저장하는 식으로 풀려고 했으나 실패했다. 숫자가 커질 수록 배열의 크기가 너무 커져서 메모리 차지가 많아졌고, 빈 배열을 처리하기가 힘들었기 때문이다. 그래서 생각해낸 두번째 방법이 동적 메모리 할당이었다. 저장되는 수만큼 배열이 커지도록 하였다. 

하지만 이것 또한 복잡하여 큐(queue)로 해결하였다. 하지만 막판에 메모리의 크기를 줄이고 런타임을 줄이는 과정에서 코드를 완성시키지 못했다. 이것또한 결국 알고리즘으로 해결해야하는데 그 부분까지는 잘 몰라서 실패했다. 쉽다고 생각했던 코드가 이렇게 복잡하여 계속 머리 속에 맴돌게 되었다.