workspace/algorithm
[백트래킹/자바] 코드트리 IL. 아름다운 수
HwangJerry
2023. 9. 8. 14:15
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
문제 해석
이 문제는 모든 경우의 수를 순회하면서 '아름다운 수'인지 판단하고, 그 수를 세는 문제이다. n도 10 이하의 자연수이므로 완전 탐색 알고리즘 중 하나를 사용하는 것이 합리적이다.
그 중에서 이번에는 n에 따라 파악해야 하는 대상 숫자의 자릿수가 변동되므로 완전탐색 중 백트래킹을 이용하여 경우의 수를 탐색하고, 탐색된 경우의 수가 '아름다운 수'인지 확인하는 함수를 작성해서 true일 때마다 count할 수 있도록 연산하면 된다.
풀이 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
private static int n;
private static int ans = 0;
private static List<Integer> li = new ArrayList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
choose(1);
System.out.println(ans);
}
private static void choose(int x) {
if (x == n + 1) {
if (isBeautifulNum(li)) {
ans++;
}
return;
}
x++;
for (int k = 1; k <= 4; k++) {
li.add(k);
choose(x);
li.remove(li.size() - 1);
}
}
private static boolean isBeautifulNum(List<Integer> li) {
for (int i = 0; i < li.size(); i++) {
Integer elem = li.get(i);
if (elem == 1) {
continue;
} else if (elem == 2) {
if (inRange(i + 1)) {
Integer nextElem = li.get(i + 1);
if (elem.equals(nextElem)) {
i = i + 1;
} else {
return false;
}
} else {
return false;
}
} else if (elem == 3) {
if (inRange(i + 2)) {
Integer nextElem = li.get(i + 1);
Integer thirdElem = li.get(i + 2);
if (elem.equals(nextElem) && nextElem.equals(thirdElem)) {
i = i + 2;
} else {
return false;
}
} else {
return false;
}
} else if (elem == 4) {
if (inRange(i + 3)) {
Integer nextElem = li.get(i + 1);
Integer thirdElem = li.get(i + 2);
Integer fourthElem = li.get(i + 3);
if (elem.equals(nextElem) && nextElem.equals(thirdElem) && thirdElem.equals(fourthElem)) {
i = i + 3;
} else {
return false;
}
} else {
return false;
}
}
}
return true;
}
private static boolean inRange(int i) {
return i >= 0 && i < n;
}
}
위 로직이 바로 떠오른 가장 1차원적인 로직이었습니다. 하지만 위 로직은 2,3,4에 대해 생짜로 하드코딩을 해서 구현한 상황입니다.
차근차근 생각해보면 위와 같은 상황은 반복되는 부분이 arr[i] == arr[i+1] 맥락이 반복되며, 그 숫자 만큼 i = i + k 만큼 되는 것을 알 수 있습니다.
따라서 위 로직은 다음과 같이 개선될 수 있습니다.
public class Main {
...
private static boolean isBeautifulNum(List<Integer> li) {
for (int i = 0; i < li.size(); i++) {
Integer elem = li.get(i);
while (--elem > 0) {
if (inRange(i + 1)) {
Integer nextElem = li.get(i + 1);
if (elem.equals(nextElem)) {
i = i + 1;
} else {
return false;
}
} else {
return false;
}
}
}
return true;
}
...
}
위와 같이 개선하니까 조금이지만 실행 속도 또한 향상된 것을 알 수 있었습니다.