문제 탐색하기
입력 자료 정리
- 입력으로 들어오는 N은 정수지만 주어진 문제를 해결하기 위해 문자열로 보면 된다.
해결방법 추론
- 선택지가 두개고, 각 원소를 하나씩 뽑아서 선택하여 모든 경우의 수를 다 맞춰본 뒤,
N과 같은 경우 개수를 세어주어서 출력하면 되는 문제로 보인다 - 백트래킹을 사용하면 쉽게 해결할 수 있겠다고 생각하였다
- 단순히 문자열의 길이를 앞에다가 붙이는 방법으로는 이 문제를 해결하기에 무리가 있다
- 왜냐하면 앞에도 붙이는 경우가 존재하기 때문이다. 따라서 기존과는 다른 방법을 사용해야한다
- 일단 각 문자열 지점을 시작으로 하도록 N의 길이만큼 순회하여 첫 문자를 선택하도록 했다
- 그 다음 선택지에 있어서 만약 누적되는 문자열이 N의 길이와 같다면
같은지 체크하고, 개수를 세어준뒤 종료하도록 설계하였다. - 만약 왼쪽과 오른쪽으로 가는 범위를 벗어나는 경우는 다시 뒤로 돌아가서 문자를 선택하도록 하였다
- 방문 배열을 하나 만들어서 중복 선택을 하지 않도록 구현하였다
- 이렇게 완성한 ans를 출력하면 정답이 될 것이라 생각하였다
시간복잡도 계산
- 시간 복잡도는 간단하다. 일단 n이 엄청 큰데 그냥 저 수를 문자로 바꿨을 때 길이로 보면된다
- 즉 총 8개의 숫자가 최대 입력값이므로,
시간복잡도는 O(n x 2^n)일때, 시간제한 없이 문제를 해결할 수 있음을 알 수 있다.
코드 설계하기
입력값 상태 관리하기
- 입력값은 문자열로 관리하였다.
이후, 재설계에서는 더 편리하게 관리하도록 문자 배열로 바꾸어 관리하였다
해결하지 못한 고민
- 한가지 문제에서 주어진 조건을 완전히 이해하지도, 구현하지도 못했다
- 바로 숫자를 적는 과정에서 나온 수가 순서대로 모두 같다면 같은 방법이라는 내용이다
- 일단 중복을 제거하라는 말인 것 같아 Set을 사용해야하는 것 같은데,
문제는 현재 선택한 방법은 결국 문자열을 완성시켜 나가는 과정만 존재하고,
그 끝에서 검사할 때는 다 같은 문자열이라 중복이 되지 않는다 생각하여 필요없다고 생각하였다 - 과정에 대한 정확한 이해가 되지 않고 코드를 계속 설계해나갔다.
백트래킹 구현
함수식
- backtracking(String s, int size, int depth)
1. s에 선택한 문자를 계속 더해나가며 size와 길이가 같아질 때가 base condition이된다
2. depth가 -1보다 작거나 같으면 depth에 size-1로 갱신해주었고,
depth가 size와 같으면 depth를 0으로 갱신해주었다
재귀식
- backtracking(s + n.charAt(depth), size, depth+1)
- backtracking(n.charAt(depth) + s, size, depth-1)
- 위 재귀식이 현재 depth를 미방문했을 때 실행시켜주고,
방문 체크와 백트래킹 종료 후, 방문 체크를 해주는 방식으로 진행하였다
base condition
- if(s.length() == size) {...}
1. 길이가 전체 문자열 n의 크기와 같아지면 종료한다
2. 만약 s가 n과 같다면 ans의 값을 증가시켜준다
출력값 설계
- 완성한 ans를 출력하면 정답이 될 텐데...
시도회차 수정
1회차 실패
- 1%에서 틀렸습니다가 나와버렸다...
문제 인식
- 일단 1%에서 틀리면 높은 확률로 코드 설계에 결함이 있다는 것이다.
- 문제 파악을 잘못하였고, 코드 설계 로직도 잘못되었다는 것이다
- 앞서 해결하지 못한 문제에서 주어진 조건에 대한 이해부분에서 틀리지 않았나 싶다.
기존 코드 재설계
- 일단 입력값 상태 관리부터 재설계하였다. 문자열에서 문자 배열로 변경하여 관리하였다
- left와 right 두개의 포인터를 파라미터를 추가하였다
left, right 포인터로 간소화
- 기존에는 depth 하나를 가지고 구분 없이 재귀를 두번 돌렸었다
- 더 간소화하고, 불필요한 탐색을 줄이기 위해 left와 right로 나누었다
- left-1이 0보다 크거나 같은 경우거나 right+1이 문자배열의 길이보다 작은 경우만
dfs를 돌리도록 하여 불필요한 탐색을 줄였다 - 왼쪽에 붙이는 경우는 left-1로 그 범위를 줄여나가고 arr[left-1] + s로 왼쪽에 붙여준다
- 오른쪽에 붙이는 경우는 right-1로 그 범위를 줄여나가고 arr[right-1] + s로 오른쪽에 붙여준다
숫자를 적는 과정 누적 설계
- 숫자를 선택하는 과정을 경로로 누적해 나가면 미해결했던 문제에 대해 해결할 수 있을 것이다
- path라는 문자열 파라미터를 하나 더 선언하였다.
초기에는 완성해나가는 문자열처럼 초기 문자 하나로 선언해서 관리한다 - 이어서 각 dfs과정에서 기존 path에 " "라는 빈칸을 두고 arr[left] + s 또는
s + arr[right]로 선택해온 과정을 더해나간다
중복된 과정 제거
- 이제 과정을 누적해서 관리할 수 있게 되었다.
중복된 과정은 제외하고 그 개수를 세어주어야 하므로 HashSet 자료구조를 사용하였다 - base Condition에 도달하면 set에 path를 넣어준다
출력 재설계
- ans 변수를 없애고 경로의 개수를 담은 set을 출력하면 정답이 된다.
2회차 시도 성공
- 재설계로 인해 바로 성공하였다.
앞으로 적용할 부분
- 해결되지 않은 문제가 발견되면 꼭 해결방법을 깊게 모색해보자
- 경로에 대해서도 누적하는 백트래킹이 존재함을 꼭 기억해두자
정답 코드
(1회차 시도 실패)
import java.io.*;
import java.util.*;
public class Main {
static int ans = 0;
static String n;
static boolean[] visited;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = br.readLine();
int size = n.length();
visited = new boolean[size];
for (int i = 0; i < size; i++) {
backtracking("", size, i);
}
bw.write(ans+"");
br.close();
bw.close();
}
private static void backtracking(String s, int size, int depth) {
if(s.length() == size){
if(s.equals(n)){
ans++;
}
return;
}
if(depth <= -1){
depth = size-1;
}
if(depth == size){
depth = 0;
}
if(!visited[depth]){
visited[depth] = true;
backtracking(s + n.charAt(depth), size, depth + 1);
backtracking(n.charAt(depth) + s, size, depth - 1);
visited[depth] = false;
}
}
}
(2회차 시도 성공)
import java.io.*;
import java.util.*;
public class Main {
static char[] arr;
static Set<String> set;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
arr = br.readLine().toCharArray();
set = new HashSet<>();
for (int i = 0; i < arr.length; i++) {
dfs(i, i, "" + arr[i], "" + arr[i]);
}
bw.write(set.size()+"");
br.close();
bw.close();
}
private static void dfs(int left, int right, String s, String path) {
if(left == 0 && right == arr.length-1){
set.add(path);
return;
}
if(left - 1 >= 0){
dfs(left-1, right, arr[left-1] + s, path + " " + arr[left] + s);
}
if(right + 1 < arr.length){
dfs(left, right+1, s + arr[right+1], path + " " + s + arr[right]);
}
}
}
문제 링크
Software Developer