SWEA 5658 : 보물상자 비밀번호 (모의 SW 역량테스트)

 

SW 역량테스트 합격하기 A형 강의 오픈!! (인프런 바로가기)

 

삼성 A형 전체 링크

 

모의 SW 역량테스트 문제집

 

보물상자 비밀번호 링크

 

이후 설명 및 입/출력은 링크 참고

 

문제에서 제시한 예시는 아래와 같다.

 

이 배열을 직접 4칸 나눠서 회전할 필요는 없다. 구현이 까다롭고 귀찮기 때문이다.

 

먼저 크기 N / 4 = 3만큼 배열을 뒤에 덧붙인다.

 

그리고 i = 0부터 N - 1까지 N / 4 칸씩 문자열을 10진수로 저장하면 생성 가능한 수를 모두 구하게 된다.

---

makeDecimal은 넘겨받은 배열을 기준으로 size만큼 16진수로 변경한다.

배열은 문자열이기 때문에 'A' 이상인 경우는 'A'를 빼주고 10을 더하고, 그 외에는 문자열 '0'만큼 빼면 된다.

그리고 mul 변수에 16을 곱해가면서 16진수로 변경한다.

int makeDecimal(char* ptr, int size)
{
	int sum, mul;

	sum = 0; mul = 1;
	for (int i = size - 1; i >= 0; i--)
	{
		if (ptr[i] >= 'A') sum += (ptr[i] - 'A' + 10) * mul;
		else sum += (ptr[i] - '0') * mul;
		
		mul *= 16;
	}

	return sum;
}

 

위의 그림대로 옆으로 1칸씩 움직이면서 16진수 문자열을 10진수로 만들어 decimal 배열에 담자.

여기까지의 구현을 main에서 하면 다음과 같다.

int main(void)
{
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++)
	{
		dcnt = 0;

		char number[MAX];
		
		scanf("%d %d %s", &N, &K, number);

		for (int i = 0; i < N / 4; i++) number[N + i] = number[i];
		number[N + N / 4] = 0;
		
		for (int i = 0; i < N; i++) decimal[dcnt++] = makeDecimal(number + i, N / 4);

		...
        
    }
 
	return 0;
}

 

K번째로 큰 수를 구하기 위해 정렬한다.

A형에서는 정렬 알고리즘을 요구하는 경우가 거의 없으므로, O(N²) 정렬 알고리즘을 사용해도 된다.

for (int i = 0; i < dcnt - 1; i++)
{
	for (int k = i + 1; k < dcnt; k++)
	{
		if (decimal[i] < decimal[k])
		{
			int tmp = decimal[i];
			decimal[i] = decimal[k];
			decimal[k] = tmp;
		}
	}
}

 

정렬을 했으면, 중복을 제거해서 uniqueList에 담으면 된다.

그러면 K번째로 큰 수는 uniqueList[K - 1]에 저장된다.

int uniqueList[MAX] = { 0 };
int ucnt = 0;

uniqueList[ucnt++] = decimal[0];
for (int i = 1; i < dcnt; i++)
{
	if (decimal[i] == uniqueList[ucnt - 1]) continue;

	uniqueList[ucnt++] = decimal[i];
}

printf("#%d %d\n", tc, uniqueList[K - 1]);

 

최종 코드는 아래를 참고하자.

#include <stdio.h>

#define MAX (28 + 10)

int T, N, K;
int decimal[MAX];
int dcnt;

int makeDecimal(char* ptr, int size)
{
	int sum, mul;

	sum = 0; mul = 1;
	for (int i = size - 1; i >= 0; i--)
	{
		if (ptr[i] >= 'A') sum += (ptr[i] - 'A' + 10) * mul;
		else sum += (ptr[i] - '0') * mul;
		
		mul *= 16;
	}

	return sum;
}

int main(void)
{
	scanf("%d", &T);
	for (int tc = 1; tc <= T; tc++)
	{
		dcnt = 0;

		char number[MAX];
		
		scanf("%d %d %s", &N, &K, number);

		for (int i = 0; i < N / 4; i++) number[N + i] = number[i];
		number[N + N / 4] = 0;
		
		for (int i = 0; i < N; i++) decimal[dcnt++] = makeDecimal(number + i, N / 4);

		for (int i = 0; i < dcnt - 1; i++)
		{
			for (int k = i + 1; k < dcnt; k++)
			{
				if (decimal[i] < decimal[k])
				{
					int tmp = decimal[i];
					decimal[i] = decimal[k];
					decimal[k] = tmp;
				}
			}
		}

		int uniqueList[MAX] = { 0 };
		int ucnt = 0;

		uniqueList[ucnt++] = decimal[0];
		for (int i = 1; i < dcnt; i++)
		{
			if (decimal[i] == uniqueList[ucnt - 1]) continue;

			uniqueList[ucnt++] = decimal[i];
		}

		printf("#%d %d\n", tc, uniqueList[K - 1]);
	}

	return 0;
}