[ 백준 17281 ] ⚾ 야구 - Java 시간초과

문제 링크

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

17281번: ⚾

문제 풀이

결과 자체는 금방 나오도록 풀 수 있는데 시간 초과에서 막혀서 고생한 문제이다 ㅜㅜ. 이 문제는 모든 경우의 수를 돌려보는 브루트 포스 문제고, 문제 설명에 따라 구현을 해야 하는 문제이다. 

 

다음과 같은 순서로 풀었다.

 

1. 나는 야구선수들의 순서는 순열(Permutation)을 통해서 모든 경우를 돌려보았다.

2. 그 후에 각 타자들이 공을 쳐서 얻는 결과를 큐를 통해서 구현하였다가. 시간 초과가 나서 실패하였다. (주석 처리된 부분이 그 부분)

2. 몇 루타를 쳤는지 ArrayList에 담는다.

3. 뒤에서부터 반복문을 통해 Sum 하여서 4를 넘는 순간부터 점수가 되므로 해당 index까지를 score에 더한다.

4. max값을 출력한다.

 

 

소스 코드

package test;

import java.util.ArrayList;
import java.util.Scanner;

public class P17281 {
	static int [][] scoreArr;
	static int max = 0;
	static int turn =0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int size = sc.nextInt();
		int[][] arr = new int[size][9];

		for (int i = 0; i < arr.length; i++) {
			for (int j = 0; j < arr[0].length; j++) {
				arr[i][j] = sc.nextInt();
			}
		}
		
		scoreArr = arr;
		int [] player = {1,2,3,4,5,6,7,8};
		perm(player, 0);
		System.out.println(max);
	}

	public static void perm(int[] arr, int pivot) {
		if (pivot == arr.length) {
			play(arr);
			return;
		}
		for (int i = pivot; i < arr.length; i++) {
			swap(arr, i, pivot);
			perm(arr, pivot + 1);
			swap(arr, i, pivot);
		}
	}

	public static void swap(int[] arr, int i, int j) {
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	
/*	public static void play(int[] temp) {
		int [] arr = new int[9];
		int j=0;
		for(int i=0 ; i< 9 ; i++) {
			if(i!=3) {
				arr[i] = temp[j++];
			}
		}
		Queue<Integer> ru = new LinkedList<>();
		turn = 0;
		int score=0;
		for (int i = 0; i < scoreArr.length; i++) {
			int out =0;
			int [] scores = scoreArr[i];
			ru.clear();
			ru.add(0);
			ru.add(0);
			ru.add(0);
			while (out <3) {
				int player = arr[turn++ %9 ] ;
				int ruta = scores[player];
				if(ruta == 0) out++;
				else {
					ru.add(1);
					while(--ruta>0) {
						ru.add(0);
					}
				}
				
			}
			while(ru.size()>3) {
				if(ru.poll() == 1) score++;
			}
			
		}
		max = Math.max(max, score);
	}*/
	
	
	public static void play(int[] temp) {
		int [] arr = new int[9];
		int j=0;
		for(int i=0 ; i< 9 ; i++) {
			if(i!=3) {
				arr[i] = temp[j++];
			}
		}
		
		turn = 0;
		int score=0;
		for (int i = 0; i < scoreArr.length; i++) {
			int out =0;
			int [] scores = scoreArr[i];
			ArrayList<Integer> list = new ArrayList<>();
			while (out <3) {
				int player = arr[turn++ %9 ] ;
				int ruta = scores[player];
				if(ruta == 0) out++;
				else list.add(ruta);
			}
			int sum =0;
			for (int k = list.size() -1; k >= 0; k--) {
				sum += list.get(k);
				if(sum >= 4) {
					score += k+1;
					break;
				}
			}
		}
		max = Math.max(max, score);
	}
	
	
}

테스트 케이스

시간초과가 나나 확인할때 돌려본 테스트 케이스이다.

 

50
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0
4 4 4 4 4 4 4 4 0