[백준/boj] 17281: ⚾ (Java) / 순열 / 브루트포스 / 구현

문제

17281번: ⚾

풀이

import java.io.*;
import java.util.*;

public class Main {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static int inningNum;
	static int[] order;
	static int turn, score =0;
	static int[][] player;
	static int out = 0;
	static int[] field;
	static boolean[] isSelected;

	public static void main(String[] args) throws Exception {
		inningNum = stoi(br.readLine());
		player = new int[inningNum][9];
		
		for (int i = 0; i < inningNum; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 9; j++) {
				player[i][j] = stoi(st.nextToken());
			}
		}
		order = new int[9];
		isSelected = new boolean[9];
		field = new int[4];
		permutation(0);
		System.out.println(score);
	}
	
	private static void permutation(int cnt) {
		if(cnt == 9) {
			int inning = 0;
			turn = 0;
			int newScore=0;
			while (inning < inningNum) {
				out =0;
//				field = new int[4];
				while(out < 3) {
					newScore += game(player[inning][order[turn%9]]);
					turn++;
				}
				inning++;
			}
			score = Math.max(score, newScore);
		}

		if(cnt == 3) {
			permutation(cnt+1);
			return;
		}
		
		for(int i=1 ;i < 9; i++) {
			if(isSelected[i]) continue;
			order[cnt] = i;
			isSelected[i] = true;
			permutation(cnt+1);
			isSelected[i] = false;
		}
	}

	private static int game(int exp) {
		int newS = 0;
		if (exp == 0) {
			out++;
		}
		switch(exp) {
		case 1:
			newS += field[3];
			field[3] = field[2];
			field[2] = field[1];
			field[1] = 1;
			field[0] = 0;
			break;
		case 2:
			newS += field[3] + field[2];
			field[3] = field[1];
			field[2] = 1;
			field[1] = 0; field[0] = 0;
			break;
		case 3:
			newS += field[3] + field[2] + field[1];
			field[3] = 1;
			field[2] = 0; field[1] = 0; field[0] = 0;
			break;
		case 4:
			newS += field[3] + field[2] + field[1] + 1;
			field[3] = 0; field[2] = 0; field[1] = 0; field[0] = 0;
			break;
		}
		
		if(out == 3) {
			field[0] = 0; field[1] = 0; field[2] = 0; field[3] =0;
		}
		return newS;
	}

	static int stoi(String input) {
		return Integer.parseInt(input);
	}
}

변수 설명

• player : 이닝(행)에 해당하는 선수들의 결과(열)를 담은 int[][] 배열
• inningNum : 총 이닝 수
• inning : 현재 몇번째 이닝인지 담겨져 있다.
• order : 순서 
• turn : 현재 몇번째 선수 차례인지를 나타낸다. order의 인덱스가 된다.

이때, 중요한 점!
turn은 한 이닝이 끝나도 갱신되지 않기 때문에 한 게임이 끝날때마다 무조건 turn++ 해주어야한다. 
turn이 9가 넘어가는 상황이 생기기 때문에 turn%9 를 order의 인덱스로 사용한다. (9&9 => 0 이므로, 자연스럽게 첫번째 순서의 선수가 타석에 있게 된다.)

• field : 1루, 2루, 3루, 홈의 정보를 담고 있다. (field[1] = 1루, field[2] = 2루, field[3] = 3루, field[0] = 홈)

• out : 전역 변수로 out 이 3 이 되면 한 이닝이 종료 된다. (inning++)
• score: 답이 되는 최대 점수
• newScore: 순열이 바뀔 때마다 갱신되는 점수, score와 최댓값을 갱신해가며 최대 점수를 찾는다.

permutaion()

기본 순열 수도 코드에 순열이 하나씩 생성될 때마다 N이닝 동안 게임 (game())을 진행한다.

이 함수에서 제일 중요한 점은 

아인타는 자신이 가장 좋아하는 선수인 1번 선수를 4번 타자로 미리 결정했다.

이 조건을 만족해야한다는 점이다. 나는 이것을 cnt가 3일 때 (0부터 시작하므로 3이 order배열의 4번째 순서이다.) 다음 인덱스를 뽑는 것으로 넘겨버리고, return 해주었다. 

		if(cnt == 3) {
			permutation(cnt+1);
			return;
		}

이 코드의 위치도 중요한데, 그 이유는 아래 시행착오의 1번을 참고하면 된다.

기본 순열 코드가 이해 안된다면 아래 포스팅을 보고 오면 이해가 좀 더 쉬울수도 있다.

2021/02/15 - [언어/자바(Java)] - [Java] 순열 / 조합 / 부분 집합 정리 (수도 코드 - 재귀편)

[Java] 순열 / 조합 / 부분 집합 정리 (수도 코드 - 재귀편)

 

game()

exp는 타자의 결과를 의미한다. 

exp == 0

out이므로 out++ 해준다. field는 변화 없다.

exp == 1 

out( 홈으로 들어오는)되는 field 값(만약 선수면 1이 더해지고 비어있었다면 0이 더해질 것이다.)은  newS(return될 점수)에 더해준다.

		case 1:
			newS += field[3];
			field[3] = field[2];
			field[2] = field[1];
			field[1] = 1;
			field[0] = 0;
			break;
	

exp == 2

		case 2:
			newS += field[3] + field[2];
			field[3] = field[1];
			field[2] = 1;
			field[1] = 0; field[0] = 0;
			break;

exp == 3

		case 3:
			newS += field[3] + field[2] + field[1];
			field[3] = 1;
			field[2] = 0; field[1] = 0; field[0] = 0;
			break;

exp == 4

		case 4:
			newS += field[3] + field[2] + field[1] + 1;
			field[3] = 0; field[2] = 0; field[1] = 0; field[0] = 0;
			break;

 

이렇게 exp에 맞게 필드를 바꾼 후에 out이 3이 됐는지 확인해서 3이 됐다면 이닝이 증가할 것이므로 필드를 비워준다 (모두 0으로 초기화)

시행착오

1. 처음엔 field를 Queue 로 구현했다. 또한 permutation 함수에서

if(cnt == 3) {
	permutation(cnt+1);
	continue;
}

위 코드를 for문 안에 넣었다. 시간 초과가 났다. => 9!에서 8!으로 줄여야한다. (for문 밖으로 코드를 뺀다) Queue는 Link로 연결되어 있기 때문에 Deque보다 느리다. (Deque로 구현한다.)

2. for문 밖으로 코드를 빼고, Deque 로 field를 구현했다. 시간 초과가 났다 => Collections 를 쓰면 안된다.

3. field를 배열로 구현했다. => 통과 ! 

4. 풀이 코드에서 주석( // field = new int[4]; )을 해제하면 위에서 두번째 결과가 나오는데, 가비지 컬렉터가 계속 메모리 공간을 비워주는 것이 아닌 일정 양이 찼을때만 비워주기 때문에 메모리나 시간적으로 더 비효율적인 결과가 나온다. 한마디로, 반복문 안에서 new 는 지양하는 것이 좋다.