🔗 문제 링크
https://www.acmicpc.net/problem/1889
✍️ 문제 풀이
해당 문제는 우선순위큐를 사용했다. 받은 선물 개수를 체크하여 2개 미만일 경우 가장 먼저 참가 목록에서 제외하는 방식으로 풀었다.
1) 각 학생에 대해 [진입차수(선물 받은 수), 참여 여부, 진출 노드1, 진출 노드2 (해당 학생이 선물 준 학생1, 2)]를 저장하는 tuple들을 저장하는 벡터를 선언한다.
2) 각 학생이 2명에게 주는 선물을 입력받아 받은 학생들의 진입 차수를 증가시키고, 준 학생의 진출 노드1, 2를 갱신한다. 그리고 모든 학생의 참여 여부는 true로 갱신해놓는다.
3) 반복문을 돌며 벡터 내의 모든 학생들의 정보를 확인해 모든 학생이 조건을 충족할 때까지 학생들을 참가 목록에서 제외시킨다. 조건을 충족한 학생은 count 변수에 누적 시켜 인원수를 확인한다.
- 만약 받은 선물이 2개 미만인데 참가 목록에 남아있는 경우
- 해당 학생은 참가 목록에서 제외되기 때문에 이 학생으로부터 선물 받은 학생들의 진입 차수 -1
- 이후 해당 학생의 참가 여부 false로 갱신
- 이외의 경우
- 참가 목록에 없거나, 받은 선물이 2개인 경우 count에 1을 더해준다.
-> 최종 결과에 남아있을 수 있는 유일한 두 가지 조건
- 참가 목록에 없거나, 받은 선물이 2개인 경우 count에 1을 더해준다.
- 반복이 한 번 끝날 때마다 count를 확인해 count == 모든 학생의 수일 경우 반복을 종료한다.
4) 이후 모든 학생의 참여 여부를 확인해 참여 여부가 true인 학생들의 수와 번호(인덱스)를 확인해 출력한다.
🖥️ 풀이 코드
#include <stdio.h>
#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
int main(int argc, char** argv)
{
ios::sync_with_stdio(false);
cin.tie(); cout.tie();
int n = 0;
cin >> n;
vector<tuple<int, bool, int, int>> students(n); // 진입차수(선물 받은 수), 참여 여부, 진출노드 1(해당 학생이 선물 준 학생 1), 진출노드 2(학생 2)
for (int i = 0; i < n; i++)
{
int a, b;
cin >> a >> b;
// i번째 학생이 선물을 준 학생들의 진입 차수 + 1
get<0>(students[a - 1]) += 1;
get<0>(students[b - 1]) += 1;
// 참여 여부 갱신
get<1>(students[i]) = true;
// i번째 학생이 선물 준 학생 1, 2 갱신
get<2>(students[i]) = a;
get<3>(students[i]) = b;
}
bool check = false;
while(!check)
{
int count = 0;
for (int i = 0; i < students.size(); i++)
{
if (get<0>(students[i]) < 2 && get<1>(students[i])) // 받은 선물이 2개 미만이고, 아직 참가 목록에 남아있는 경우
{
int a = get<2>(students[i]);
int b = get<3>(students[i]);
// 해당 학생은 참가 목록에서 제외되기 때문에 이 학생으로부터 선물 받은 학생들의 선물 개수 -1
get<0>(students[a - 1]) -= 1;
get<0>(students[b - 1]) -= 1;
get<1>(students[i]) = false; // 참가 목록에서 제외
}
else
{
if (!get<1>(students[i]) || get<0>(students[i]) == 2) // 참가 목록에 없거나, 받은 선물이 2개인 경우 -> 최종 결과에 남아있을 수 있는 유일한 두 가지 조건
count++;
}
}
if (count == n) // 모든 학생이 조건을 충족할 경우
check = true;
}
vector<int> result;
for (int i = 0; i < n; i++)
{
if (get<1>(students[i]))
result.push_back(i + 1);
}
cout << result.size();
if (result.size() > 0)
{
cout << '\n';
for (int i = 0; i < result.size(); i++)
cout << result[i] << ' ';
}
}
🖥️ 실패 코드 1
: 일단 참여 여부를 체크만 하면 되는데 벡터에서 아예 erase 하는 바람에 시간 효율성이 떨어지게 된 것 같다. 그리고 erase 할 경우 벡터가 변화하기 때문에 탐색에 문제가 있을 것이라고 생각했는지 erase할 때마다 다시 처음으로 돌아가서 탐색했었다. 마지막으로 우선순위 큐 문제이기 때문에 우선순위가 높은 케이스(받은 선물 개수가 2개 미만인 경우)를 가장 앞에 두어야 한다고 생각했는지 계속 학생들의 진입 차수(선물 받은 수)를 기준으로 오름차순 정렬을 해주었다. 이렇게 [불필요한 반복 + 정렬 + 벡터 erase] 등 총체적 난국으로 인해 시간 초과가 발생하게 되었다.
#include <stdio.h>
#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
bool Compare(tuple<int, int, int, int> a, tuple<int, int, int, int> b)
{
return get<1>(a) < get<1>(b);
}
int main(int argc, char** argv)
{
ios::sync_with_stdio(false);
cin.tie(); cout.tie();
int n = 0;
cin >> n;
vector<tuple<int, int, int, int>> students(n); // 진입차수(선물 받은 수), 학생 번호, 진출노드 1(해당 학생이 선물 준 학생 1), 진출노드 2(학생 2)
for (int i = 0; i < n; i++)
{
int a, b;
cin >> a >> b;
// i번째 학생이 선물을 준 학생들의 진입 차수 + 1
get<0>(students[a - 1]) += 1;
get<0>(students[b - 1]) += 1;
// 학생 번호 갱신
get<1>(students[i]) = i + 1;
// i번째 학생이 선물 준 학생 1, 2 갱신
get<2>(students[i]) = a;
get<3>(students[i]) = b;
}
bool check = false;
while (!check)
{
if (students.size() == 0)
{
cout << 0;
return 0;
}
sort(students.begin(), students.end());
for (int i = 0; i < students.size(); i++)
{
if (get<0>(students[i]) != 2)
{
int a = get<2>(students[i]);
int b = get<3>(students[i]);
int idxA = find_if(students.begin(), students.end(), [=](const tuple<int, int, int, int>& e) {return get<1>(e) == a; }) - students.begin();
int idxB = find_if(students.begin(), students.end(), [=](const tuple<int, int, int, int>& e) {return get<1>(e) == b; }) - students.begin();
if (idxA != students.size()) get<0>(students[idxA]) -= 1;
if (idxB != students.size()) get<0>(students[idxB]) -= 1;
students.erase(students.begin());
break;
}
else
{
if (i == students.size() - 1)
check = true;
}
}
}
sort(students.begin(), students.end(), Compare);
cout << students.size() << endl;
for (int i = 0; i < students.size(); i++)
cout << get<1>(students[i]) << ' ';
}🖥️ 실패 코드 2
: 이후에는 정렬을 하지 않고, 참여 목록에서 제외하는 것도 벡터에서 erase 하는 것이 아닌 bool 변수 갱신으로 체크해주었다. 다만 이 때까지도 참여 목록에서 제외시켜줄 때마다 처음으로 돌아가는 것은 고치지 못해서 시간 초과는 여전히 발생했다. 왜 이렇게 생각했을까? 아마 한 학생을 제외시킬 때마다 다른 학생들의 진입 차수도 변화하기 때문에 이것이 뒷 요소들의 탐색에 문제를 일으킬 것이라고 생각했던 것 같다.
#include <stdio.h>
#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>
using namespace std;
bool Compare(tuple<int, int, int, int> a, tuple<int, int, int, int> b)
{
return get<1>(a) < get<1>(b);
}
int main(int argc, char** argv)
{
ios::sync_with_stdio(false);
cin.tie(); cout.tie();
int n = 0;
cin >> n;
vector<tuple<int, bool, int, int>> students(n); // 진입차수(선물 받은 수), 참여 여부, 진출노드 1(해당 학생이 선물 준 학생 1), 진출노드 2(학생 2)
for (int i = 0; i < n; i++)
{
int a, b;
cin >> a >> b;
// i번째 학생이 선물을 준 학생들의 진입 차수 + 1
get<0>(students[a - 1]) += 1;
get<0>(students[b - 1]) += 1;
// 참여 여부 갱신
get<1>(students[i]) = true;
// i번째 학생이 선물 준 학생 1, 2 갱신
get<2>(students[i]) = a;
get<3>(students[i]) = b;
}
bool check = false;
int check_erase = 0;
while (!check)
{
for (int i = 0; i < students.size(); i++)
{
if (get<0>(students[i]) < 2 && get<1>(students[i]))
{
int a = get<2>(students[i]);
int b = get<3>(students[i]);
get<0>(students[a - 1]) -= 1;
get<0>(students[b - 1]) -= 1;
get<1>(students[i]) = false;
break;
}
else
{
if (i == students.size() - 1)
check = true;
}
}
}
vector<int> result;
for (int i = 0; i < n; i++)
{
if (get<1>(students[i]))
result.push_back(i + 1);
}
cout << result.size() << endl;
for (int i = 0; i < result.size(); i++)
cout << result[i] << ' ';
}
게임 클라이언트 개발자 지망생의 TIL