https://www.acmicpc.net/problem/2668
2668번: 숫자고르기
세로 두 줄, 가로로 N개의 칸으로 이루어진 표가 있다. 첫째 줄의 각 칸에는 정수 1, 2, …, N이 차례대로 들어 있고 둘째 줄의 각 칸에는 1이상 N이하인 정수가 들어 있다. 첫째 줄에서 숫자를 적절
www.acmicpc.net
이 글을 읽는다면 문제는 이미 다 알고 있다고 생각합니다.
구해야하는 정답은 첫 번째 줄에서 뽑은 수와 두 번째에서 뽑은 수가 같은 집합의 최대 크기이다.
두번째 줄에서 주어진 수에서 인덱스번호가 없는 2와 7은 첫번째 줄에서 선택할 필요가 없다.
-> 왜냐하면 2와 7을 뽑아봤자 2번째 줄에 2와 7이 없기 때문에 같은 수를 뽑을 수가 없기 때문이다.
일단 이해하기 쉽도록 그래프를 그려줍니다.
-> 그래프를 그릴 때 각 노드들은 인덱스 번호이며 연결되어있는 값들은 2번째 줄에서 준 값들의 인덱스 번호입니다.
그럼으로 2와 7을 기준으로 각 노드들에 연결되어 있는 2와 7를 제거합니다.
## 먼저 2를 제거합니다
2가 연결된 곳은 1 번 노드였고 1번 노드에 자식 노드가 있음으로 제거할 대상이 아닙니다. 이후 2가 연결된 곳이 없음으로 7를 제거합니다.
## 7 제거
7이 연결된 곳은 6이었고, 지우니, 자식 노드가 없습니다. 이로 인해 6도 사용하지 못합니다. 그럼으로 6도 지워줍니다.
## 6 제거
6이 연결된 곳은 4였고 지우니, 자식 노드가 없으므로 쓰지 못합니다.
## 4 제거
4가 연결된 곳은 5였고 제거하니 자식 노드가 남아있음으로 제거를 멈춥니다.
다 제거하고 나니 사용가능한 수는 총 3개입니다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int inputs[101];
vector<int> adj[101];
int main() {
int n;
cin >> n;
for(int i=1; i<=n; i++) {
cin >> inputs[i];
adj[inputs[i]].push_back(i);
}
int answer = n;
for(int i=1; i<=n; i++) {
if(adj[i].size() == 0) {
int k = i;
int index = inputs[i];
while(true) {
// 제거
for(int j=0; j<adj[index].size(); j++) {
if(adj[index][j] == k) {
adj[index].erase(adj[index].begin()+ j);
answer--;
break;
}
}
if(adj[index].size() == 0) {
k = index;
index = inputs[index];
} else {
break;
}
}
}
}
vector<int> answers;
for(int i=1; i<=n; i++) {
if(adj[i].size() != 0 ) {
for(int j=0; j<adj[i].size(); j++) {
answers.push_back(adj[i][j]);
}
}
}
sort(answers.begin(), answers.end());
cout << answer << "\n";
for(int i=0; i<answers.size(); i++){
cout << answers[i] << "\n";
}
}## 재귀로 작성
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int inputs[101];
vector<int> adj[101];
int answer;
int n;
void remove(vector<int>& temp, int target){
for(int j=0; j<temp.size(); j++) {
if(temp[j] == target) {
temp.erase(temp.begin()+ j);
answer--;
break;
}
}
}
void recrucive(int target, int index) {
remove(adj[index], target);
if(adj[index].size() == 0) {
recrucive(index, inputs[index]);
} else {
return;
}
}
int main() {
cin >> n;
answer = n;
for(int i=1; i<=n; i++) {
cin >> inputs[i];
adj[inputs[i]].push_back(i);
}
for(int i=1; i<=n; i++) {
if(adj[i].size() == 0) {
recrucive(i, inputs[i]);
}
}
vector<int> answers;
for(int i=1; i<=n; i++) {
if(adj[i].size() != 0 ) {
for(int j=0; j<adj[i].size(); j++) {
answers.push_back(adj[i][j]);
}
}
}
sort(answers.begin(), answers.end());
cout << answer << "\n";
for(int i=0; i<answers.size(); i++){
cout << answers[i] << "\n";
}
}
'코딩 관련 > c++' 카테고리의 다른 글
| 공원 산책 프로그래머스 (0) | 2023.06.21 |
|---|---|
| 프로그래머스 할인행사 (0) | 2022.12.17 |
| 백준 1, 2, 3 더하기 5 문제 분석 (0) | 2022.08.09 |
| 이집트인의 곱셈 (0) | 2021.08.24 |
| 스택 응용 분석해보기 1편 (0) | 2021.08.24 |
