프로그래머스 - 단체사진 찍기 [자바] (feat. += , + 차이)

• 문제 링크 : 단체사진 찍기

코딩테스트 연습 - 단체사진 찍기

 

정답

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