-
프로그래머스 - 단체사진 찍기 [자바] (feat. += , + 차이)Algorithms/- 프로그래머스 2022. 2. 6. 22:18
- 문제 링크 : 단체사진 찍기
정답
class Solution { private int answer = 0; private String[] arr = {"A", "C", "F", "J", "M", "N", "R", "T"}; public int solution(int n, String[] data) { boolean[] v = new boolean[arr.length]; dfs("", v, data); return answer; } private void dfs(String str, boolean[] v,String[] data){ if(str.length() == arr.length){ if(check(str, data)){ answer++; } return; } for(int i=0; i<arr.length; i++){ if(!v[i]){ v[i] = true; String temp = str + arr[i]; dfs(temp, v, data); v[i] = false; } } } private boolean check(String str, String[] data){ for(String dStr : data){ int a = str.indexOf(dStr.charAt(0)); int b = str.indexOf(dStr.charAt(2)); char c = dStr.charAt(3); int d = dStr.charAt(4) - '0'; if(c == '>'){//큰거 if(!(Math.abs(a-b) -1 > d)){ return false; } }else if(c == '<'){ if(!(Math.abs(a-b) -1 < d)){ return false; } }else{ if(!(Math.abs(a-b) - 1 == d)){ return false; } } } return true; } }
분석
- dfs문제 인데 이해가 잘 안된다.
- 아래 참조를 보고 푼 내용이다.
- 나만의 방법으로 다시 정리할 예정이다.
알고리즘 오답 이유 해결
- 계속 틀리고 이해가 되지 않는 이유를 알게 되었다.
위 코드 중
String temp = str + arr[i]; dfs(temp, v, data);
이 부분을 원래는
dfs(str += arr[i], v, data);
이렇게 구현을 하였고 계속 오답이 나왔다.
그래서 다른 해답을 참고해서 현재의 정답과 같이 풀었는데
이렇게 풀면 틀리는 이유에 대해서 원인을 찾게 되었다.
java에서는 +=연산이 아래와 같은 순서로 동작하기 때문에
//3 + 2 + 1을 만들기 위해한 재귀함수 fun() Here is what Java is doing: inside fun(3) sum += fn(n-1) // sum is 0 becomes sum = 0 + fun(2) // sum is 0 Then inside fun(2) sum = 0 + fun(1) // sum is 0 Then inside fun(1) return 1 // sum is 0 Back inside fun(2) sum = 0 + 1; // sum is 0 becomes sum = 1; // sum will soon become 1 Back inside fun(3) sum = 0 + 1; // sum is 1 becomes sum = 1; // sum gets reset to 1
우리가 재귀에서 원하는 3 + 2 + 1이 아니라 1이 나오는 것이다.
원래 문제로 돌아가서 보면
//1 번 방식 String temp = str + arr[i]; //2 번 방식 str += arr[i];
1번과 2번 방식은 다른 결과를 출력하게 되고
우리가 재귀에서 원하는 방식은 1번의 방식이기 때문에 1번 처럼 작성하였을때만 결과가 일치하게 출력되는 것이다.
문제를 알았으므로
String temp = str + arr[i]; dfs(temp, v, data);
을 간단하게
dfs(str + arr[i], v, data);
이렇게 수정하면 될 것 같다.
참조
[알고리즘] 프로그래머스 단체사진 찍기 (2017 카카오코드 본선) -DFS- 자바
Different results in Java and C++ using += in recursion반응형