1. 문제 설명
1 ~ 18의 정수가 적힌 18장의 카드
2명이 9장씩 나누어 가지고, 9라운드 카드게임 진행
- 한 라운드 : 한 장씩 카드를 낸 후
높은 수가 나온 사람: 두 카드에 적힌 수의 합 만큼 점수 획득
낮은 수가 나온 사람: 점수 X
9라운드를 끝내고 총점을 따졌을 때, 총점이 더 높은 사람이 승자, 같으면 무승부
규영이가 내는 카드의 순서를 고정시키면, 인영이가 낼 수 있는 경우의 수: 9!
이것에 따라 규영이의 승패가 정해짐
Q: 규영이가 이기는 경우 & 지는 경우는 각각 몇 가지인가?
// [input]
4 // t
1 3 5 7 9 11 13 15 17 // 규영이가 내는 9장의 카드의 순서
18 16 14 12 10 8 6 4 2
13 17 9 5 18 7 11 1 15
1 6 7 9 12 13 15 17 18 2. 스크래치
[입력]
1. 규영이가 가지고 있는 9장의 카드 (문제에서 주어짐)
규영이의 카드 순서 입력 받기
[로직]
2. 인영이가 가지고 있는 9장의 카드 찾기
1 ~ 18 중 규영이가 가지고 있는 카드들을 제외
3. 인영이가 낼 수 있는 카드 순서 구하기
9장의 카드 순서에 따라 한 라운드의 승패가 달라짐 → 순열
4. 규영이가 이기는 횟수 카운트
인영이의 각 카드 순서에 따라 규영이가 게임을 이기는 횟수를 카운트
[출력]
5. 규영이가 이기는 경우 & 지는 경우
= 규영이가 이기는 횟수 & (9! - 규영이가 이기는 횟수)
3. 풀이
주요 알고리즘: 백트래킹 (순열)
규영이의 9장의 카드 순서가 정해져 있는 상태에서
인영이가 낼 수 있는 9장의 카드 순서에 따라 한 라운드마다의 결과가 달라짐
⇒ 인영이가 가질 수 있는 9장의 카드의 모든 순서를 고려해야 함
문제 쪼개기
1. 인영이가 가지고 있는 9장의 카드 구하기: List 자료형 사용
cards변수 : List 자료형으로 1 ~ 18까지의 정수를 담기kyuCards변수: int[] 자료형으로 규영이의 9장의 카드 값을 저장 (문제에서 입력받기)inCards변수: int[] 자료형으로 인영이의 9장의 카드 값을 저장할 배열- cards에서 kyuCards의 0~8인덱스에 해당하는 카드를 삭제 & 나머지 원소 → inCards에 추가
2. 인영이가 낼 수 있는 카드 순서 구하기: 백트래킹 (순열)
- parameter:
(int depth, boolean[] visited)
depth: 현재 몇 번째 카드의 순서를 정하고 있는지
visited: 9장의 카드 사용 여부 - 순열 구하기 (수도 코드)
for ( i = 0 ~ 9) visited[i] = true recursion visited[i] = false - base-case :
depth == 9
9장의 순서가 완성되었으면 해당 순서에서 규영이가 이기는 경우의 수를 구하기
inCardCase변수: int[]자료형으로 현재 완성된 9장 카드의 순서
inCardCase→ 규영이의 9장의 카드와 비교하여 점수 계산하는 함수에 전달
해당 함수에서 규영이가 이기면kyuWincount ++ - 규영이가 지는 경우의 수?
static final int TotalCount = 362880;← 9! 값 저장
TotalCount - kyuWincount
3. 코드
public class swea6808_카드게임 {
static int[] kyuCards= new int[9];
static int[] inCards= new int[9];
static int[] inCardCase = new int[9];
static final int TotalCount = 362880;
static int kyuWincount;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for(int t=1; t<=T; t++) {
// [input]
String[] temp = br.readLine().split(" ");
// 1 ~ 18까지의 카드
List<Integer> cards = new ArrayList<>() ;
for(int i=1; i<=18; i++) {
cards.add(i);
}
// 규영이 카드
for(int i=0; i<9; i++) {
kyuCards[i] = Integer.parseInt(temp[i]);
if(cards.contains(kyuCards[i])) {
cards.remove(Integer.valueOf(kyuCards[i]));
}
}
// 인영이 카드
for(int i=0; i<9; i++) {
inCards[i] = cards.get(i);
}
//System.out.println(Arrays.toString(kyuCards));
//System.out.println(Arrays.toString(inCards));
// [logic]
// 인영이 카드 순서 구하기
boolean[] visited = new boolean[9];
kyuWincount = 0; // 규영이가 몇 번 이기는지 카운트
inCardsOrder(0, visited); // 인영이 카드의 순열을 구해 차례대로 -> countKyuWin
// [output]
System.out.println("#"+t+" "+kyuWincount+ " " + (TotalCount-kyuWincount));
}// for: T
}// main
/**
* 인영이의 카드 순열 생성하는 함수
* @param depth: 현재 몇 번째 카드인가
* @param visited: 방문 체크
*/
private static void inCardsOrder(int depth,boolean[] visited) {
// base-case
if(depth ==9) {
countKyuWin(inCardCase);
return;
}
for(int i=0; i<9;i++) {
if(!visited[i]) {
// do
visited[i] = true;
inCardCase[depth] = inCards[i];
inCardsOrder(depth+1, visited);
// undo
visited[i] = false;
}
}
}//
/**
* 인영이의 카드 순서를 입력받아 규영이가 게임을 이기는 횟수를 카운트하는 함수
* @param inCardCase: 인영이의 카드 순서
*/
private static void countKyuWin(int[] inCardCase) {
int kyuScore = 0;
int inScore = 0;
for(int i=0; i<9; i++) {
if(kyuCards[i] > inCardCase[i]) {
kyuScore += kyuCards[i] + inCardCase[i];
}
else if (kyuCards[i] < inCardCase[i]) {
inScore += kyuCards[i] + inCardCase[i];
}
// 동점 -> 점수 x
}
if(kyuScore > inScore) kyuWincount ++;
}//
}
4. De-Fault
Fault
1. static 변수 사용 시 초기화
- 테스트 케이스마다 초기화하기
static으로 선언한 변수의 값은 프로그램이 끝날 때까지 유지됨 - 가변적 입력 N
테스트케이스마다 N과 같은 입력값에 따라 크기가 변하는 배열 / 리스트는 반드시 새로 생성 (new) - 올바른 위치에서 초기화하기
⇒ static 변수 선언 시, 초기화 코드 먼저 작성하기
시간 복잡도
- 순열 생성: O(9!)
- 각 순열에 대해 승패 비교: O(9)
- 전체 시간 복잡도: O(9! * 9)
개선 가능한 부분
1. 인영이의 카드 찾기
[현재 코드]
List<Integer> cards = new ArrayList<>();
for(int i=1; i<=18; i++) {
cards.add(i);
}
for(int i=0; i...){
//...
if(cards.contains(kyuCards[i])) {
cards.remove(Integer.valueOf(kyuCards[i]));
}
}- ArrayList에 1~18의 수를 모두 넣고, 규영이의 카드를 remove()하는 방식
- 리스트 순회 시, 시간 복잡도면에서 비효율 발생 가능 O (n)
→ 1 ~ 18까지의 숫자를 체크할 수 있는 boolean 배열 만들기
[수정 후 코드]
boolean[] isKyuCard = new boolean[19]; // 1 ~ 18 인덱스 사용
// 규영이 카드 체크
for(int i=0; i<9; i++) {
kyuCards[i] = Integer.parseInt(temp[i]);
isKyuCard[kyuCards[i]] = true;
}
// 인영이 카드 구성
int inIdx = 0;
for(int i=1; i<=18; i++) {
if(!isKyuCard[i]) { // 규영이의 카드가 아니면
inCards[inIdx++] = i;
}
}이 코드에서 잘못된 부분이나 개선할 점이 있다면 언제든지 댓글로 알려주세요.
알고리즘을 작성하면서 더 좋은 코드를 만들 수 있도록 도와주시면 정말 감사하겠습니다! 🙂
