https://www.acmicpc.net/problem/2529
2529번: 부등호
여러분은 제시된 부등호 관계를 만족하는 k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력해야 한다. 단 아래 예(1)과 같이 첫 자리가 0인 경우도 정수에 포함되어야 한다. 모든 입력
www.acmicpc.net
#문제
두 종류의 부등호 기호 ‘<’와 ‘>’가 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 }중에서 선택해야 하며 선택된 숫자는 모두 달라야 한다.
#알고리즘
브루트포스 알고리즘
백트래킹
#난이도
Silver 2
#풀이방법
백트래킹을 이용하여 모든 경우의 수를 탐색하는 방법으로 풀이하면 된다. 재귀함수를 이용하여서 모든 경우의 수를 탐색하여 일정한 숫자가 되면 if문을 써서 더해준후 return 시켜 종료 시킨다.
부등호가 <, > 밖에 없으므로 지금 idx와 이전 배열의 idx를 비교하여 조건에 맞으면 재귀함수를 써서 재호출한다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | if(idx == K) { an.add(str); return; }//일정 조건이 되면 더해주고, return 시킴 for(int i=0; i<visited.length; i++) { //i는 0~9의 범위이다. if(!visited[i]) { if(sign[idx] == '<') { if(str.charAt(idx) < Integer.toString(i).charAt(0)) { visited[i] = true; back_track(idx+1,visited,str+Integer.toString(i)); visited[i] = false; } }//부등호가 <인 경우 else { if(str.charAt(idx) > Integer.toString(i).charAt(0)) { visited[i] = true; back_track(idx+1 ,visited,str+Integer.toString(i)); visited[i] = false; } }//부등호가 >인 경우 }//방문하지 않는 경우 } | cs |
Arraylist<String>을 써서 모든 경우의 수를 더해주면 list의 마지막 인덱스와 첫번째 인덱스를 출력해주면 된다.
visited을 0부터9까지 탐색했으므로 정렬 해줄 필요없이 마지막과 첫번째를 출력하면 된다.
하지만 여기서 중요한 점은 부등호가 N개일지라도 숫자는 N+1을 넣어 탐색해야 하므로
Main 메소드에서 백트래킹을 호출하여 탐색할때 for문을 이용하여 선 탐색을 해야한다.
1 2 3 4 5 | for(int i=0; i<10; i++) { visited[i] = true; back_track(0,visited,Integer.toString(i)); visited[i] = false; } | cs |
#전체 코드
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | import java.util.*; public class Main { static ArrayList<String> an = new ArrayList<>(); static int K; static char[] sign; public static void back_track(int idx ,boolean[] visited,String str) { if(idx == K) { an.add(str); return; }//일정 조건이 되면 더해주고, return 시킴 for(int i=0; i<visited.length; i++) { //i는 0~9의 범위이다. if(!visited[i]) { if(sign[idx] == '<') { if(str.charAt(idx) < Integer.toString(i).charAt(0)) { visited[i] = true; back_track(idx+1,visited,str+Integer.toString(i)); visited[i] = false; } }//부등호가 <인 경우 else { if(str.charAt(idx) > Integer.toString(i).charAt(0)) { visited[i] = true; back_track(idx+1 ,visited,str+Integer.toString(i)); visited[i] = false; } }//부등호가 >인 경우 }//방문하지 않는 경우 } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); K = sc.nextInt(); sign = new char[K]; for(int i=0; i<sign.length; i++) { sign[i] = sc.next().charAt(0); } //2 <= K <= 9 boolean[] visited = new boolean[10];//0부터 9까지 for(int i=0; i<10; i++) { visited[i] = true; back_track(0,visited,Integer.toString(i)); visited[i] = false; } System.out.println(an.get(an.size()-1)); System.out.println(an.get(0)); } } | cs |
'알고리즘 문제' 카테고리의 다른 글
| 백준 17142번) 연구소3(JAVA) (0) | 2022.08.05 |
|---|---|
| 프로그래머스) 튜플 (0) | 2022.08.02 |
| 백준 6236번) 용돈 관리 (JAVA) (0) | 2022.07.21 |
| 백준 2343번) 기타 레슨 (JAVA) (0) | 2022.07.20 |
| 백준 7795번) 먹을 것인가 먹힐 것인가(JAVA) (0) | 2022.07.19 |