[Programmers] PCCP 모의고사 #2 체육대회 JAVA

728x90

반응형

[Programmers] PCCP 모의고사 #2 체육대회

---

접근

• DFS
• 재귀 함수
• 백트래킹

---

풀이

학생의 수가 최대 10명이길래 처음엔 DFS를 이용해 구현해보려 했다. 정답은 맞혔지만 학생수가 10명 밖에 되지 않는데도 불구하고 효율이 매우 좋지 않았다. 아마 BFS를 사용했다면 시간초과가 났을 것이다.

private static class State {
	private final int step;
	private final int abilitySum;
	private final boolean[] checkAbility;
	private final boolean[] checkStudent;

	public State(int step, int abilitySum, boolean[] checkAbility, boolean[] checkStudent) {
		this.step = step;
		this.abilitySum = abilitySum;
		this.checkStudent = checkStudent.clone();
		this.checkAbility = checkAbility.clone();
	}
}

재귀함수 보다 Stack이나 Queue를 사용하는 것을 선호하기 때문에 상태를 저장할 class를 선언했다.

int answer = 0;
Stack<State> stack = new Stack<>();
stack.push(new State(0, 0, new boolean[ability[0].length], new boolean[ability.length]));

스택에 초기값을 넣어주고

while (!stack.isEmpty()) {
	State state = stack.pop();

	int step = state.step;
	int abilitySum = state.abilitySum;
	boolean[] checkStudent = state.checkStudent;
	boolean[] checkAbility = state.checkAbility;

while문 아래서 탐색을 수행한다.

if (step == ability[0].length) {
	answer = Math.max(answer, abilitySum);
	continue;
}

모든 운동 종목을 다 선택했을 경우 answer값과 비교해 최댓값으로 채운다.

for (int i = 0; i < ability.length; i++) {
	if (!checkStudent[i]) { 
		boolean[] newCheckStudent = checkStudent.clone();
		boolean[] newCheckAbility = checkAbility.clone();

		newCheckStudent[i] = true; 
		newCheckAbility[step] = true; 

		stack.push(new State(step + 1, abilitySum + ability[i][step], newCheckAbility, newCheckStudent));
	}
}

중복을 체크해 줄 배열들인데 true로 바꾸고 que에 넣은 뒤 다시 false로 바꿔줘도 되지만 새로운 배열을 생성해 넣어주는 게 보기 깔끔한 거 같아 이렇게 해줬다. 물론 메모리 측면에선 새로운 배열을 계속 생성하기 때문에 좋지 않다. 이렇게 하면 학생수와 운동의 개수가 늘어날 경우 효율이 매우 좋지 않은 것을 확인했다.

---

성능 개선

효율을 개선하기 위해 백트래킹 가지치기를 위한 코드를 추가해 주었다. 백트래킹이란 해를 찾는 과정 중 절대 해가 될 수 없는 값이라면 돌아가서 다시 해를 찾는 기법이다. 즉 이 문제는 최댓값을 구하는 문제로 가지치기를 위해선 각 step마다 최댓값들을 갱신해 주면서 해당 step의 최댓값보다 지금 탐색 중인 값이 낮다면 탐색 중이던 값을 결과적으로 최댓값이 될 가능성이 없기 때문에 더 이상 탐색을 해주지 않는 것이다.

int potentialMax = abilitySum;

for (int i = step; i < ability[0].length; i++) {
	int maxForThisStep = 0;
	for (int j = 0; j < ability.length; j++) {
		if (!checkStudent[j]) {
			maxForThisStep = Math.max(maxForThisStep, ability[j][i]);
		}
	}
	potentialMax += maxForThisStep;
}

if (potentialMax <= answer) {
	continue;
}

가지치기를 위한 변수를 선언하고 현재 상태의 능력치의 합으로 초기화해 준다. 현재 단계에서 앞으로 남은 단계에 최댓값들을 찾아 더해준다. 만약 그렇게 예상하는 값이 현재 최댓값으로 설정된 answer보다 낮거나 같다면 그 경로는 더 이상 탐색할 필요가 없기 때문에 탐색을 종료한다.

가지치기 전	가지치기 후

 

특히 테스트 케이스 3번과 8번에선 엄청난 효율이 상승된 것을 볼 수 있다. 870ms, 390MB를 기록하던 것이 5~10ms, 70MB로 굉장한 효율 상승이다. Stack이 아닌 재귀함수를 사용해 구현했을 경우 미세하지만 조금 더 효율이 좋아진 것을 확인했다.

Stack DFS	재귀 함수 DFS

 

재귀 함수를 사용할 경우 코드가 간결해지고 Stack을 사용하지 않아 스택 연산 시 발생할 수 있는 동기화 오버헤드 문제가 없어 효율이 좀 더 잘 나온다고 생각하면 될 것 같다.

---

전체 코드

Stack DFS

import java.util.*;

class Solution {
    private static class State {
        private final int step;
        private final int abilitySum;
        private final boolean[] checkAbility;
        private final boolean[] checkStudent;

        public State(int step, int abilitySum, boolean[] checkAbility, boolean[] checkStudent) {
            this.step = step;
            this.abilitySum = abilitySum;
            this.checkStudent = checkStudent.clone();
            this.checkAbility = checkAbility.clone();
        }
    }

    public int solution(int[][] ability) {
        int answer = 0;
        Stack<State> stack = new Stack<>();
        stack.push(new State(0, 0, new boolean[ability[0].length], new boolean[ability.length]));

        while (!stack.isEmpty()) {
            State state = stack.pop();

            int step = state.step;
            int abilitySum = state.abilitySum;
            boolean[] checkStudent = state.checkStudent;
            boolean[] checkAbility = state.checkAbility;

       
            if (step == ability[0].length) {
                answer = Math.max(answer, abilitySum);
                continue;
            }

  
            int potentialMax = abilitySum;
            for (int i = step; i < ability[0].length; i++) {
                int maxForThisStep = 0;
                for (int j = 0; j < ability.length; j++) {
                    if (!checkStudent[j]) {
                        maxForThisStep = Math.max(maxForThisStep, ability[j][i]);
                    }
                }
                potentialMax += maxForThisStep;
            }
            if (potentialMax <= answer) {
                continue;
            }

      
            for (int i = 0; i < ability.length; i++) {
                if (!checkStudent[i]) { 
                    boolean[] newCheckStudent = checkStudent.clone();
                    boolean[] newCheckAbility = checkAbility.clone();

                    newCheckStudent[i] = true; 
                    newCheckAbility[step] = true; 

                    stack.push(new State(step + 1, abilitySum + ability[i][step], newCheckAbility, newCheckStudent));
                }
            }
        }

        return answer;
    }
}

 

재귀 함수 DFS

public class Solution {
    private int maxAbilitySum;

    public int solution(int[][] ability) {
        maxAbilitySum = 0; 
        boolean[] selected = new boolean[ability.length]; 
        backtrack(ability, selected, 0, 0); 
        return maxAbilitySum; 
    }

    private void backtrack(int[][] ability, boolean[] selected, int step, int currentSum) {
        int potentialMax = currentSum;
        for (int i = step; i < ability[0].length; i++) {
            int maxForThisStep = 0;
            for (int j = 0; j < ability.length; j++) {
                if (!selected[j]) {
                    maxForThisStep = Math.max(maxForThisStep, ability[j][i]);
                }
            }
            potentialMax += maxForThisStep;
        }


        if (potentialMax <= maxAbilitySum) {
            return;
        }

  
        if (step == ability[0].length) {
            maxAbilitySum = Math.max(maxAbilitySum, currentSum); 
            return;
        }


        for (int i = 0; i < ability.length; i++) {
            if (!selected[i]) { 
                selected[i] = true; 
                backtrack(ability, selected, step + 1, currentSum + ability[i][step]);  
                selected[i] = false; 
            }
        }
    }
}