Study/Problem Solving

[SWEA / Java] 6808번: 규영이와 인영이의 카드게임 (D3)

Pearlii 2023. 8. 21. 15:28

문제 풀이 날짜: 2023.08.10
포스트 작성일: 2023.08.21

 

* 학습 목적으로 작성하는 글입니다. 풀이가 정석적이지 못할 수도 있습니다.

 

문제 출처

SWEA 6808번: 규영이와 인영이의 카드게임 (D3)

 

키워드

순열, 백트래킹

 

풀이 접근법

  • 순열 문제로, Next Permutaion을 이용하면 시간을 더욱 줄일 수 있다.
  • 상대방이 내고 남은 카드 중에서 뽑아야 하기 때문에, 상대방이 뽑지 않은 나머지 카드 배열을 별도로 만들어주어야 한다. 카드는 종류 당 한 장씩 존재하므로 중복된 카드를 뽑을 수 없다.
  • 문제에 명시되지 않은 조건 중 하나로, 두 카드 값이 같아도 상대방에게 점수를 준다. 규영이가 점수를 얻을 수 있는 경우는 오직 인영이보다 큰 수를 냈을 때(kyuCards[i] > inCards[i])에만 해당한다.
  • 인영이가 내는 카드 순열을 생성하는 데에 비해, 구해야 하는 승/패 횟수는 규영이의 것이기 때문에 주의한다.
  • 이름이 비슷해서 문제 해석하는데 헷갈린다.

 

코드

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

public class Solution {

	private static final int SIZE = 9;
	private static final int MAX = 362_880;

	private static int[] kyuCards;
	private static int[] inCards;

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

		StringBuilder sb = new StringBuilder();
		for (int test_case = 1; test_case <= T; test_case++) {

			String[] input = br.readLine().split(" ");
			
			kyuCards = new int[SIZE];
			inCards = new int[SIZE];

			boolean[] used = new boolean[SIZE * 2 + 1];
			
			for (int i = 0; i < SIZE; i++) {
				kyuCards[i] = Integer.parseInt(input[i]);
				used[kyuCards[i]] = true;
			}
			
			int idx = 0;
			for(int i = 1; i <= SIZE * 2; i++) {
				if(!used[i]) {
					inCards[idx++] = i;
				}
			}
			
			Arrays.sort(inCards);
			
			//초기 상태 계산
			int count = 0;
			count += calculate();

			//마지막 순열이 될 때까지 반복
			while(nextPermutation(inCards)) {
				count += calculate();
			}

			sb.append("#").append(test_case).append(" ").append(count).append(" ")
				.append(MAX - count).append("\n");
		}

		System.out.print(sb);
	}

	private static int calculate() {
		int kScore = 0;
		int iScore = 0;
		
		for(int i = 0; i < SIZE; i++) {
			if(kyuCards[i] > inCards[i]) {
				kScore += (kyuCards[i] + inCards[i]);
			}
			else {
				iScore += (kyuCards[i] + inCards[i]);
			}
		}
		
		if(kScore > iScore) {
			return 1;
		}
		
		return 0;
	}

	public static boolean nextPermutation(int[] target) {

		int swapIdx = -1;
		for (int i = 1; i < target.length; i++) {
			if (target[i - 1] < target[i])
				swapIdx = i - 1;
		}

		if (swapIdx == -1)
			return false;

		int largerIdx = -1;
		for (int j = 1; j < target.length; j++) {
			if (target[swapIdx] < target[j])
				largerIdx = j;
		}

		swap(target, swapIdx, largerIdx);

		int j = target.length - 1;
		for (int i = swapIdx + 1; i < j; i++) {
			swap(target, i, j);
			j--;
		}
		
		inCards = target;

		return true;
	}

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

}

알고리즘 문제 풀이에는 독해력도 중요하게 작용된다는 걸 다시금 깨달은 문제였다. 구현 내용 자체는 크게 어렵지 않지만 혼동되는 정보들을 주의하자.

 

참고한 링크

https://comgong-man.tistory.com/23

 

git 링크

(git 링크 첨부)