CosPro1급 모의고사 - Part.2 한 줄 바꾸기 - 카드셔플 (C언어)

Cos Pro 1급 모의고사 - 종이접기에 대한 C언어를 이용한 저의 풀이입니다.

 

목차

• 문제 설명
• 매개변수 설명
• return 값 설명
• 예제
• ***풀이 전략***
• 문제와 답

 

문제 설명

1부터 n까지 숫자가 적힌 카드 뭉치를 다음 규칙에 따라 카드 뭉치를 섞었을 때, 아래에서부터 k번째에 있는 카드에 적힌 숫자를 알아내려합니다. 카드 뭉치 가장 아래에는 1이 쓰여있으며, 위로 갈수록 숫자가 커집니다. 카드 뭉치를 섞는 규칙은 다음과 같습니다.

1. 카드 뭉치를 정확히 반으로 나눕니다.
2. 두 개로 나뉜 카드 뭉치를 교차로 섞어서 카드 뭉치 하나를 만듭니다. 이때, 항상 1이 적힌 카드가 있는 뭉치를 아래로 놓고 섞습니다.
3. 위 과정을 반복합니다.

예를 들어, 1부터 6까지 숫자가 적힌 카드 뭉치를 3번 섞는다면 과정별로 아래에서부터 적힌 숫자는 다음과 같습니다.

횟수카드 뭉치

1	[1, 4, 2, 5, 3, 6]
2	[1, 5, 4, 3, 2, 6]
3	[1, 3, 5, 2, 4, 6]

이때, 아래에서 3번째에 있는 카드에 적힌 숫자는 5입니다.

처음에 가장 위에 있는 카드에 적힌 숫자 n, 섞는 횟수 mix, 알고 싶은 카드의 위치 k가 매개변수로 주어질 때, 아래에서부터 k번째에 있는 카드에 적힌 숫자를 return 하도록 solution 함수를 작성했습니다. 그러나, 코드 일부분이 잘못되어있기 때문에, 몇몇 입력에 대해서는 올바르게 동작하지 않습니다. 주어진 코드에서 한 줄만 변경해서 모든 입력에 대해 올바르게 동작하도록 수정하세요.

 

매개변수 설명

처음에 가장 위에 있는 카드에 적힌 숫자 n, 섞는 횟수 mix, 알고 싶은 카드의 위치 k가 solution 함수의 매개변수로 주어집니다.

• n은 10 이상 50 이하인 짝수입니다.
• 카드는 0회 이상 10회 이하로 섞습니다.
• k는 1 이상 n 이하인 자연수입니다.

 

return 값 설명

아래에서 k번째에 있는 카드에 적힌 숫자를 return 해주세요.

예제

n	mix	k	return
6	3	3	5

 

문제와 답

 

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
 
int solution(int n, int mix, int k) {
    int answer = 0;
 
    int* card = (int*) malloc(sizeof(int) * n);
    for(int i = 0; i < n; i++)
        card[i] = i+1;
 
    while(mix--) {
        int* card_a = (int*) malloc(sizeof(int) * n/2);
        int* card_b = (int*) malloc(sizeof(int) * n/2);
 
        for(int i = 0; i < n; i++) {
            if(i < n/2)
                card_a[i] = card[i];
            else
                // Original Wrong Code
                // card_b[i-(n/2)] = card[i]; 
                // Modified Code
                card_b[i-(n/2)] = card[i];
        }
 
        for(int i = 0; i < n; i++) {
            if(i % 2 == 0)
                card[i] = card_a[i/2];
            else
                card[i] = card_b[i/2];
        }
    }
 
    answer = card[k-1];
 
    return answer;
}
 
// 아래는 테스트케이스 출력을 해보기 위한 main 함수입니다. 아래에는 잘못된 부분이 없으니 위의 코드만 수정하세요.
int main() {
    int n = 6;
    int mix = 3;
    int k = 3;
    int ret = solution(n, mix, k);
 
    // [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    printf("solution 함수의 반환 값은 %d 입니다.\n", ret);
}

 

풀이 전략

규칙 1, 규칙 2가 각각의 for 문으로 구분

문제 설명과 코드 구현을 비교해볼 필요가 있다.

규칙 2의 카드 인덱스

정수의 나누기 규칙이 헷갈릴 수 있겠다 싶지만

정수의 나누기는 소수점을 버리기 때문에 (올림/반올림/내림) 중에서 내림 규칙을 따른다.

*** 규칙 1의 카드 옮기기 ***

카드 옮기기의 인덱스가 잘못되어있다.

card_b 뭉치의 인덱스는 1부터 시작하기 때문이다.

이 문제는 설명을 읽고 코드 구현과 연결지어볼 수 있는지 확인하는 문제같다.