99클럽 코테 스터디 37일차 TIL , 부등호(2529)

문제

풀이

입력 첫 번째 줄에 부등호의 개수가 주어진다. 그다음 줄로 부등호들이 간격을 두고 주어진다.

부등호의 앞뒤로 0~9의 숫자가 한번씩 들어갈 수 있는데 부등호 관계가 옳게 되어야 한다.

부등호의 관계를 만족하는 경우 중에 가장 큰 수와 가장 작은 수를 차례대로 출력하면 된다.

풀이 1 - 정답

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

public class Main {
	//출력 값 클래스 멤버변수 선언
    private static long max = Long.MIN_VALUE;
    private static long min = Long.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

		//부등호 character 배열에 담아주기
        char[] inequality = new char[n];
        for(int i=0;i<n;i++){
            inequality[i] = st.nextToken().charAt(0);
        }

        //n, 부등호, visited, val
        dfs(n, inequality, new boolean[10], new int[n + 1], 0);
		
        //자릿 수 맞춰주기
        StringBuilder maxValue = new StringBuilder(String.valueOf(max));
        StringBuilder minValue = new StringBuilder(String.valueOf(min));

        while(maxValue.length() < n+1){
            maxValue.insert(0,"0");
        }
        while(minValue.length() < n+1){
            minValue.insert(0,"0");
        }
        System.out.println(maxValue);
        System.out.print(minValue);
    }

    private static void dfs(int n, char[] inequality
            , boolean[] visited, int[] values, int depth) {
        if(depth == n+1){	//자릿 수를 모두 채웠다면
            StringBuilder sb = new StringBuilder();
            //부등호가 옳지 않다면 return
            for(int i=0;i<n;i++){
                if(inequality[i] == '<'){
                    if(values[i] >= values[i+1]) return;	
                }else{ // '>'
                    if(values[i] <= values[i+1]) return;
                }
                sb.append(values[i]);
            }
            sb.append(values[n]);

			//max, min값 갱신
            max = Long.max(max, Long.parseLong(sb.toString()));
            min = Long.min(min, Long.parseLong(sb.toString()));

            return;
        }

        for(int i=0;i<visited.length;i++){
            if(visited[i]) continue;
            visited[i] = true;
            values[depth] = i;
            dfs(n, inequality, visited, values, depth+1);

            visited[i] = false;
        }

    }
}

 

완전탐색 문제라 DFS로 풀이했다.

자릿수를 모두 채우면 조건을 만족하는지 확인하고 min, max값을 갱신해 준다.

 

제출 1 리팩토링

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

public class No2529 {
    private static long max = Long.MIN_VALUE;
    private static long min = Long.MAX_VALUE;
    private static boolean[] visited = new boolean[10];
    private static int[] values;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());

        char[] inequality = new char[n];
        for(int i=0;i<n;i++){
            inequality[i] = st.nextToken().charAt(0);
        }

        values = new int[n + 1];
        //n, 부등호, visited, val
        dfs(n, inequality, 0);

        String maxValue = String.format("%0" + (n+1) + "d", max);
        String minValue = String.format("%0" + (n+1) + "d", min);

        System.out.println(maxValue);
        System.out.print(minValue);
    }

    private static void dfs(int n, char[] inequality, int depth) {
        if(depth == n+1){
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<n;i++){
                if(inequality[i] == '<'){
                    if(values[i] >= values[i+1]) return;
                }else{ // '>'
                    if(values[i] <= values[i+1]) return;
                }
                sb.append(values[i]);
            }
            sb.append(values[n]);

            max = Long.max(max, Long.parseLong(sb.toString()));
            min = Long.min(min, Long.parseLong(sb.toString()));

            return;
        }

        for(int i=0;i<visited.length;i++){
            if(visited[i]) continue;
            visited[i] = true;
            values[depth] = i;
            dfs(n, inequality, depth+1);

            visited[i] = false;
        }

    }
}

 

dfs 메서드에 매개변수가 많아 가독성이 떨어진다 판단하여 클래스 멤버변수로 생성해 주었다.

출력 시 길이를 맞춰주기 위해서 String.format으로 변경해 주었다.

속도는 비슷하다.

TIL

• DFS