야근 지수 (프로그래머스 Level 3)

알고리즘 연습노트

오늘의 문제

• 야근 지수 (프로그래머스 Level 3)

내가푼 코드

public class problem145 {
    static int MAX = 0;
    static int baseArray[] = new int[3];
    
    public static void solution(int N, int[] W){
        if(N == 0){
            int temp = 0;
            System.out.print("this time : ");
            for(int i = 0; i < W.length; i++){
                System.out.print(W[i]);
                temp += Math.pow(W[i], 2);
            }
            System.out.println();
            MAX = Math.max(MAX, temp);
            System.out.println(MAX);
            W = baseArray.clone();
            return;
        }
        
        
        for(int i = 0; i < W.length; i++){
            W[i] = W[i]-1;
            solution(N-1, W);
        }
        return;
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int work[] = {4,3,3};
        int n = 4;
        
        baseArray = work.clone();
        solution(n, work);
    }

}

설계 노트

1. 전체탐색을 하여서 최소의 경우를 찾을려고 함.
2. 시간(N)과 각 작업량을 한개씩 줄여(-1) 재귀 호출을 한다.
3. 시간(N)을 다 사용하면 현재의 작업량에 대한 야근지수를 구한다.
4. 이전에 구한 야근지와 비교하여 최대값을 구한다.

발견된 오류 및 코드 분석

1. 배열의 값은 call by reference여서 함수를 return 하여도 이전의 값으로 원복 되지 않는다.

   • 전체 탐색자체가 구현하기 쉽다는 착각에서 접근을 하였지만 오히려 재귀의 함수에 봉착.

2. 전체 탐색을 하는 재귀 호출부분도 잘못되었다.

   • 각 작업별 접근을 하기 위해서 작업의 길이만큼 반복을 하게 두었는데, 전체의 경우를 탐색하지 못하는 것 같다.
   • 화면에 숫자를 찍어서 전체의 경우의 수를 도는지 확인이 필요.

소요 시간

1. 설계 25분
2. 구현 25분
3. 오류분석 25분

참고한 사이트

• 경영학도의 좌충우돌 프로그래밍
• WONJOON LEE's blog