[JAVA] 2529번 - 부등호
문제 탐색하기
- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정
문제 아이디어)
숫자는 [0,1,2,3,4,5,6,7,8,9]로 고정되어 있다.
이중에서 K+1개만큼의 숫자들로 이루어진 수열들 중 부등호를 만족하는 것을 찾으면 된다!
예를 들어 부등호K가 2면 숫자는 3자리수가 가능하고 0부터 9까지 숫자들을 중복 없이 3자리수로 만들수 있다.
만들어진 숫자들 중에서 부등호를 충족하는 애들을 고르면 된다.
즉 모든 가능한 수열을 탐색하여, 조건에 맞는 수열만 선택해 나가는 거다.
그래서 백트래킹으로 풀 수 있다.
문제를 풀기 위해 필요한 것)
1.부등호를 담은 배열
2. 방문배열(0부터 9까지 중에서 중복을 허용하지 않으니까)
3. 문자열을 담을 List (9567843012) 이렇게 문자열들을 담아야하니까
4. 문자열의 깊이(k에 따라서 3자리수, 6자리수 등등이 있으면 백트래킹을 수행할때마다 자리수를 체크해야하니까)
시간복잡도
K+1개 만큼의 숫자로 만들 수 있는 경우의 수는 (K+1)! 이다.
K는 최대 9니까 10!만큼 소요된다. = 3,628,800
O(3,628,800)이니까 1초안에 연산이 가능하다!
코드 설계하기
위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성
1. 백트래킹 함수 선언
백트래킹은 함수에 파라미터를 뭘로 넣을지가 되게 중요한 것 같다.
문자열을 만들어서 요구하는 자리수만큼 다 만들면? 백트래킹을 종료해야하니까 String num 필요
몇번째 자리 수 까지 만들어졌는지 확인하기 위해 int depth 필요
private static void backtrack(String num, int depth) {
}
2. 종료 조건
종료 조건은 depth가 k+1을 만족한다면 종료 되어야한다.
정답리스트에 넣고 종료한다!
if(depth == k+1) {
ans.add(num);
return;
}
3. 0부터 9까지 탐색하면서 가능한 경우의 수를 찾기
만약 해당 숫자가 이미 방문했다면 중복이안되니까 continue
depth가 0이라면 아직 한자리수라는 거니까 다음 숫자로 패스
둘다 아니라면 부등호 조건에 맞는지 확인해야한다. 확인하는 함수를 따로 만든다.
내 앞에 있는 숫자랑, 내 숫자랑, 부등호 -> 부등호 확인함수로 비교
부등호가 맞다면 방문 처리하고 다시 백트래킹 호출하여 문자열을 추가해나간다
마지막에 방문배열을 false처리해준다. 하나의 문자열 탐색이 끝나고 다른 문자열을 탐색할때 다시 숫자를 써야하기 때문이다
for(int i=0; i<=9; i++) {
if(visited[i]) continue;
// depth가 0이면 비교할 숫자가 하나밖에 없음 다음 숫자로 패스
// 비교한 두 숫자가 주어진 부등호의 조건과 맞다면 계속 진행
if(depth==0 || check(Character.getNumericValue(num.charAt(depth -1)), i, sign[depth-1])) {
visited[i]= true;
backtrack(num+i, depth+1);
visited[i] = false;
}
}
4. 부등호 확인
조건에 맞지 않는다면 false반환, 조건에 맞는다면 true를 반환한다.
private static boolean check(int a, int b, char c) {
if (c=='<') {
if( a>b) return false;
}
else if( c=='>') {
if(a<b) return false;
}
return true;
}
5. 출력
굳이 정렬안해도된다. 애초에 탐색할때 0부터 탐색하니까
제일 처음 들어가게 되는게 제일 작은 수이기 때문이다.
시도 회차 수정 사항
- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeSet;
public class Main {
static int k;
static char[] sign;
static List<String>ans;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
k = Integer.parseInt(br.readLine());
sign = new char[10];
ans = new ArrayList<>();
visited = new boolean[10];
st = new StringTokenizer(br.readLine());
for(int i=0; i<k; i++) {
sign[i] = st.nextToken().charAt(0);
}
backtrack("", 0);
System.out.println(ans.get(ans.size()-1));
System.out.println(ans.get(0));
}
private static void backtrack(String num, int depth) {
// 종료 조건
if(depth == k+1) {
ans.add(num);
return;
}
for(int i=0; i<=9; i++) {
if(visited[i]) continue;
// depth가 0이면 비교할 숫자가 하나밖에 없음 다음 숫자로 패스
// 비교한 두 숫자가 주어진 부등호의 조건과 맞다면 계속 진행
if(depth==0 || check(Character.getNumericValue(num.charAt(depth -1)), i, sign[depth-1])) {
visited[i]= true;
backtrack(num+i, depth+1);
visited[i] = false;
}
}
}
private static boolean check(int a, int b, char c) {
if (c=='<') {
if( a>b) return false;
}
else if( c=='>') {
if(a<b) return false;
}
return true;
}
}