백준 2164번 카드2 C#으로 문제 풀어보기

안녕하세요 박민성입니다.

 

오늘은 백준 2164번 카드2 를 풀어 보겠습니다.

문제를 보면

입력은 1보다 크거나 같고 500,000보다 작거나 같은 카드의 개수 N이 주어집니다.

 

출력은 마지막으로 남아 있는 카드에 적혀 있는 숫자를 출력합니다.

 

문제는 1부터 N까지의 카드들이 1부터 N까지 숫자가 적혀 있습니다. 6이 주어지면 1 2 3 4 5 6 카드가 순서대로 있습니다.

첫 번째로 맨 앞 카드는 버리고요 ( 2 3 4 5 6 )

다음은 맨 뒤로 보냅니다 ( 3 4 5 6 2 )

그리고 또다시 카드를 맨 앞 카드를 버립니다 ( 4 5 6 2 )

또 맨 앞 카드를 맨 뒤로 보냅니다 ( 5 6 2 4 )

이걸 1장이 남을 때까지 반복하는 문제입니다.

 

저는 이 문제를 보고 처음에는 다른 풀이 방식을 생각했지만(뒤에서 다룰 예정)

굳이 그럴 필요가 없다는 걸 깨닫고 자료구조 중 Queue를 사용하기로 합니다.

일단은 카드의 수를 변수 a에 입력을 받아주고 

Queue int형으로 객체 생성을 해줍니다.

그리고 뒤에서 카드를 버리고 뒤로 넘기는 걸 하기 위한 count 변수도 선언해 줍니다.

그리고 a까지 수들을 queue에 넣어줍니다.

 

그리고 while문과 if문을 사용하여 queue에 들어 있는 것이 1개가 남을 때까지(카드 한 장이 남을 때까지) 반복해 줍니다.

그리고 count가 짝수면 카드를 제거해 주고 홀수면 카드를 빼준걸 다시 넣어줍니다.

그리고 한 번씩 반복하기 위해 count를 ++ 해주고

마지막으로 while문에서 빠져나온 카드 한 장을 출력해 주면 끝입니다.

이것이 전체 코드입니다. 

 

이렇게 백준에 제출하였더니

정답이었습니다.

 

제가 이 문제를 보고 처음에는 "어? 입력이 크고 시간제한이 2초네? 그럼 일반적인 빼고 뒤로 넘기고는 안 되겠네?"

라고 생각하여

일단은

메모장으로 1은 1이 나오고 2는 2가 나오고 8은 8이 나오고 16은 16이 나오고 

이런 걸 보면서 패턴을 찾았습니다.

그 패턴은 1은 예외처리하고

정답이 2의 배수로 늘어납니다. 5는 2 6은 4 7은 6 8은 8

하지만 입력과 정답이 같아지면(예를 들어 2는 2 8은 8 16은 16)

다시 2에서 시작하여 4 6 8 10 12 14로 2의 배수씩 늘어납니다.

하지만

알고리즘 분류를 보고 "이렇게 푸는 문제가 아니구나" 하고 포기했습니다.

나중에 시간제한이 더 빡빡하거나 메모리 제한이 더 빡빡한 문제가 있으면 이 방법을 시도해 보겠습니다.