[BOJ] 백준 17281. 야구

문제

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

17281번: ⚾

---

풀이

순열이 포함된 구현 문제입니다.

 

 처음에는, 점수를 계산하는 과정을 큐로 구현을 했습니다. Base를 돌고 홈으로 오는 선수들을 큐 자료형을 표현했는데 시간 초과가 나서, 점수를 산정하는 과정을 boolean[] 배열을 통해 경우를 따져가는 식으로 변경했습니다.

 그리고 순열 시에 1번 타자는 항상 4번 째에 위치하는 것을 고려해, 해당 depth일 때는 배정을 한 칸씩 뒤로 미루었습니다. 

 

 

아래는 소스 코드와, 추가로 큐로 구현했던 코드(시간 초과남) 입니다.

---

소스 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int N;
    static int maxScore = -5;
    static int score;
    static int[][] players;
    static int[] orders = new int[9];
    static boolean[] visited = new boolean[9];

    public static void main(String[] args) {
        input();
        setOrder(0);
        System.out.println(maxScore);
    }
    static void input(){
        N = sc.nextInt();
        players = new int[N][9];
        for(int i =0;i<N;i++){
            for(int j=0;j<9;j++){
                players[i][j] = sc.nextInt();
            }
        }
    }

    static void setOrder(int depth){
        if(depth == 8){
            playGame(orders);
            maxScore = Math.max(maxScore,score);
        }
        else {
            for (int i = 1; i < 9; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    if(depth>=3) orders[depth+1] = i;
                    else orders[depth] = i;
                    setOrder(depth + 1);
                    visited[i] = false;
                }
            }
        }
    }
    static void playGame(int[] order){
        int inning = 0;
        int nowNum = 0;
        score = 0;

        for(int r=0; r<N; r++) {
            int inningScore = 0;
            int outCnt = 0;
            boolean[] base = new boolean[4];

            while(outCnt < 3) {
                switch(players[r][order[nowNum]]) {
                    case 0:
                        outCnt++;
                        break;
                    case 1:
                        if(base[3]) {
                            inningScore++;
                            base[3] = false;
                        }
                        if(base[2]) {
                            base[3] = true;
                            base[2] = false;
                        }
                        if(base[1]) {
                            base[2] = true;
                        }
                        base[1] = true;
                        break;
                    case 2:
                        if(base[3]) {
                            inningScore++;
                            base[3] = false;
                        }
                        if(base[2]) {
                            inningScore++;
                        }
                        if(base[1]) {
                            base[3] = true;
                            base[1] = false;
                        }
                        base[2] = true;
                        break;
                    case 3:
                        if(base[3]) {
                            inningScore++;
                        }
                        if(base[2]) {
                            inningScore++;
                            base[2] = false;
                        }
                        if(base[1]) {
                            inningScore++;
                            base[1] = false;
                        }
                        base[3] = true;
                        break;
                    case 4:
                        if(base[3]) {
                            inningScore++;
                            base[3] = false;
                        }
                        if(base[2]) {
                            inningScore++;
                            base[2] = false;
                        }
                        if(base[1]) {
                            inningScore++;
                            base[1] = false;
                        }
                        inningScore++;
                        break;
                }
                nowNum++;
                if(nowNum > 8) {
                    nowNum = 0;
                }
            }
            score += inningScore;
        }

    }
}

 

 

 

 

시간 초과 코드 참고 (Queue)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static int N;
    static int maxScore = -5;
    static int[][] players;
    static int[] orders = new int[9];
    static boolean[] visited = new boolean[9];

    public static void main(String[] args) {
        input();
        setOrder(0);
        System.out.println(maxScore);
    }
    static void input(){
        N = sc.nextInt();
        players = new int[N][9];
        for(int i =0;i<N;i++){
            for(int j=0;j<9;j++){
                players[i][j] = sc.nextInt();
            }
        }
    }

    static void setOrder(int depth){
        if(depth == 8){
            playGame(orders);
        }
        else {
            for (int i = 1; i < 9; i++) {
                if (!visited[i]) {
                    visited[i] = true;
                    if(depth>=3) orders[depth+1] = i;
                    else orders[depth] = i;
                    setOrder(depth + 1);
                    visited[i] = false;
                }
            }
        }
    }
    static void playGame(int[] order){
        int inning = 0;
        int nowNum = 0;
        int score = 0;
        int outCnt = 0;
        Queue<Integer> base = new LinkedList<>();

        while(inning<N){
            int playerNum = order[nowNum];
            int ru = players[inning][playerNum];

            if(ru!=0){
                base.add(1);
                for(int r= 1;r<ru;r++){
                    base.add(0);
                }
                while (base.size() > 3) {
                    if (base.poll() == 1) score++;
                }
            }
            else outCnt++;

            nowNum++;
            if(nowNum>8) nowNum=0;

            if(outCnt==3) {
                outCnt=0;
                inning++;
                base = new LinkedList<>();
            }
        }
        maxScore = Math.max(maxScore,score);
    }
}