https://www.acmicpc.net/problem/2529
2529번: 부등호
두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시
www.acmicpc.net
코딩테스트 언어를 python에서 java를 바꾸는 과정에서 문제들의 유형들을 여러가지 풀어봐야할 것 같아서 DFS 문제로 정하고 문제를 품
📌 - 처음 생각한 풀이
- DFS로 완전탐색을 하면서 부등호에 맞는 모든 경우의 수를 List에 저장
- list의 크기가 N+1이 됐을 때, 리스트에 있는 모든 값들을 str에 순차적으로 저장
- str을 long으로 형변환 하면서 크기 비교 -> 최솟값과 최댓값 비교해서 저장
이렇게 풀이를 하니까 예외처리를 해줘야할 것들이 많이 생겨서 코드가 점점 복잡해지고, 가독성이 많이 떨어졌다.
DFS의 매개변수도 부등호 배열의 인덱스 값을 넣어주다보니 코드를 작성하면서도 스스로가 헷갈려서 시간을 더 잡아 먹은것 같다.
물론 정답으로 통과는 했지만 만족할만한 풀이가 아니기에 다른 분의 코드를 참고해서 다시 문제를 해결해봤다.
👉 - java code
package DFS.S1_2529_부등호;
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;
public class Main {
public static int N;
public static long min = Long.MAX_VALUE,max = Long.MIN_VALUE;
public static String[] arr;
public static String minStr,maxStr;
public static ArrayList<String> result = new ArrayList<>();
public static boolean[] visited;
public static void main(String[] args) throws IOException {
//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
StringTokenizer st = new StringTokenizer(br.readLine());
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(st.nextToken());
arr = new String[N+1];
visited = new boolean[10];
st = new StringTokenizer(br.readLine());
for ( int i = 0;i<N;i++){
arr[i] = st.nextToken();
}
DFS(0,result);
System.out.println(maxStr);
System.out.println(minStr);
}
public static void DFS(int s,ArrayList<String> list){
if (list.size() == N+1){
String ans="";
for(String t : list){
ans+=t;
}
if (min> Long.parseLong(ans)){
min = Math.min(Long.parseLong(ans),min);
minStr = ans;
}
if (max <Long.parseLong(ans)){
max = Math.max(Long.parseLong(ans),max);
maxStr = ans;
}
return;
}
for (int i =0;i<10;i++){
boolean mis = false;
if (list.size() ==0){
mis = true;
}
if (!visited[i]){
if(s >0){
switch (arr[s-1]){
case "<":
if(Integer.parseInt(list.get(list.size()-1)) < i){
mis = true;
}
break;
case ">":
if(Integer.parseInt(list.get(list.size()-1)) >i){
mis = true;
}
break;
}
}
if(mis){
visited[i] = true;
list.add(String.valueOf(i));
DFS(s+1,list);
visited[i] = false;
list.remove(list.size()-1);
}
}
}
}
}
📌 - 참고해서 다시 만든 코드
- 모든 경우의 수를 DFS로 돌면서 조건에 부합하면서 길이가 N+1이 됐을 때 ArrayList에 추가한다.
- 추가된 숫자들을 sort해서 최댓값과 최솟값을 구한다.
확실히 너무 쉽게 짤 수 있는 문제였고, 이런 방법을 생각 못해서 아쉽지만 그래도 배웠다고 생각하며 기록을 한다.
package DFS.S1_2529_부등호;
import java.io.*;
import java.util.*;
public class Main2 {
public static int N;
public static String[] arr;
public static ArrayList<String> result = new ArrayList<>();
public static boolean[] visited = new boolean[10];
public static void main(String[] args) throws IOException {
//BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedReader br = new BufferedReader(new FileReader("src/input.txt"));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
arr = new String[N + 1];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = st.nextToken();
}
DFS( "",0);
Collections.sort(result);
System.out.println(result.get(result.size() - 1)); //최댓값
System.out.println(result.get(0)); //최솟값
}
public static void DFS( String str,int depth) {
if (depth == N + 1) {
result.add(str);
return;
}
for (int i = 0; i < 10; i++) {
if (depth == 0 || !visited[i] && compare(str.charAt(str.length()-1)-'0',i,arr[depth-1])) {
visited[i] = true;
DFS(str+i,depth+1);
visited[i] = false;
}
}
}
private static boolean compare(int a, int b, String c) {
if (c.equals("<")) return a < b;
else return a > b;
}
}