[JAVA] 10451번 - 순열 사이클

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

문제 이해

순열 사이클의 개수를 구하는 문제이다. 

위쪽은 인덱스고 밑에는 입력받은 배열값이다!

순열을 입력받아서 배열에 저장하고 그 배열을 돌면서 1번노드부터(인덱스는 1번부터 늘 시작이니까)  방문했는지 체크를 한다. 이미 방문했던 노드를 다시 방문하면 싸이클이 생긴다! 

이때 개수를 증가시킨다.

 

** 처음에는 1부터 n까지 배열을 따로 만들려고 햇는데 곰곰히 생각해보니 인덱스로 접근하는게 더 나을 것 같아서 인덱스 -> 배열 이렇게 접근했다

 

=> arr[k] 이렇게 하면 자연스럽게 1인덱스에 맞는 값(밑에 순열배열 부분) 을 이용해서 풀 수 있다

1. 방문하지 않은 노드는 방문 했다고 체크

2. arr[k]에 해당하는 값(next)가 다음 arr의 인덱스번호가 된다 이렇게 하면 싸이클이 완성될떄(=처음 시작했던 인덱스 번호로 돌아옴) 카운트를 증가한다 

 

시간복잡도

전체 순열을 한번만 탐색하면 된다.

그러므로 O(n) 이고 O(1000)이다 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. t만큼 입력을 받으면서

2. 순열배열을 만들어 입력을 받는다

3. 순열배열을 반복문돌면서 방문여부를 체크하고 싸이클 여부를 확인

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int[] arr;
	static int n,m,k=0;
	static boolean[]isVisited;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
             
        int t = Integer.parseInt(br.readLine());
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();

        
        for(int i=0; i<t; i++) {
        	n = Integer.parseInt(br.readLine());
        	arr = new int[n+1];
            isVisited = new boolean[n + 1];
            
            st = new StringTokenizer(br.readLine());
            //배열이 순열 숫자를 채움
        	for(int j=1; j<=n; j++) {	
        		arr[j] = Integer.parseInt(st.nextToken());
        	}
        	
        	int cnt=0;
        	for(int k=1; k<=n; k++) {
        		if(!isVisited[k]) {
        			isVisited[k] = true; //방문처리
        			int next = arr[k];
        			while(true) {
        				if(isVisited[next]) {
        					cnt++;
        					break;
        				}
        				isVisited[next] = true;
        				next = arr[next];
        			}
        		}
        	}
        	
        	System.out.println(cnt);
        }
    
    }
}