[코테 대비]백준 #2164 카드2, #5430 AC, #1972 최소힙, #2696 중앙값 구하기 풀이

#2164 카드 2, C++ 사용

https://www.acmicpc.net/problem/2164

 

티어는 실버IV이고, 문제는 다음과 같다.

문제 이해

# 우선 제일 위에 있는 카드를 바닥에 버린다.
# 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다.
# 규칙 : 버리고 밑으로 옮기고,,, 반복

# 예를 들어, N=6 -> 1,2,3,4,5,6

#0 1 버리고
#1 2는 맨뒤로, 3,4,5,6,2
#2 3 버리고
#3 4는 맨뒤로, 5,6,2,4
#4 5는 버리고
#5 6은 맨뒤로, 2,4,6
#6 2는 버리고
#7 4는 맨뒤로, 6,4
#8 6은 버림
#9 4가 남게됨
따라서 큐 활용해야한다.

# 예를 들어, N=4 -> 1,2,3,4
#0 1버리고
#1 2는 맨뒤로 3,4,2
#2 3 버리고, 4,2
#3 4는 맨뒤로, 2,4
#4 2 버리고, 4
#5 4 남게됨 

# 예들 들어, N=3 -> 1,2,3
#0 1버리고
#1 2는 맨뒤로 3,2
#2 3 버리고 2
#3 2가 남음

 

코드구현 

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

int solution(int N, queue<int> q)
{
	int last,i=0;
	vector<int> v;
	while(!q.empty())
	{
		if (i % 2 == 0)
		{
			v.push_back(q.front());
			q.pop();
		}
		else
		{
			int num = q.front();
			//cout << "num: " << num << "\n";
			q.push(num);
			q.pop(); // 앞에 있는 요소는 무조건 pop해줘야함
		}
		
		i++;
	}
	last = v.back();
	//cout<<v.back()<<'\n';
	return last;
}
int main()
{
	int N,result;
	queue<int> q;
	//입력
	cin >> N;
	for (int i = 1; i <= N; i++)
	{
		q.push(i);
	}
	//연산
	result = solution(N,q);

	//출력
	cout << result;

}

나는 일단 문제 그대로 구현했다.

코드를 구현할 때 어려웠던 점은 "어떻게 queue가 비어지기전 마지막 수를 출력할것인가"이었다.

그래서 나는 생각한것이 벡터 라이브러리로 이용하여 배열에 버린수를 저장시킨다. 비어지기전 마지막 수도 결국 버려질것이기 때문이다. 

---

#5430 AC, C++ 사용

https://www.acmicpc.net/problem/5430

 

골드 V이고, 문제는 다음과 같다:

 

일단 넘어가....!

푸는 중...!

 

---

#1927 최소힙, C++

https://www.acmicpc.net/problem/1927

 

문제이해

최소힙 문제라서 우선순위 큐를 이용하였고, 제일 작은 값, 맨 앞에 있는 수를 출력하고 제거했다.

코드 구현

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

/*
	최소힙 문제
	배열에 자연수 x를 넣는다
	배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.

	프로그램은 처음에 비어있는 배열에서 시작
*/

priority_queue<int, vector<int>, greater<int>> q;
// 지역번수는 연산할 때마다 새로 선언되기 때문에 데이터가 유지되지 않는 문제가 있다.
// 전역변수로 해야 데이터가 유지가 된다.
void solution(int num)
{

	if (num == 0)   // 0일때 가장 작은 값을 출력, 비어있을경우 0 출력
	{
		if (q.empty())
			cout << 0 <<"\n";
		else
		{
			cout << q.top() <<"\n";
			q.pop();
		}
	}
	else
	{
		q.push(num);

	}
	
}

int main()
{
	ios::sync_with_stdio(false); // 입출력 속도 최적화
	cin.tie(nullptr); // 입출력 묶음 해제

	int N; int num; int result;
	//vector<int> v;

	// 입력
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		// 연산
		cin >> num;
		solution(num);
	}
	return 0;
}

여기서 풀 때 힘들었던 점은 변수 선언이다. 지역변수로 계속했지만, 지역변수는 연산할 때마다 새로 선언되기 떄문에 데이터가 유지되지 않는 문제가 있었다. 전역변수로 해야된다.

ios::sync_with_stdio(false); // 입출력 속도 최적화
cin.tie(nullptr); // 입출력 묶음 해제

이 코드로 시간초과를 잡았다.

 

---

#2696 중앙값 구하기

푸는 중!!!