[Baekjoon] 2668_숫자고르기

Gold V

문제(출처: https://www.acmicpc.net/problem/2668)

---

< 숫자 고르기 >

 

문제 풀이 

 

첫째줄과 둘째 줄에 들어 있는 정수들이 이루는 집합이 일치해야 하는 것을 골라야 하는 문제였다.

일치하는지 판단하기 위해 TreeSet을 활용했다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.TreeSet;

public class _2668_ { // 숫자고르기
	static int arr[];
	static TreeSet<Integer> set, a, b;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(bf.readLine());

		arr = new int[n + 1];
		for (int i = 1; i <= n; i++) {
			arr[i] = Integer.parseInt(bf.readLine());
		}

		set = new TreeSet<>();
		a = new TreeSet<>();
		b = new TreeSet<>();

		for (int i = 1; i <= n; i++) {
			if (set.contains(i)) {
				continue;
			}
			dfs(i);
			if (a.equals(b)) {
				for (int num : a) {
					set.add(num);
				}
			}
			a.clear();
			b.clear();
		}

		bw.write(set.size()+"\n");
		for(int num: set) {
			bw.write(num+"\n");
		}
		bw.flush();

	}

	private static void dfs( int i) {
		a.add(i);
		b.add(arr[i]);
		if(a.contains(arr[i])) return;
		dfs(arr[i]);
	}
}

 

Main

변수)
n : 표 크기
arr : 정수 저장
set : 최종으로 뽑힌 정수
a, b : 첫째 줄, 둘째 줄에서 뽑힌 정수들

 

- 표 크기(n) 입력

- 표 크기(n)만큼 정보를 입력받아 정수 저장(arr)

- 표 크기만큼 반복

: 이 값이 이미 set에 포함되었다면 넘김

: dfs 함수 호출

: 첫째 줄(a)과 둘째 줄(a)이 동일하다면 집합이 일치하다는 뜻이므로 set에 추가

- set의 크기와 set의 값 출력

 

dfs

- 첫째 줄 값을 a에 저장

- 둘째 줄 값을 b에 저장

- 둘째 줄 값이 이미 a에 포함되어 있다면 종료

- 포함되어있지 않다면 dfs 함수 호출

---

---