[Algorithm] 백준 4992 - Hanafuda Shuffle (Node / C#)

문제

https://www.acmicpc.net/problem/4992

 

풀이

1. Node.js(fs)

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

let index = 0;

while (true) {
    const [n, r] = input[index++].split(' ').map(Number);
    if (n === 0 && r === 0) break;

    let deck = Array.from({length: n}, (_, i) => n - i);

    for (let i = 0; i < r; i++) {
        const [p, c] = input[index++].split(' ').map(Number);
        const cut = deck.splice(p - 1, c);
        deck = [...cut, ...deck];
    }

    console.log(deck[0]);
}

 

2. Node.js(readLine)

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let n, r;
let deck;
let operationCount = 0;

rl.on('line', (line) => {
    const [a, b] = line.split(' ').map(Number);

    if (a === 0 && b === 0) {
        rl.close();
        return;
    }

    if (!n) {
        n = a;
        r = b;
        deck = Array.from({length: n}, (_, i) => n - i);
        operationCount = 0;
    } else {
        const [p, c] = [a, b];
        const cut = deck.splice(p - 1, c);
        deck = [...cut, ...deck];
        operationCount++;

        if (operationCount === r) {
            console.log(deck[0]);
            n = r = null;
        }
    }
});

3. C#

using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        while (true)
        {
            string[] input = Console.ReadLine().Split();
            int n = int.Parse(input[0]);
            int r = int.Parse(input[1]);

            if (n == 0 && r == 0) break;

            List<int> deck = Enumerable.Range(1, n).Reverse().ToList();

            for (int i = 0; i < r; i++)
            {
                input = Console.ReadLine().Split();
                int p = int.Parse(input[0]);
                int c = int.Parse(input[1]);

                List<int> cut = deck.GetRange(p - 1, c);
                deck.RemoveRange(p - 1, c);
                deck.InsertRange(0, cut);
            }

            Console.WriteLine(deck[0]);
        }
    }
}

 

 

설명

1. 입력 처리:
   • 각 테스트 케이스마다 카드의 수 n과 셔플 횟수 r을 읽습니다.
   • n과 r이 모두 0이면 프로그램을 종료합니다.
2. 데이터 구조:
   • 덱을 나타내기 위해 배열 또는 리스트를 사용합니다.
   • 초기 덱은 n부터 1까지 역순으로 채워집니다 (맨 위가 n).
3. 알고리즘:
   • 각 셔플 작업마다:
     1. p번째 카드부터 c개의 카드를 잘라냅니다.
     2. 잘라낸 카드들을 덱의 맨 위로 옮깁니다.
   • 이 과정을 r번 반복합니다.
4. 결과 출력:
   • 모든 셔플 작업이 끝난 후, 덱의 맨 위 카드 번호(deck[0])를 출력합니다.
5. 시간 복잡도:
   • 전체 알고리즘의 시간 복잡도는 O(n * r)입니다.
   • 각 셔플 작업이 최악의 경우 O(n) 시간이 걸릴 수 있고, 이를 r번 반복하기 때문입니다.
6. 공간 복잡도:
   • 공간 복잡도는 O(n)입니다.
   • n개의 카드를 저장하는 덱이 필요하기 때문입니다.