삼성 B형 샘플 문제 : 숫자야구게임 (+ Linked List 삭제)

삼성 B형 전체 링크

 

swexpertacademy.com/main/sst/intro.do

 

SW Expert Academy에서 B형 샘플 문제 숫자야구게임을 풀어보자. 

 

B형에서 가끔 출제 되는, 시간보다 함수 호출 횟수를 줄여야 하는 쿼리형 문제이다.

따라서 register나 ++i 같은 최적화를 신경 쓸 필요가 없다.

---

먼저, 숫자 야구 게임에 대해서 간단히 알아보자.

 

정답이 1357이고, 9375라고 query를 던지면 result = { strike = 1, ball = 2 }가 된다.

위치도 같고, 숫자도 같은 3 → strike 1, 

위치는 다르지만, 숫자는 같은 5, 7 → ball = 2 가 된다.

 

guess 배열에 [1, 3, 5, 7]을 담아주면 tc 1개가 패스가 되고, 적은 query로 정답을 얻어야 한다.

---

정답을 찾는 원리.

 

정답 [1, 3, 5, 7]에 대해 [9, 3, 5, 7]로 query를 던지면 얻는 결과를 이용해서, 절대 정답이 될 수 없는 경우를 지운다.

 

거꾸로 생각을 해보자.

정답을 모르는 상태에서 [9, 3, 5, 7]로 strike = 1, ball = 2를 얻었다.

 

그러면 [0, 1, 2, 3]이 답일 수 있을까?

[0, 1, 2, 3]은 strike = 0, ball = 1인 결과를 얻기 때문에, 반드시 답이 될 수 없다.

 

마찬가지로, [0, 1, 2, 4] ... 등등은 답이 될 수 없다가.

 

[0, 3, 7, 5], ..., [5, 9, 2, 7] 정도는 되어야, 답이 될 가능성이 높다고 할 수 있다.

즉, 모든 답이 되는 후보군 [0, 1, 2, 3] ~ [9, 8, 7, 6] 중에, query를 던진 결과를 받아서,

절대 답이 될 수 없는 경우를 지우다가 strike = 4가 될 때 guess에 답을 담고 종료하면 된다.

---

구현해야하는 함수

 

1) 정답 후보군을 만드는 함수 : [0, 1, 2, 3] ~ [9, 8, 7, 6] 만들기 = DFS

2) 불필요한 후보군을 지우는 함수 = deleteNode

3) extern된 query함수 외에 답을 지울 때, 던질 query함수 = query2

 

시간이 매우 넉넉하므로, 원하는 방법대로 정답 후보군을 만들면 된다.

여기에서는 Linked List로 정답 후보군을 만들고, Linked List에서 Node를 삭제하는 함수를 연습해보자.

 

DFS와 visit배열을 이용해서, [0, 1, 2, 3] ~ [9, 8, 7, 6]을 만들자.

typedef struct st
{
	int g[4];
	struct st *next;
}NODE;

NODE HEAD;
NODE POOL[10000];
int pcnt;

int visit[10];
int list[4];

void DFS(int L)
{
	if (L > 3)
	{
		NODE *nd = &POOL[pcnt++]; 

		/* 4개의 숫자를 모두 구했으므로, linked list g[4]에 저장 */
		for (int k = 0; k < 4; k++) nd->g[k] = list[k]; 

		nd->next = HEAD.next;
		HEAD.next = nd;

		return;
	}

	for (int i = 0; i < 10; i++)
	{
		if (visit[i]) continue;

		list[L] = i; /* 임시 list에 숫자 0 ~ 9 중 하나 저장 */

		visit[i] = 1; /* 저장된 숫자는 다음에 못쓰게 체크 */
		DFS(L + 1);
		visit[i] = 0; /* DFS 종료 후에는 다시 사용할 수 있도록 초기화 */
	}
}

정답 후보군에서 중복된 숫자들은 필요가 없기 때문에, visit을 이용해서 걸러냈다.

참고로, Linked List를 만들면 [0, 1, 2, 3] ~ [9, 8, 7, 6]이 아닌 [9, 8, 7, 6] ~ [0, 1, 2, 3] 가 된다.

이유는 링크를 참고하자.

 

정답 후보군이 완성되었으므로, 삭제 함수를 만들자.

void deleteNode(int stk, int ball, int guess[])
{
	NODE *nd = &HEAD;

	while (nd->next)
	{
		Result result;
		int tmpstk, tmpball;

		result = query2(guess, nd->next->g); /* user가 만들어야 하는 query */
		tmpstk = result.strike;
		tmpball = result.ball;

		if (!(tmpstk == stk && tmpball == ball)) /* 삭제해야하는 후보군 */
			nd->next = nd->next->next; /* 노드의 삭제 */
		else /* 아니면 다음 node로 */
			nd = nd->next;
	}
}

strike와 ball의 결과를 넘겨준다.

같은 strike와 ball이 아니면 절대 답이 될 수 없기 때문에, 해당 경우는 삭제한다.

 

nd의 다음 node를 nd의 다음다음 node로 연결해주면 nd의 다음 node는 삭제가 된다.

(다음 deleteNode에서 참조할 수 없게 된다.)

 

strike와 ball이 같다면 단순히 nd를 다음 node로 바꾸면 되고, NULL이 될 때까지 반복하자. 

 

그리고 deleteNode는 strike == 4가 될 때 까지 반복한다.

 

마지막으로 query 함수를 만들자.

처음에 던진 답은 외부함수 query를 사용해서 strike와 ball을 얻는다. 

하지만 외부함수 query는 사용하면 할수록 점수에 감점이 된다.

 

