[백준] 17281.⚾ 야구공 (java) / 시뮬레이션, Next-Permutation, 순열

@시뮬레이션, Next-Permutation, 순열 / 1h 30m

푸는건 1시간만에 풀었는데, 알고보니 문제를 잘못 이해했었다.

다시 풀어서 제출.

Gold4로 되어있는데 생각보다 무난한 문제였다

 

 

 

문제 링크

https://www.acmicpc.net/problem/17281

17281번: ⚾

 

 

구현 방법

1. 타순을 미리 정해두고

2. 그 타순으로 N이닝 동안의 득점 합을 구한다.

3. 가장 높은 득점을 출력한다.

 

- 무조건 1번째 타자가 4번째로 가야 하므로, 2-9번째 수만 배열로 돌린 뒤 1번째 타자를 4번째 자리에 넣어준다.

- 홈, 1루, 2루, 3루 를 표시할 int[4]짜리 배열을 만들어 두고, 공을 친 결과에 따라 각 배열의 값을 이동시켜준다.

 

 

 

구현 포인트

이 문제는 Next-Permutation로 풀기 딱 좋은 문제다.

왜냐하면 중복되는 숫자가 여러번 등장하는데, 재귀를 사용하면 중복수가 여러번 나온다(ex)1223이면 2231이 두번 출력된다).

그렇지만 Next-Permutation를 사용하면 중복값은 출력되지 않고, 모든 값들이 한번씩만 나온다.

 

 

 

삽질 포인트

"두 팀은 경기가 시작하기 전까지 타순(타자가 타석에 서는 순서)을 정해야 하고, 경기 중에는 타순을 변경할 수 없다."

이 경기 중이라는 부분을 한 이닝으로 잘못 이해해서, 코드를 잘못 구현했다.

저 경기 중이라는 뜻은 게임이 시작해서 끝날 때까지를 의미한다. 즉, 타순을 한번 정하면 모든 이닝이 끝날 때까지 바꿀 수 없게 된다.

그래서 (넥퍼로 타순을 정하고-모든 이닝을 돌고) 이 작업을 반복한다

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	private static int N, num[][], np[], temp[];

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		num = new int[N][9];
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < 9; j++)
				num[i][j] = Integer.parseInt(st.nextToken());
		}

		int maxSum = Integer.MIN_VALUE;
		//np는 1번인덱스-8번인덱스까지만 돌리고, 0번인덱스를 3번인덱스 자리에 넣어준
		np = new int[]{0, 1, 2, 3, 4, 5, 6, 7, 8};
		do {
			temp = np.clone();
			int t = temp[0];
			temp[0] = temp[1];
			temp[1] = temp[2];
			temp[2] = temp[3];
			temp[3] = t;
			int sum = calc();
			if (maxSum < sum) maxSum = sum;
		} while (nextPermutation());

		System.out.println(maxSum);
	}

	private static int calc() {
		int sum = 0, i = 0;
		for (int in = 0; in < N; in++) {
			
			int out = 0;
			int[] field = new int[4];
			while (out < 3) {
				if (num[in][temp[i]] == 0) {
					out++;
				} else {
					field[0]++;
					sum += move(field, num[in][temp[i]]);
				}
				i = (i + 1) % 9;
			}
		}
		return sum;
	}

	private static int move(int[] field, int num) {
		int sum = 0;
		if (num == 1) {
			sum += field[3];
			for (int i = 2; i >= 0; i--)
				field[i + 1] = field[i];
			field[0] = 0;
		} else if (num == 2) {
			sum += field[2] + field[3];
			for (int i = 1; i >= 0; i--)
				field[i + 2] = field[i];
			field[1] = field[0] = 0;
		} else if (num == 3) {
			sum += field[1] + field[2] + field[3];
			field[3] = field[0];
			field[2] = field[1] = field[0] = 0;
		} else {
			sum += field[0] + field[1] + field[2] + field[3];
			field[3] = field[2] = field[1] = field[0] = 0;
		}
		return sum;
	}

	private static boolean nextPermutation() {
		int i = 9 - 1;
		while (i > 1 && np[i - 1] >= np[i]) i--;
		if (i == 1) return false;
		
		int j = 9 - 1;
		while (np[i - 1] >= np[j]) j--;
		swap(i - 1, j);
		
		j = 9 - 1;
		while (i < j) swap(i++, j--);
		return true;
	}

	private static void swap(int i, int j) {
		int temp = np[i];
		np[i] = np[j];
		np[j] = temp;
	}
}

 

 

+ 인덱스 문제

처음에는 첫번째 for문과 세번째 for문을 한번에 처리 가능 할 줄 알았는데. 아니었다

만약 for문을 끝에서부터 --해서 돌면서 field[(i + 1)%4] = field[i]; 를 하면

3 → 0

2 → 3

1 → 2

0 → 1

 이렇게 되는데, 문제는 마지막 0번째 인덱스의 값은 이미 위에서 3번째 값이 덮어버렸기 때문에,

값이 의도한대로 출력되지 않는다. (+그래서 swap할 때, 또는 인덱스를 한 칸씩 미루거나 당길 때 temp를 두는 것과 같은 의미!)

 

그래서 for문을 나눠서 구현했다!

 

(그런데 move 부분을 함수로 모듈화시켜서 이렇게 고쳤더니 시간이 거의 400대에서 800대로 늘었다. 이유는 선생님께 여쭤보고 나서 추가해야겠다..!)

private static int move(int[] field, int num) {
    int sum = 0;

    for (int i = 3; i >= 4 - num; i--)
    sum += field[i];

    for (int i = 3 - num; i >= 0; i--)
    field[i + num] = field[i];

    for (int i = 0; i < num; i++)
    field[i] = 0;

	return sum;
}

아래가 그냥 푼 코드, 위가 함수로 모듈화 한 코드

 

어려워 보였는데 생각보다 쉬운 문제였다.

 

끝!