바둑대회 질문드립니다.

자바 코딩테스트 - it 대기업 유제

3. "바둑대회" 문제 해법

작성

247

이처럼 코드를 작성했는데 마지막 테스트 케이스 답이 0이 나옵니다. 어디가 잘못된건지 모르겠습니다.

import java.util.*;

import javax.security.auth.Subject;

import java.awt.List;
import java.io.*;


class Main {
	public static int n,answer=10000000;
	public static boolean[] visit;
	
	public int solution(int[][] cans){
		n=cans.length;
		visit = new boolean[n];
		dfs(0,0,cans);
		return answer;
	}
		public static void dfs(int L, int s, int[][] cans) {
			if(L==n/2) {
				ArrayList<Integer> a =new ArrayList<>();
				ArrayList<Integer> b =new ArrayList<>();
				
				for(int i=0; i<n; i++) {
					if(visit[i]) a.add(i);
					else b.add(i);
				}
				
				int sum1=0,sum2=0;
				for(int i=0; i<L; i++) {
					sum1+=cans[a.get(i)][0];
					sum2+=cans[b.get(i)][1];
				}
				answer = Math.min(answer, Math.abs(sum1-sum2));
			}
			else {
				for(int i=s; i<n; i++) {
					visit[i] = true;
					dfs(L+1, i+1, cans);
					visit[i] = false;
				}
			}
		}
	public static void main(String[] args){
		Main T = new Main();
		System.out.println(T.solution(new int[][]{{87, 84}, {66, 78}, {94, 94}, {93, 87}, {72, 92}, {78, 63}}));
		System.out.println(T.solution(new int[][]{{10, 20}, {15, 25}, {35, 23}, {55, 20}}));
		System.out.println(T.solution(new int[][]{{11, 27}, {16, 21}, {35, 21}, {52, 21}, {25, 33},{25, 32}, {37, 59}, {33, 47}}));
	}
}

java 코딩-테스트

답변 2

김태원

지식공유자

안녕하세요^^

answer 를 static 전역으로 잡아서 앞전 테스트 케이스의 answer를 그대로 유지하면서 다음 테스트 케이스를 실행하기 때문입니다. 아래 처럼 solution에서 매번 answer를 초기화해야 합니다.

public int solution(int[][] cans){
	answer = 10000000;
	n=cans.length;
	visit = new boolean[n];
	dfs(0,0,cans);
	return answer;
}

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴이에요. 코드를 확인해보니, dfs 함수에서 L이 n/2와 같은 경우에만 a와 b에 숫자를 나누고, sum1과 sum2를 계산하고 있네요. 그러나 L이 n/2와 같아지기 전에 이미 재귀 함수가 끝나버리는 오류가 있습니다.

dfs 함수에서 for문을 돌리면서 visit[i]를 true로 바꾸고 재귀 호출을 하고 있는데, 재귀 호출 후에 visit[i]를 false로 바꾸지 않고 있습니다. 따라서 이전 단계에서 true로 바뀐 visit[i]가 그대로 남아서 올바른 결과를 얻을 수 없게 됩니다.

해결책은 dfs 함수의 마지막 부분에 visit[i]를 false로 바꾸는 코드를 추가하는 것입니다. 아래는 수정된 코드입니다.

public static void dfs(int L, int s, int[][] cans) {
    if(L==n/2) {
        ArrayList<Integer> a =new ArrayList<>();
        ArrayList<Integer> b =new ArrayList<>();

        for(int i=0; i<n; i++) {
            if(visit[i]) a.add(i);
            else b.add(i);
        }

        int sum1=0,sum2=0;
        for(int i=0; i<L; i++) {
            sum1+=cans[a.get(i)][0];
            sum2+=cans[b.get(i)][1];
        }
        answer = Math.min(answer, Math.abs(sum1-sum2));
    }
    else {
        for(int i=s; i<n; i++) {
            visit[i] = true;
            dfs(L+1, i+1, cans);
            visit[i] = false; // 추가된 부분
        }
    }
}

이렇게 수정하고 실행해보세요. 이제 정상적인 결과가 나와야 할 거에요. 이해가 되지 않는 부분이 있다면 또 문의해주세요. 좋은 결과 있기를 바라며 화이팅하세요!

인프런 커뮤니티 질문&답변

바둑대회 질문드립니다.