BOJ) 부등호

부등호

2529번: 부등호

풀이

 

답은 바로 구했지만, 메모리를 너무 많이 잡고 속도가 느려서 몇 번을 다시 풀었다.

처음에는 모든 경우의 수를 다 구해서, 부등호의 갯수 n개 +1 만큼의 숫자를 뽑은 경우를 답 리스트에 넣어주었다.

이후, 정렬을 통해 양 끝에 있는 수를 출력해주었다.

 

코드 1

정말 별로인 코드다...

그래서 조금 고쳐보기로 했다.

String으로 다 저장해서 정렬을 하는것이 아니라, Long 타입 변수를 통해 MAX와 MIN 값을 저장해주었다.

로직 자체가 문제라서 메모리와 속도에 큰 효과를 보지 못할 것이라고 생각했지만, 더 나은 코드를 생각하는 과정이라고 생각하고 진행했다.

최대 최솟값이 앞자리가 0인 경우는 LONG 타입이기 때문에 0이 저장되지 않는다.

그래서 자릿수에 맞게 0까지 print를 해주는 메소드를 만들어서 제출했다.

 

코드 2

속도 측면에서는 꽤나 성능이 좋아졌다.

하지만, 여전히 메모리를 많이 잡아먹고 속도도 좋지 못하다고 생각이 들었다.

그래서 list를 빼고 생각하기로 했다.

 

하지만, 잘 떠오르지 않아서 질문 게시판을 참고했다.

list로 숫자를 추가하는 과정을, Long타입의 숫자에 이전 숫자를 10씩 증가시키면서 해당 숫자를 더해 하나의 숫자로 그냥 구해주었다.

또한, 0~9를 다 도는 것이 아니라, 부등호에 따라서 0~n , n~9 까지만 for문을 돌게 해주었다.

 

Long 타입으로 최대 최소를 구해줬기 때문에, 여기서도 0을 포함하는 print를 해야했다.

C언어에서 %0nd가 생각나서 찾아봤는데, 자바에도 String.format으로 쓸 수 있었다. ( 잘 쓰지 않아서 까먹고 있었는데, 다시 생각났다. )

 

코드 3

메모리와 속도가 현저히 좋아졌다.

답답한 마음이 확 풀리는 순간이었다.

brute-force 문제는 어떻게 가지치기를 하느냐가, 그리고 어떤 식으로 값을 도출하는가에 따라 정말 천차만별인것 같다.

물론 다른 알고리즘들도 마찬가지지만, brute-force는 완전 탐색을 전제로 하기 때문에, 더욱 조심할 필요가 있는 것 같다.

 

코드 1

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.LinkedList;

public class Main {
    final static int NUMMAX = 10;
    final static String LEFT = ">";
    static String[] ineqArr;
    static LinkedList<String> ansList;

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

        solution(n);

        br.close();
    }

    private static void solution(int n) {
        ansList = new LinkedList<>();
        getAns(new boolean[NUMMAX], 0, n, new LinkedList<>());
        Collections.sort(ansList, (o1, o2) -> o1.compareTo(o2) < o2.compareTo(o1) ? 1 : -1);
        System.out.println(ansList.poll());
        System.out.println(ansList.pollLast());
    }

    private static void getAns(boolean[] visit, int cnt, int n, LinkedList<Integer> list) {
        if(n <cnt) {
            if(list.size()>n) {
                LinkedList<Integer> newList = copyList(list);
                StringBuffer sb = new StringBuffer();
                for (String ineq : ineqArr) {
                    int leftNum = newList.poll();
                    int rightNum = newList.peek();
                    if (ineq.equals(LEFT)) {     // >
                        if (leftNum < rightNum) {
                            return;
                        }
                    } else {                    // <
                        if (leftNum > rightNum) {
                            return;
                        }
                    }
                    sb.append(leftNum);
                }
                sb.append(newList.poll());
                ansList.offer(sb.toString());
            }
            return;
        }
        for(int i=0; i<NUMMAX; i++) {
            if(!visit[i]) {
                visit[i] = true;
                list.offer(i);
                getAns(visit,cnt+1,n,list);
                visit[i] = false;
                list.pollLast();
            }
        }

    }

    private static LinkedList<Integer> copyList(LinkedList<Integer> list) {
        LinkedList<Integer> result = new LinkedList<>();
        for(int num : list) {
            result.offer(num);
        }
        return result;
    }
}

 

