Algorithm Study

[BOJ] 2529번: 부등호 / JAVA, 백트래킹

hyun-1200 2022. 4. 6. 22:45

 

 

https://www.acmicpc.net/problem/2529

 

2529번: 부등호

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

www.acmicpc.net

 

 

1.  재귀함수 돌릴 조건

 - 첫번째 시작하는 숫자는 0부터 9까지 모든 숫자가 가능하므로

 - 0 부터 9 까지 모든 수를 재귀함수로 돌린다. 

for(int i=0;i<10;i++){
check[i]=true;
recursion(0,Integer.toString(i));
check[i]=false;
}
 
 

2. 재귀함수 파라미터

-  깊이를 비교하는 int depth, 저장될 String 로 한다.

public static void recursion(int depth, String str)
 
 
 

3. 결과값 처리

- 저장될 String 값은 012 와 같은 숫자아닌 값도 비교해야 하므로,
- ArrayList 형식에 담아서
- 마지막에 Collections.sort 를 사용해서 제일 큰 String형과 작은 String형을 반환한도록 한다.
 
Collections.sort(result);
 
bw.write(result.get(result.size()-1) +"\n");
bw.write(result.get(0)+"\n");
 

4. 재귀함수 내부 설명

  1)  "<" 값을 만나면, String 마지막 값보다 큰 값부터~ 9까지  for 문을 돌리도록
  2) ">" 값을 만나면, String 마지막 값보다 0부터 ~ 작은 값까지 for문을 돌리도록
 

5. 그 외

* ArrayList 에서 길이는 size() 사용
* String에서 길이는  length() 사용 
 
* Char 에서 int 형으로 출력하고싶으면 - '0' 사용
str.charAt(str.length()-1) - '0';