BOJ 2529 부등호 (Java, Python)

2529 부등호

문제 탐색하기

• 두 종류의 부등호 기호 기준에 의거해, 선택되는 숫자의 최솟값과 최댓값을 구해야 한다.

• 입력 예시

  2
  < >
  

• 출력 예시

  210
  012
  

코드 설계하기

• 만약에 DFS로 순회를 한다면, 최초 선택되는 값은 최솟값 - 최후 순회되는 값은 최댓값이다.
  1. 최솟값이 선택된 이후 최솟값 출력 > 이후 계속 갱신하다가 마지막으로 갱신된 값 (최댓값) 출력하는 방식으로 하거나
  2. 최솟값 저장 후 최댓값은 계속 갱신하는 방식 으로 구현하면 된다.
• 입, 출력 예시로부터 DFS 탐색 과정을 확인하면 다음과 같다.

부등호: < <
가능한 최소값 찾기 과정:
0 → 1 → 2  (최소값: 012)
가능한 최대값 찾기 과정:
9 → 8 → 7  (최대값: 987)

• 정답인 String을 직접 조작하지 않고, 종료시 StringBuilder.toString을 사용해 메모리 사용량을 낮춘다.

구현 방법

1. N과 해당하는 부등호 값을 입력받는다.
2. 정답으로 출력할 최솟값과 최댓값 변수, 방문 여부를 저장할 visited배열 객체를 저장한다.

시간 복잡도

• 부등호 최대 개수가 9개이므로 숫자의 최대 길이는 10
• 최대 시간 복잡도 (n+1)! -> n = 9 이므로 최대 연산 개수는 3,628,800 이다.
  • DFS를 사용한 Brute Force을 채택하여도 1초 이내에 연산이 가능하다.

정답 코드 (Java)

import java.io.BufferedReader;  
import java.io.InputStreamReader;  
import java.util.StringTokenizer;  
  
public class Main {  
    private static int N;  
    /** 정답 값 */  
    private static String min, max;  
    /** 부등호 저장 배열 */  
    private static char[] arr;  
    /** 0 ~ 9에 해당하는 각 숫자 방문 여부 저장 배열 */  
    private static final boolean[] visited = new boolean[10];  
  
    public static void main(String[] args) throws Exception{  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        N = Integer.parseInt(st.nextToken());  
        arr = new char[N];  
  
        st = new StringTokenizer(br.readLine());  
        // 부등호 입력받기  
        for (int i = 0; i < N; i++) {  
            arr[i] = st.nextToken().charAt(0);  
        }  
          
        DFS(0, new StringBuilder());  
  
        System.out.println(max +"\n" + min);  
    }  
  
    /**  
     *
	 * @param idx DFS 깊이  
     * @param s 생성 문자열  
     */  
    private static void DFS(int idx, StringBuilder s) {  
        // 종료 조건: idx가 N+1이면 완성된 숫자 생성  
        if (idx == N + 1) {  
            // 첫 번째 순회로 완성된 숫자가 최소값, 마지막이 최대값  
            if (min == null) {  
                min = s.toString();  
            } else {  
                max = s.toString();  
            }  
            return;  
        }  
  
        for (int i = 0; i < 10; i++) {  
            if (visited[i]) continue;  
            // 첫 단계일 경우는 무조건 진행, 아닐 경우 마지막 추가 숫자와 비교  
            if (idx == 0 || possible(arr[idx - 1], s.charAt(s.length() - 1), (char)(i + '0'))) {  
                visited[i] = true;  
                s.append(i);  
                DFS(idx + 1, s);  
                // 재귀 호출 후 마지막에 추가한 문자 제거  
                s.deleteCharAt(s.length() - 1);  
                visited[i] = false;  
            }  
        }  
    }  
  
    /**  
    * @return 부등호 값에 따라 가능한지 여부를 반환  
    * */  
    private static boolean possible(char c, char cur, char next) {  
        if (c == '<'){  
            return cur < next;  
        }  
        if (c == '>'){  
            return cur > next;  
        }  
  
        return true;  
    }  
}

정답 코드 (Python)

import sys

r = sys.stdin.readline

N = int(r())
numList = list(map(str, r().split()))
max_val, min_val = None, None

visited = [False] * 10 # 0-9

def DFS(x, num): # 재귀함수
    global max_val, min_val
    
    if x == N+1:
        if not min_val:
            min_val = num
        else:
            max_val = num
        return
    for i in range(10):
        if not visited[i]: # 방문하지 않았으면
            if x == 0 or possible(num[-1], str(i), numList[x-1]):
                visited[i] = True
                DFS(x+1,num + str(i))
                visited[i] = False

def possible(i,j,k): # 가능한지 여부를 판정
    if k == '<':
        return i<j
    if k == '>':
        return i>j

    return True

DFS(0,"")
print(max_val)
print(min_val)