6808. 규영이와 인영이의 카드게임 - 자바(JAVA)

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWgv9va6HnkDFAW0 

SW Expert Academy

 

문제 해석

1~18까지의 수가 적인 18장의 카드가 존재한다.

아홉 라운드에 걸쳐 게임이 진행하며 한 번의 게임에 둘은 카드를 잘 섞어 9장씩 나눈다.

한 라운드에는 한 장씩 카드를 낸다.

카드의 수를 비교해서 점수를 계산한다.

높은 수가 적힌 카드를 낸 사람은 두 카드에 적힌 수의 합만큼 점수를 얻는다.

낮은 수가 적힌 카드를 낸 사람은 아무런 점수도 얻을 수 없다.

 

두 사람의 총점이 같으면 무승부이다.

게임에 규영이가 받은 9장의 카드에 적힌 수가 주어진다.

규영이가 내는 카드의 순서를 고정했을 때, 인영이가 어떻게 카드를 내는지에 따른 9! 가지 순서에 따라 규영이의 승패가 결정될 것이다.

이때, 규영이가 이기는 경우와 지는 경우가 총 몇 가지 인지 구하라.

 

 

문제 풀이 전 설계

9! 가지 경우의 수를 모두 구해야 한다.

카드의 순서를 어떻게 정하느냐가 게임의 승패를 가르기 때문에 이는 순서가 중요한 순열 알고리즘을 사용한다.

 

규영이의 카드를 기반으로 인영이의 카드를 구해야 한다.

순열로 생성된 인영이의 카드를 기반으로 규영이가 이기는지 지는지 구해야 한다.

코드

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

public class Solution_6808_규영이와인영이의카드게임 {
	static int winCount, loseCount;
	static int[] gyuCardList, youngCardList, permutatedList;
	static boolean[] visitedList;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int tc = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();

		for (int t = 1; t <= tc; t++) {
			visitedList = new boolean[9];
			youngCardList = new int[9];
			gyuCardList = new int[9];
			permutatedList = new int[9];
			winCount = 0;
			loseCount = 0;
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < 9; i++) {
				gyuCardList[i] = Integer.parseInt(st.nextToken());
			}

			createYoungCardList();			
			permutation(0);

			sb.append("#" + t + " " + winCount + " " + loseCount + "\n");			
		}
		System.out.print(sb);
	}

	private static void createYoungCardList() {
		int index = 0;
		for (int i = 1; i <= 18; i++) {
			boolean isDuplicated = false;
			for (int j = 0; j < 9; j++) {
				if (gyuCardList[j] == i) {
					isDuplicated = true;
					break;
				}
			}
			if (isDuplicated) {
				continue;
			}
			youngCardList[index++] = i;

		}
	}

	private static void permutation(int cnt) {
		if (cnt == 9) {
			calculateWhoWin();
			return;
		}

		for (int i = 0; i < 9; i++) {
			if (visitedList[i]) {
				continue;
			}

			visitedList[i] = true;
			permutatedList[cnt] = youngCardList[i];
			permutation(cnt + 1);
			visitedList[i] = false;

		}
	}

	private static void calculateWhoWin() {
		int gyuScore = 0;
		int youngScore = 0;
		for(int i=0; i<9; i++) {
			if(gyuCardList[i] > permutatedList[i]) {
				gyuScore += (gyuCardList[i] + permutatedList[i]);
				continue;
			}
			
			if(permutatedList[i] > gyuCardList[i]) {
				youngScore += (gyuCardList[i] + permutatedList[i]);
				continue;
			}			
		}
		if(gyuScore > youngScore) {
			winCount++;
		}
		if(youngScore > gyuScore) {
			loseCount++;
		}
		
	}
}