[C] 백준 - 2164번: 카드 2

4월 17일(월) - 큐, 덱 (2164번)

2164번: 카드2

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 큐의 push와 pop을 이용하면 될 것 같다

- 먼저 입력받은 N을 통해서, 1부터 N까지의 숫자를 큐에 push하며 저장해준다

- 그리고나서는 큐의 사이즈가 1로 줄어들기전까지,

  1) pop을 해준다

  2) 그 다음 숫자는 pop을 해준뒤에, 다시 push 해준다

  위의 과정을 계속 반복해주어야한다

  -> while문 사용

- 최종출력은...뭐로 뽑아내줘야하는지 약간 애매함 -> 풀이하면서 생각하기로

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

// 수정 전
int queue[500001];
int front = 0;
int rear = -1;

// 수정 후
int queue[1000002];
int front = 0;
int rear = -1;

1. 단순히 N의 최대값이 500,000이기 때문에 queue[500001]으로 설정했다

-> 런타임 에러(OutOfBounds) 가 발생

-> pop해준 값을, 다시 push하는 경우도 있기때문에 최대범위를 500,001의 2배인 1,000,002로 수정

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>
#include <string.h>

int queue[1000002];
int front = 0;
int rear = -1;

void push(int x)
{
	queue[++rear] = x;
}

int pop()
{
	if (rear - front + 1 == 0)
	{
		return -1;
	}
	else
	{
		return (queue[front++]);
	}
}

int size()
{
	return (rear - front + 1);
}

int empty()
{
	if (rear - front + 1 != 0)
	{
		return 0;
	}
	else
	{
		return 1;
	}
}

int main(void)
{
	int N;
	scanf("%d", &N);

	for (int i = 1; i <= N; i++)
	{
		push(i);
	}

	while (size() != 1)
	{
		pop();
		push(pop());
	}

	printf("%d", pop());
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