따라서 정답 후보군을 지울 때는 자기가 만든 query를 사용하면 된다.

당연히 Main에서 제공되는 query와 다를 필요가 없다.

(정답에는 불필요한 코드를 지웠다.)

 

전체 코드는 아래를 참고하자.

 

Main

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

#define N              4
#define MAX_QUERYCOUNT 1000000

static int digits[N];
static int digits_c[10];

static int T;

extern void doUserImplementation(int guess[]);

static int querycount;

// the value of limit_query will be changed in evaluation
static int limit_query = 2520;

typedef struct {
	int strike;
	int ball;
} Result;

static bool isValid(int guess[]) {
	int guess_c[10];

	for (int count = 0; count < 10; ++count) guess_c[count] = 0;
	for (int idx = 0; idx < N; ++idx) {
		if (guess[idx] < 0 || guess[idx] >= 10 || guess_c[guess[idx]] > 0) return false;
		guess_c[guess[idx]]++;
	}
	return true;
}

// API : return a result for comparison with digits[] and guess[]
Result query(int guess[]) {
	Result result;

	if (querycount >= MAX_QUERYCOUNT) {
		result.strike = -1;
		result.ball = -1;
		return result;
	}

	querycount++;

	if (!isValid(guess)) {
		result.strike = -1;
		result.ball = -1;
		return result;
	}

	result.strike = 0;
	result.ball = 0;

	for (int idx = 0; idx < N; ++idx)
		if (guess[idx] == digits[idx])
			result.strike++;
		else if (digits_c[guess[idx]] > 0)
			result.ball++;

	return result;
}

static void initialize() {
	for (int count = 0; count < 10; ++count) digits_c[count] = 0;
	for (int idx = 0; idx < N; ++idx) {
		char c;
		do 
			scanf("%c", &c); 
		while (c < '0' || c > '9');
		digits[idx] = c - '0';
		digits_c[digits[idx]]++;
	}

	querycount = 0;
	scanf("%d", &limit_query);
}

static bool check(int guess[]) {
	for (int idx = 0; idx < N; ++idx)
		if (guess[idx] != digits[idx]) return false;
	return true;
}

int main() {
	int total_score = 0;
	int total_querycount = 0;;

	//freopen("sample_input.txt", "r", stdin);
	setbuf(stdout, NULL);

	scanf("%d", &T);
	for (int testcase = 1; testcase <= T; ++testcase) {
		initialize();

		int guess[N];
		doUserImplementation(guess);
		int score = 100;
		if (!check(guess)) querycount = MAX_QUERYCOUNT;
		if (querycount <= limit_query)
			total_score++;
		else
			score = 0;

		printf("#%d %d\n", testcase, score);
		total_querycount += querycount;
	}
	if (total_querycount > MAX_QUERYCOUNT) total_querycount = MAX_QUERYCOUNT;
	printf("total score = %d\ntotal query = %d\n", total_score * 100 / T, total_querycount);
	return 0;
}

 

User Code

#define N          4

typedef struct {
	int strike;
	int ball;
} Result;

// API
extern Result query(int guess[]);

void doUserImplementation(int guess[]) {
	// Implement a user's implementation function
	//
	// The array of guess[] is a return array that
	// is your guess for what digits[] would be.
}

---

정답

#define N          4

typedef struct {
	int strike;
	int ball;
} Result;

// API
extern Result query(int guess[]);

typedef struct st
{
	int g[4];
	struct st *next;
}NODE;

NODE HEAD;
NODE POOL[10000];
int pcnt;

int visit[10];
int list[4];

void DFS(int L)
{
	if (L > 3)
	{
		NODE *nd = &POOL[pcnt++];

		for (int k = 0; k < 4; k++) nd->g[k] = list[k];

		nd->next = HEAD.next;
		HEAD.next = nd;

		return;
	}

	for (int i = 0; i < 10; i++)
	{
		if (visit[i]) continue;

		list[L] = i;

		visit[i] = 1;
		DFS(L + 1);
		visit[i] = 0;
	}
}

Result query2(int guess[], int nd[]) 
{
	Result result;
	int check[10] = { 0 };

	result.strike = 0;
	result.ball = 0;

	for (int i = 0; i < 4; i++) check[guess[i]]++;

	for (int idx = 0; idx < N; ++idx)
		if (guess[idx] == nd[idx])
			result.strike++;
		else if (check[nd[idx]] > 0)
			result.ball++;

	return result;
}

void deleteNode(int stk, int ball, int guess[])
{
	NODE *nd = &HEAD;

	while (nd->next)
	{
		Result result;
		int tmpstk, tmpball;

		result = query2(guess, nd->next->g);
		tmpstk = result.strike;
		tmpball = result.ball;

		if (!(tmpstk == stk && tmpball == ball))
			nd->next = nd->next->next; 
		else
			nd = nd->next;
	}
}

void doUserImplementation(int guess[])
{
	Result result;

	pcnt = 0;
	HEAD.next = 0;
	DFS(0);

	while (1)
	{
		int stk, ball;
		
        /* 정답 후보군 1개를 guess에 복사 */
		for (int i = 0; i < 4; i++) guess[i] = HEAD.next->g[i];

		/* 후보군 1개는 다시 볼 필요 없으므로 head 이동 */
		HEAD.next = HEAD.next->next;

		result = query(guess);
		stk = result.strike;
		ball = result.ball;

		if (stk == 4) break; /* 정답을 찾은 경우 종료 */

		deleteNode(stk, ball, guess); /* 불필요한 후보군 삭제 */
	}
}

---

정답 후보군을 count하면서 count가 1이 될 경우 break를 걸면, query 수를 조금 더 줄일 수 있다.