[JAVA04] 2529. 부등호

2529. 부등호 (S1)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	28766	16786	11422	57.414 %

 

 

문제

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자. 

 

A ⇒ < < < > < < > < >

 

부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다. 

3 < 4 < 5 < 6 > 1 < 2 < 8 > 7 < 9 > 0

 

이 상황에서 부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있는데 이 수를 주어진 부등호 관계를 만족시키는 정수라고 한다. 그런데 주어진 부등호 관계를 만족하는 정수는 하나 이상 존재한다. 예를 들어 3456128790 뿐만 아니라 5689023174도 아래와 같이 부등호 관계 A를 만족시킨다.

 

5 < 6 < 8 < 9 > 0 < 2 < 3 > 1 < 7 > 4

 

여러분은 제시된 k개의 부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다. 앞서 설명한 대로 각 부등호의 앞뒤에 들어가는 숫자는 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다. 

입력

첫 줄에 부등호 문자의 개수를 나타내는 정수 k가 주어진다. 그 다음 줄에는 k개의 부등호 기호가 하나의 공백을 두고 한 줄에 모두 제시된다. k의 범위는 2 ≤ k ≤ 9 이다. 

 

출력

여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력에 답은 항상 존재하며 출력 정수는 하나의 문자열이 되도록 해야 한다. 

---

summary

부등호 조건에 만족하는 정수 최댓값과 최솟값 찾기 

 

- 각 자리에는 숫자 0부터 9까지 사용된다.

- 각 자리에 숫자는 중복되지 않는다.

- 결과값의 첫자리가 0일때 0도 출력시켜야 한다. (숫자로 저장하면 안됨)

 

strategy

k 가 9 이기 때문에 k + 1인 최대 10으로 완전탐색 고려. 백트래킹으로 가지치기.

(모든 숫자조합을 따진다면 O(10^N) 이다. 하지만 해당 문제는 숫자가 중복되지 않기 때문에 경우의 수를 체크하면 10! 이기이다. 가지치기하면 완전탐색 가능.)

 

 

- 입력받은 부등호 기호들 저장 (list)

- 사용되는 숫자들을 순서대로 저장 (number[])

- 해당 숫자를 사용했는지 체크, join 함수 사용하기 위해서 String 선택 (String numberUsed[])

- 큰수를 구하는 경우와 작은 수를 구하는 경우를 나눠줘야 한다. (큰수부터 선택, 작은수부터 선택)

 

note

-  2 ≤ k ≤ 9

 

 

열심히 구현해봤는데 틀렸다. 왜지. 처음부터 다시 생각해봐야 할거같다.

import java.util.*;
import java.io.*;

public class Main {

    static int N;
    static String[] list;
    static String[] number;
    static boolean[] numberUsed = new boolean[10];
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder answer = new StringBuilder();

        /* Input */
        N = Integer.parseInt(br.readLine());
        list = br.readLine().split(" ");
        number = new String[N + 1];

        /* logic */
        for (int i = 9; i >= 0; i--) {
            Arrays.fill(number, "");
            Arrays.fill(numberUsed, false);
            
            number[0] = String.valueOf(i);
            numberUsed[i] = true;

            if (backtracking(0, true)) {
                answer.append(String.join("", number)).append("\n");
                break;
            }
        }

        for (int i = 0; i <= 9; i++) {
            Arrays.fill(number, "");
            Arrays.fill(numberUsed, false);
            
            number[0] = String.valueOf(i);
            numberUsed[i] = true;
            
            if (backtracking(0, false)) {
                answer.append(String.join("", number));
                break;
            }
        }

        /* Output */
        System.out.println(answer.toString());
    }
    
    public static boolean backtracking(int currentIdx, boolean isLargest) {
        if (currentIdx == N) {
            return true;
        } 

        int start = isLargest ? 9 : 0;
        int end = isLargest ? 0 : 9;
        int step = isLargest ? -1 : 1;


        if (list[currentIdx].equals("<")) {
            for (int i = start; isLargest ? i >= end : i <= end; i += step) {
                if (!numberUsed[i] && (Integer.parseInt(number[currentIdx]) < i)) {
                    numberUsed[i] = true;
                    number[currentIdx + 1] = String.valueOf(i);

                    if (backtracking(currentIdx + 1, isLargest)) {
                        return true;
                    }

                    numberUsed[i] = false;
                }
            }
        } else if (list[currentIdx].equals(">")) {
            for (int i = start; isLargest ? i >= end : i <= end; i += step) {
                if (!numberUsed[i] && (Integer.parseInt(number[currentIdx]) > i)) {
                    numberUsed[i] = true;
                    number[currentIdx + 1] = String.valueOf(i);

                    if (backtracking(currentIdx + 1, isLargest)) {
                        return true;
                    }

                    numberUsed[i] = false;
                }
            }
        }

        return false;
    }
}

 

문제	결과	메모리	시간	언어코드	길이
2529	맞았습니다!!	14220	100ms	Java 11 / 수정	2707

 

MEMO

- String 동등비교할 때 equals 쓰도록 신경쓰기

- 출력 조건 제대로 읽자... (최대, 최소 출력인데 최소, 최대 출력으로 착각함.)

	public static boolean isValid(int digit, int idx, char operator) {
        if (idx == 0) return true;

        int prevDigit = Integer.parseInt(number[idx]);
        return operator == '<' ? prevDigit < digit : prevDigit > digit;
    }

- 해당 코드를 사용하면 중복 코드를 줄일 수 있음 (if(list[currentIdx].equals("<")) { ... },  else if() { ...} 를 안나눠도 됨.)

 

실버1 인데 조건들이 너무 복잡해서 다른 코드들 찾아봤더니 내가 너무 복잡하게 풀었다.

조건에 해당하는 모든 수를 구해서 리스트에 저장한 다음에 제일 작은거랑 제일 큰거 구하면 되는거였다.

괜히 시간 줄이겠다고 코드가 길어지고 조건 나눈다고 문제 푸는 시간을 오래 소비했다. 내 문제푸는 시간이 더 소중한데... 코테때 이러면 완전 큰 실수임