코드 2

 

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

public class Main {
    final static int NUMMAX = 10;
    final static String LEFT = ">";
    static String[] ineqArr;
    static long minAns, maxAns;

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

        solution(n);

        br.close();
    }

    private static void solution(int n) {
        minAns = Long.MAX_VALUE;
        maxAns = 0;
        getAns(new boolean[NUMMAX], 0, n, new LinkedList<>());
        printNum(maxAns,n);
        printNum(minAns,n);
    }

    private static void printNum(long num, int n) {
        long div = (long) Math.pow(10,n);
        StringBuffer sb = new StringBuffer();

        for(int i=0 ;i<=n; i++) {
            sb.append(num/div);
            num%=div;
            div/=10;
        }
        System.out.println(sb.toString());
    }

    private static void getAns(boolean[] visit, int cnt, int n, LinkedList<Integer> list) {
        if(n <cnt) {
            if(list.size()>n) {
                StringBuffer sb = new StringBuffer();
                int leftIdx =0;
                int rightIdx =1;
                for(int i=0; i<n; i++) {
                    int leftNum = list.get(leftIdx++);
                    int rightNum = list.get(rightIdx++);
                    if (ineqArr[i].equals(LEFT)) {     // >
                        if (leftNum < rightNum) {
                            return;
                        }
                    } else {                    // <
                        if (leftNum > rightNum) {
                            return;
                        }
                    }
                    sb.append(leftNum);
                }
                sb.append(list.get(leftIdx));
                maxAns = Math.max(Long.parseLong(sb.toString()),maxAns);
                minAns = Math.min(Long.parseLong(sb.toString()), minAns);
            }
            return;
        }
        for(int i=0; i<NUMMAX; i++) {
            if(!visit[i]) {
                visit[i] = true;
                list.offer(i);
                getAns(visit,cnt+1,n,list);
                visit[i] = false;
                list.pollLast();
            }
        }

    }
}

 

코드 3

 

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

public class Main {
    final static int NUMMAX = 10;
    final static String LEFT = ">";
    static String[] ineqArr;
    static long minAns, maxAns;
    static boolean[] visit;

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

        solution(n);

        br.close();
    }

    private static void solution(int n) {
        minAns = Long.MAX_VALUE;
        maxAns = 0;
        visit = new boolean[NUMMAX];
        for(int i=0; i<NUMMAX; i++) {
            visit[i] = true;
            getAns(i, 0, n, i);
            visit[i] = false;
        }

        System.out.println(maxAns);
        StringBuffer sb = new StringBuffer("%0").append(n+1).append("d");
        System.out.println(String.format(sb.toString(),minAns));
    }

    private static void getAns(int now, int idx, int n, long num) {
        if(idx == n) {
            maxAns = Math.max(maxAns, num);
            minAns = Math.min(minAns, num);
            return;
        }

        if(ineqArr[idx].equals(LEFT)) {  // >
            for(int i=0; i<now; i++) {
                if(!visit[i]) {
                    visit[i] = true;
                    getAns(i, idx + 1, n, num * 10 + i);
                    visit[i] = false;
                }
            }
        } else {                    // <
            for(int i=NUMMAX-1; i>now; i--) {
                if(!visit[i]) {
                    visit[i] = true;
                    getAns(i, idx + 1, n, num * 10 + i);
                    visit[i] = false;
                }
            }
        }
    }
}