[SWEA/Java] 6808. 규영이와 인영이의 카드게임

[SWEA/Java] 6808. 규영이와 인영이의 카드게임

SW Expert Academy

---

문제 해석

규영이와 인영이는 각각 9장의 카드를 가지고 게임을 한다. 이 게임에서는 총 18장의 카드가 사용되며, 각 카드에는 1부터 18까지의 숫자가 적혀 있다. 규영이의 카드는 입력으로 주어지며, 인영이는 남은 카드를 가진다. 이 게임에서 각 턴에 두 사람은 자신의 카드 중 하나를 내고, 더 높은 숫자의 카드를 낸 사람이 점수를 얻는다. 이 점수는 두 카드의 숫자를 합한 값이다. 모든 카드가 사용될 때까지 게임을 계속하며, 게임이 끝난 후 더 많은 점수를 획득한 사람이 승리한다. 이 문제에서는 규영이와 인영이가 획득할 수 있는 모든 승리 조합의 수를 구해야 한다.

풀이 과정

제출된 Java 코드는 주어진 규영이의 카드를 바탕으로 인영이의 카드를 구성하고, 모든 가능한 순열을 생성하여 각 순열에 대해 점수를 계산하는 방식으로 문제를 해결한다. 이를 위해 백트래킹과 비트마스킹을 사용해 효율적인 순열 생성을 진행한다.

 

• 데이터 입력: 입력 데이터로부터 테스트 케이스 수와 규영이의 카드를 받는다.
• 카드 배열 구성: 규영이의 카드를 제외한 나머지 카드를 인영이의 카드 배열로 구성한다.
• 순열 생성 및 점수 계산 (permutation 메소드): 카드 순열을 생성하면서 각 카드의 대결에서 점수를 계산한다. 모든 카드가 사용된 후 최종 점수를 비교하여 승리 횟수를 갱신한다.

코드

package edu.ssafy.im.SWEA.D3.No6808;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Solution {
	private final static int SIZE = 9; // 카드 수
	private int[] arr; // 규영이의 카드 배열
	private int[] card; // 인영이의 카드 배열
	private int[] sel; // 현재 순열의 카드
	private int sw; // 규영이의 승리 횟수
	private int aw; // 인영이의 승리 횟수

	public static void main(String[] args) throws NumberFormatException, IOException {
		new Solution().io();
	}

	private void io() throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		int testCase = Integer.parseInt(br.readLine());

		for (int t = 1; t <= testCase; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			arr = new int[SIZE]; // 규영이의 카드 초기화
			for (int i = 0; i < SIZE; i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			card = new int[SIZE]; // 인영이의 카드 배열
			int idx = 0;
			for (int i = 1; i <= SIZE * 2; i++) {
				boolean flag = true;
				for (int j = 0; j < SIZE; j++) {
					if (arr[j] == i) {
						flag = false;
						break;
					}
				}
				if(flag) {
					card[idx] = i;
					idx++;
				}
			}
			sw = 0; aw = 0;
			sol();
			sb.append("#").append(t).append(" ").append(aw).append(" ").append(sw).append("\n");
		}
		bw.write(sb.toString());
		bw.flush();
		bw.close();
	}

	private void sol() {
		sel = new int[SIZE]; // 순열을 위한 선택 배열
		permutation(0, 0);
	}

	private void permutation(int k, int v) {
		if (k == SIZE) {
			int ss = 0, as = 0; // 규영이와 인영이의 점수
			for (int i = 0; i < SIZE; i++) {
				if(sel[i] > arr[i]) {
					ss += sel[i] + arr[i]; // 규영이 승리
				} else {
					as += sel[i] + arr[i]; // 인영이 승리
				}
			}
			if (ss > as) {
				sw += 1; // 규영이 승리 횟수 추가
			} else if (as > ss) {
				aw += 1; // 인영이 승리 횟수 추가
			}
			return;
		}

		for (int i = 0; i < SIZE; i++) {
			if ((v & (1 << i)) == 0) {
				sel[k] = card[i]; // 카드 선택
				permutation(k + 1, v | 1 << i); // 다음 카드 선택
			}
		}
	}
}

시간 복잡도 분석

이 알고리즘의 시간 복잡도는 순열을 생성하는 데 필요한 비용으로, 최악의 경우 9! (362880) 회의 순열을 생성해야 한다. 각 순열에 대한 처리는 O(1)이므로, 전체 시간 복잡도는 O(9!)이다.

느낀점

이 문제를 통해 순열을 사용하여 다양한 경우의 수를 고려하고, 조건에 따라 결과를 계산하는 방식을 연습할 수 있었다. 이러한 접근 방식은 조합적 문제 해결에 널리 사용되며, 다양한 분야에 적용될 수 있다.