접근 방법
- 이미 비행기가 연결된 게이트는 더 이상 비행기가 접근할 수 없다. 만약 1번 게이트부터 시작해서 올라간다면 비행기가 있는지 없는지 보고 만약 있다면 또 옆으로 옮길 수 있는지 여부를 봐야하는데 이렇게 되면 시간이 너무 많이 들 것 같았다.
- 그래서 최대 게이트에 대해 내림차순으로 정렬을 하고 하면 옮길 필요가 없다고 생각했는데 문제를 잘보니 비행기가 순서대로 들어온다고 돼있어서 정렬은 안된다고 생각했다.
- 2번 방식과 비슷하게 접근가능한 게이트 중 가장 숫자가 큰 게이트부터 1번 게이트로 가면 불필요한 연산을 줄일 수 있을 것 같았다. 그래도 이것만 적용하면 매번 중복된 곳에서 비교연산을 해야한다고 생각했다. 만약 중복 비교연산 경우를 허용하면 worst case의 시간복잡도가 n^2이 되기 때문에 이 점을 어떻게 개선할지 생각해봤다.
- 따라서 현재접근 가능한 가장 숫자가 큰 게이트와 가장 작은 게이트를 가리키는 변수를 선언하고 만약 현재 접근한 게이트가 가장 큰 게이트와 같으면 그 게이트에서 1을 빼주고 가장 작은 게이트랑 같으면 1을 더해줘서 반복문에 대한 범위를 최대한 줄이려고 했다.
추가(분리집합)
인터넷에 찾아보니 분리집합을 이용하여 푸는 방법도 있는 것을 확인했다.
접근 방식은 위 접근 방식과 비슷하다. 입력받은 게이트에 대하여 만약 이 게이트가 비어있지 않다면 바로 앞 게이트를 가리켜주고 또 그 게이트도 비어있지 않다면 그 앞 게이트를 가리켜주는 식이다. 마치 루트를 같게 하는 집합을 만드는 것과 같다.
만약 2 3 4 4를 입력받으면 차례대로 2에 접근하고 2는 1을 가리키게 3에 접근하면 3은 2를 가리키게 4에 접근하면 3을 가리키게 한다. 그 다음에 4를 가리키면 이미 도킹되었기에 4 -> 3 -> 2 -> 1이 되어 1에 도킹하게 된다.
이런식으로 만약 루트가 0이 나오면 더 이상 도킹하지 못하므로 종료를 하면된다.
두 방식으로 구현해보니 분리집합은 find를 하는데 log2n밖에 걸리지 않으니 더 빠른 것을 알 수 있었고 실제로도 10배정도 더 빠르게 나왔다.
그리디 코드
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
int G,P;
int isDocked[100001] = { 0 };
int byGate[100001] = { 0 };
int main()
{
cin >> G >> P;
int largest_gate = -100;
int smallest_gate = 1;
for (int i = 1; i <= P; i++)
{
cin >> byGate[i];
largest_gate = max(byGate[i], largest_gate);
}
int cnt = 0;
for (int i = 1; i <= P; i++)
{
int gate = byGate[i];
gate = (gate >= largest_gate) ? largest_gate : gate;
bool isdocked = false;
for (int j = gate; j >= smallest_gate; j--)
{
if (isDocked[j] == 0)
{
isdocked = true;
isDocked[j] = 1;
cnt++;
if (j == largest_gate)
{
largest_gate--;
}
if (j == smallest_gate)
{
smallest_gate++;
}
break;
}
}
if (isdocked == false)
{
break;
}
}
cout << cnt;
return 0;
}분리집합 코드
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
using namespace std;
int G,P;
int byGate[100001] = { 0 };
int univ[100001] = { 0 };
int find(int a)
{
if (a == univ[a])
return a;
return univ[a] = find(univ[a]);
}
void union_set(int a, int b)
{
a = find(a);
b = find(b);
if (a >= b)
{
univ[a] = b;
}
else
{
univ[a] = b;
}
}
int main()
{
cin >> G >> P;
int largest_gate = -100;
int smallest_gate = 1;
for (int i = 0; i <= 100000; i++)
{
univ[i] = i;
}
int cnt = 0;
for (int i = 1; i <= P; i++)
{
int gate;
cin >> gate;
int pGate = find(gate);
if (pGate == 0)
break;
cnt++;
union_set(pGate, pGate - 1);
}
cout << cnt;
return 0;
}