[백준] 2529 부등호 - 브루트포스 + 구현 JAVA

https://www.acmicpc.net/problem/2529

2529번: 부등호

코드설명

브루트포스와 구현 문제입니다.

 

문제에 주어진 로직 그대로 진행하면 되는 문제입니다.

문제에서 유의해야할점은,

처음에 저는 아래의 코드에서 simulate 재귀함수를 else if문 안에 넣어두어서 값이 실패할 경우에도 simulate를 통해 값이 실행되서 number값이 갱신되지 않은채로 실행될 수 있습니다. 각경우에 대해서만 재귀함수를 실행하여 불필요한 과정을 줄여야합니다.

추가로, visited[10] 배열을 선언하여 중복된 숫자가 다시 나오지않도록 설정했습니다.

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

    if(level == 0 && visited[i] == false) { //처음 시작에는 부등호 고려하지 않고, 바로 넣어줍니다.
        number[level] = i;
        visited[i] = true;
        simulate(level + 1);
        visited[i] = false;
    }

    else if(level >= 1 && visited[i] == false) { //부등호를 고려해서 넣어줍니다.
        if( operand[level-1] == '<' ) {
            int beforeNum = number[level-1]; //이전숫자
            if( i > beforeNum) {
                visited[i] = true;
                number[level] = i;
                simulate(level + 1);
                visited[i] = false;
            }
        }else if(operand[level-1] == '>') {
            int beforeNum = number[level-1]; //이전숫자
            if(i < beforeNum) {
                visited[i] = true;
                number[level] = i;
                simulate(level + 1);
                visited[i] = false;
            }
        }
        
		// simulate(level + 1); 처음에 여기다 두었었습니다. 그럴경우 number[level]을 채우지않는경우도 있어서 오류가 납니다.

    }


}

 

이번 문제에서는 처음에는 number[] 배열을 선언해서 각 배열에 숫자를 넣는것이 아닌,

StringBuilder를 활용하여 진행하려했지만, 조금 더 적은 메모리 사용량과 속도를 위해 배열을 사용했습니다.

 

또한, 아래의 코드를 통해 앞에 0 을 동적으로 (N+1) 처리하여 붙여주었습니다.

System.out.println(String.format("%0"+(N+1)+"d", maxAnswer));
System.out.println(String.format("%0"+(N+1)+"d", minAnswer));

 

다른 경우의 코드도 함께 살펴보았는데, 아래처럼 numberString에 계속 값을 더해가면서 나가는경우도 있습니다.

해당 방안도 좋아보입니다.

static void simulate(int level, String numberString) {
...
simulate(level+1, numberString + i)
...

이 완성된 numberString을 list에 넣어서 Collections.sort를 통해 비교한뒤 가장 큰값과 가장 작은값을 출력하는 방안이 있습니다.

 

코드

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

public class Main {
	
	public static int N;
	public static char[] operand;
	public static int answer = 0;
	public static long maxAnswer = 0;
	public static long minAnswer = Long.MAX_VALUE;
	public static int[] number;
	public static boolean[] visited;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	N = Integer.parseInt(st.nextToken());
    	operand = new char[N];
    	number = new int[N+1];
    	st = new StringTokenizer(br.readLine());
    	for(int i=0;i<N;i++) {
    		operand[i] = st.nextToken().charAt(0);
    	}
    	visited = new boolean[10];
    	simulate(0);
    	
    	System.out.println(String.format("%0"+(N+1)+"d", maxAnswer));
    	System.out.println(String.format("%0"+(N+1)+"d", minAnswer));
    }
    
    public static void simulate(int level) {
    	if(level == N+1) {
    		
    		int numTemp = 0;
    		String str="";
    		for(int i=0;i<number.length;i++) {
    			str += number[i];
    		}
    		
    		Long numberInteger = Long.parseLong(str);
    		maxAnswer = Math.max(maxAnswer, numberInteger);
    		minAnswer = Math.min(minAnswer, numberInteger);
//    		for(int i=0;i<N+1;i++) {
//    			System.out.print(" "+number[i]);
//    		}
//    		System.out.println();
    		return ;
    	}
    	
    	for(int i=0;i<=9;i++) {
    		
    		if(level == 0 && visited[i] == false) { //처음 시작에는 부등호 고려하지 않고, 바로 넣어줍니다.
    			number[level] = i;
    			visited[i] = true;
    			simulate(level + 1);
    			visited[i] = false;
    		}
    		
    		else if(level >= 1 && visited[i] == false) { //부등호를 고려해서 넣어줍니다.
    			if( operand[level-1] == '<' ) {
    				int beforeNum = number[level-1]; //이전숫자
    				if( i > beforeNum) {
    					visited[i] = true;
    					number[level] = i;
    					simulate(level + 1);
    	    			visited[i] = false;
    				}
    			}else if(operand[level-1] == '>') {
    				int beforeNum = number[level-1]; //이전숫자
    				if(i < beforeNum) {
    					visited[i] = true;
    					number[level] = i;
    					simulate(level + 1);
    	    			visited[i] = false;
    				}
    			}
				
    		}
    		
    		
    	}
    	
    	
    }
    
}