문제 풀이 날짜: 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 링크 첨부)
'Study > Problem Solving' 카테고리의 다른 글
| [SWEA / Java] 9843번: 촛불 이벤트 (D5) (0) | 2023.08.21 |
|---|---|
| [백준 / Java] 15686번: 치킨 배달 (골드5) (0) | 2023.08.21 |
| [백준 / Java] 1992번: 쿼드트리 (실버1) (0) | 2023.08.16 |
| [백준 / Java] 3109번: 빵집 (골드2) (0) | 2023.08.16 |
| [백준 / Java] 6987번: 월드컵 (골드4) (0) | 2023.08.16 |