안녕하세요. 오늘은 프로그래머스의 N으로 표현이라는 문제를 풀어보겠습니다. 이 문제는 (1) DFS를 이용 (2) set을 이용 (3) dp를 이용 총 세 가지 풀이가 있어서, 하나하나 차례대로 포스팅할 예정입니다. 오늘은 (1) DFS를 이용한 풀이에 대해 설명해보겠습니다.
1. 문제 링크
https://programmers.co.kr/learn/courses/30/lessons/42895
2. DFS를 이용한 문제 풀이
✔ answer를 Integer.MAX_VALUE로 초기화
answer 결과는 가장 작은 값이므로, Integer.MAX_VALUE로 초기화해줍니다.
✔ dfs 수행 - 파라미터 설명
dfs를 돌면서 answer값을 구합니다. dfs의 count는 여태까지 사용한 N의 갯수이고, prev는 이전 연산 값을 저장한 파라미터입니다.
✔ dfs 수행 - return 설명
문제에서 N 사용횟수의 최솟값이 8 이상이면 -1을 return하라고 했습니다. 따라서 dfs 코드에서 count 값이 8 이상이면 -1을 return 해줍니다.
또한 연산값이 주어진 number값과 같으면 return해줍니다.
✔ dfs 수행 - tempN변수 설명
+. -. /. *으로 나눠 dfs를 타고 들어갈 때, N, NN, NNN 즉 5, 55, 555를 연산하는 경우의 수를 생각해줘야 합니다. 따라서 tempN변수를 이용해 모든 경우의 수를 탐색합니다.
3. 전체 코드
class Solution {
private int n;
private int target;
private int answer = Integer.MAX_VALUE;
public int solution(int N, int number) {
n = N;
target = number;
dfs(0, 0);
return answer == Integer.MAX_VALUE ? -1 : answer;
}
private void dfs(int count, int prev) {
if (count > 8) {
answer = -1;
return;
}
if (prev == target) {
answer = Math.min(answer, count);
return;
}
//+. -. /. *으로 나눠 dfs를 타고 들어갈 때, N, NN, NNN 즉 5, 55, 555를 연산하는 경우의 수를 생각해줘야 함
//int tempN = n;
//tempN = tempN * 10 + n;을 활용해서 모든 경우의 수 탐색
int tempN = n;
for (int i = 0; i < 8 - count; i++) {
int newCount = count + i + 1;
dfs(newCount, prev + tempN);
dfs(newCount, prev - tempN);
dfs(newCount, prev / tempN);
dfs(newCount, prev * tempN);
tempN = tempN * 10 + n;
}
}
}4. 느낀점
✔ 시간이 별로 소요되지 않는이유?
문제를 풀때마다 dfs == 오래걸리는 방법 이라고 생각했습니다. 이번 문제의 경우 dfs를 8번이나 타고 들어가야 하고, 그 와중에 다양한 경우를 따져야 해서(매 노드마다 사칙연산 4개 모두 따져봐야 함) 시간이 굉장히 많이 소요될 것이기 때문에 올바른 풀이가 아니라고 판단했습니다.
하지만 풀이를 찾아보고 확인해 본 결과 별로 시간이 많이 소요되지 않았습니다..
심지어 dp풀이보다 시간이 덜 소요된 테스트케이스도 많았습니다.
그 이유에 대해 좀 더 생각해보고 이유를 찾으면 포스팅 수정하겠습니다.
