[백준 2164번/C언어] 카드2 풀이

백준 2164번 문제를 풀어보았습니다.

 

백준 2164번: https://www.acmicpc.net/problem/2164

2164번: 카드2

 

 

문제 내용은 다음과 같습니다.

 

 

 

 

 해당 문제는 접근법이나 알고리즘을 굳이 복잡하게 생각하지 않아도 풀 수 있는 문제입니다. 처음에 풀 때 어떻게 더 간단히 할 수 있을까를 너무 복잡하게 생각하다가 적절한 방법을 찾지 못했는데, 오히려 문제를 직관적으로 더 간단하게 접근하니까 해결할 수 있었습니다. 

 

 

 제가 문제를 해결한 방법을 간략히 먼저 말씀드리면, 1부터 N까지의 카드를 순회하면서 현재 카드를 삭제하고 그다음 카드는 아무 조치도 하지 않고 넘겨버린 후 다음 카드로 가서 똑같은 과정을 반복하는 식입니다. N번째 카드에 도달하면 다시 첫 번째 카드부터 현재 남은 카드까지를 순회하면서 같은 과정을 반복하게 됩니다. 아무 조치 하지 않고 넘겨버린 카드는 뒤에 있는 모든 카드를 순회한 후 다시 처음으로 돌아와 순회하게 되므로, 아무 조치도 하지 않았지만 문제에서 요구한 대로 맨 마지막으로 넘기는 것과 같은 효과를 볼 수 있습니다. 

 

 

 

 우선 1부터 N까지 카드의 존재 여부를 확인하기 위한 cards 배열을 만들어줍니다. 저는 편의상 그냥 전역 변수로 N의 최대값 + 1의 크기의 배열을 만들어주었습니다. + 1을 해준 이유는 key값을 카드 번호 자체로 사용하기 위함입니다.

 

 다음 입력받은 N값을 n변수에 저장해줍니다. 이는 카드를 삭제해 나가면서 현재 카드가 몇 개 남았는지를 확인하기 위함입니다. 남은 카드가 하나가 될 때까지 과정을 반복해야 하기 때문입니다. N값을 남겨주는 이유는, 배열의 끝을 확인하기 위함입니다. 

 

 이후에는 만약 현재 해당 숫자를 가진 카드가 존재한다면 (cards[i] == 0 이라면), 해당 카드는 삭제해 주고, 그다음 존재하는 카드를 찾아, 그 카드는 넘겨줍니다. 만약 다음 카드를 찾는 과정에서, i가 N값을 초과한다면 다시 처음으로 돌아가줍니다. 그리고 카드를 하나 삭제했으므로 n값을 감소시켜 주고, 그다음 카드부터 다시 탐색을 시작하기 위해 i를 증가시켜 주는 과정을 카드가 하나 남을 때까지 반복합니다. 

 

 이 과정을 마치고 나면 카드가 하나 남습니다. 그 카드를 찾아주기 위해 카드 배열을 다시 순회하면서 아직 삭제되지 않은 카드, 즉 배열 값이 0인 카드를 찾아 출력해주면 프로그램이 종료됩니다. 

#include <stdio.h>

int cards[500001];

int main() {
    int N;
    scanf("%d", &N);
 
    int i = 1;
    int n = N;
    while (n > 1) {
        if (cards[i] == 0) {
            cards[i] = 1;
            while (cards[i]) {
                if (++i > N) i -= N; 
            }
            n--;
        }
        
        if (++i > N) i -= N;
    }
    
    for (int i = 1; i <= N; i++) {
        if (cards[i] == 0) {
            printf("%d", i);
            return 0;
        }
    }
    return 1;
}