99클럽 코테 스터디 16일차 TIL

오늘의 학습 키워드

스택/큐

과제

문제

N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다.

이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.

예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리면 234가 남는다. 여기서 2를 제일 아래로 옮기면 342가 된다. 3을 버리면 42가 되고, 4를 밑으로 옮기면 24가 된다. 마지막으로 2를 버리고 나면, 버린 카드들은 순서대로 1 3 2가 되고, 남는 카드는 4가 된다.

N이 주어졌을 때, 버린 카드들을 순서대로 출력하고, 마지막에 남게 되는 카드를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 버리는 카드들을 순서대로 출력한다. 제일 마지막에는 남게 되는 카드의 번호를 출력한다.

예제 입력 1

7

예제 출력 1

1 3 5 7 4 2 6

풀이 과정

1. 카드 배열을 만든 뒤 앞카드를 버리고 추가한다.
2. 두번쨰 카드를 뒤에 추가하는 동작을 반복한다.

제출 코드 (python)

n = int(input())
a = []

card = [i for i in range(1, n + 1)]

while len(card) != 1:
    a.append(card.pop(0)) 
    card.append(card.pop(0)) 

for j in a:
    print(j, end=' ')

print(card[0])

다른 언어로 문제 풀기

GO 언어

package main

import "fmt"

func main() {
    var n int
    fmt.Scan(&n)

    // 큐 구현을 위한 슬라이스
    card := make([]int, n)
    for i := 0; i < n; i++ {
        card[i] = i + 1
    }

    result := make([]int, 0, n-1)
    front := 0  // 큐의 시작 인덱스
    size := n   // 현재 카드 수

    for size > 1 {
        // 첫 번째 카드는 결과에 추가
        result = append(result, card[front])
        front = (front + 1) % n
        size--

        // 두 번째 카드는 뒤로 이동
        if size > 0 {
            card[front+size] = card[front]
            front = (front + 1) % n
        }
    }

    // 결과 출력
    for _, v := range result {
        fmt.Printf("%d ", v)
    }
    fmt.Println(card[front])
}

C++

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    queue<int> card;
    vector<int> result;

    // 카드 초기화
    for(int i = 1; i <= n; i++) {
        card.push(i);
    }

    // 카드 게임 진행
    while(card.size() != 1) {
        result.push_back(card.front());
        card.pop();
        card.push(card.front());
        card.pop();
    }

    // 결과 출력
    for(int x : result) {
        cout << x << " ";
    }
    cout << card.front() << "\n";

    return 0;
}

오늘의 회고

• queue를 이용한 간단한 기본기 다지는 느낌이었다!

출처 :https://www.acmicpc.net/problem/2161