[지코바] 다른 사람 코드 분석하기 - 카드2

1. 문제

2164번: 카드2

  정렬된 카드 더미가 있고, 더미의 각 카드를 다음 규칙에 맞춰 버렸을 때 마지막 카드가 무엇인지 맞추는 문제다.

  1. 가장 위에 있는 카드를 버린다.
  2. 가장 위에 있는 카드를 카드 더미 맨 마지막으로 옮긴다.
  3. 카드 한 장이 남을 때까지 1 ~ 2를 반복한다.

 

2. 코드 분석

[지코바] solved.ac CLASS 2 Part 4

  네 개 문제 모두 C++ 버전 풀이와 Python 버전 풀이가 있다. (대단하세요...) 알고리즘이 크게 다르진 않은 것 같으므로 C++ 코드만 분석하기로 한다.

#include <iostream>
#include <queue>

using namespace std;

// C++ 특유의 IO를 더 알아보기 쉽게 하는 input, print 함수
void input (int* i) {
  cin >> *i;
}

void print (int o) {
  cout << o << '\n';
}

int main() {
  int n;
  queue<int> cards;
  
  // 카드 더미의 카드 수 n을 입력 받음
  input(&n);
	
  // 홀수는 모두 제거 되는 구조이기 때문에, 2부터 n까지의 짝수 카드 더미 생성
  for (int i=0; i<n/2; i++) {
    cards.push((i+1)*2);
  }
  
  if (n == 1) {	// n이 1인 경우 이미 남은 카드가 1장
    print(1);	// 따라서 1을 출력
  } else {
    if (n % 2 != 0) {	// n이 홀수면 카드를 맨 뒤로 옮기는 과정이 한 번 필요
      cards.push(cards.front());	// 맨 앞의 카드를 맨 뒤로 옮김
      cards.pop();
    }
    while(cards.size() > 1) {	// cards의 크기가 1보다 크면 반복
      cards.pop();	// 맨 앞 카드를 버리고
      cards.push(cards.front()); // 맨 앞 카드가 된 카드를 맨 뒤에 옮김
      cards.pop();
    }
    
    // 출력
    print(cards.front());
  }

  return 0;
}

 

  눈여겨 볼 부분은 카드 더미를 생성하는 부분이다. 위 규칙을 따르며 카드를 제거해 나가다 보면 다시 카드는 짝수만 남은 상태로 정렬될 것이다. 이러한 점을 이용해, 카드 더미를 처음부터 짝수로만 구성되도록 하신 점이 인상적이다. 홀수를 제거하는 과정을 없앰으로써 메모리와 시간이 획기적으로 단축되었다.

위) 상수님 코드 / 아래) 내 코드

 

  생각을 한 번 더 하냐 덜 하냐의 차이가 위 결과처럼 나타난 것 같다. 의식적으로 생각을 한 번 더 하고 문제 풀이를 해야겠다.