[코딩테스트 챌린지] 백준 10451 순열 사이클 (java)

문제

https://www.acmicpc.net/problem/10451

 

문제 탐색하기

1. 순열 사이클 규칙 파악하기

 

문제에 예시로 보여주는 문제를 통해서 규칙을 파악해보도록 하겠습니다. 문제의 순열 배열을 아래의 그림으로 나타냈습니다. 

 

1은 3을 가르키고 3은 7을 가르키며 7은 5, 5는 다시 1을 가르키고 있습니다. 

순열 배열의 첫번째 인덱스인 1부터 시작해서 가르키는 순열을 그림으로 나타내보면 다음과 같습니다.

5가 다시 1을 가르켰을 때 순열 사이클 1개가 완성됩니다.

순열 배열의 주황색 박스를 key, 초록색 박사를 순열, 즉 value로 생각해보면

순열 사이클이 시작되는 첫번째 key 값이 마지막 value가 될 때 순열 사이클이 1개 완성된다는 규칙이 있다는 것을 알 수 있었습니다.

 

따라서, 순서를 보장하는 LinkedHashMap에 key값은 순열 배열의 인덱스, value 값은 인덱스에 맞는 순열을 추가해서 순열 map을 만들어줍니다. 이 Map을 통해서 순열 사이클을 만들어주는 loop를 만들 수 있습니다.

(* LinkedHashMap을 사용한 이유는 한 개의 순열 사이클을 만들고 다음 순열 사이클을 만들 때 문제에 보여지는 순열 배열처럼 순차적으로 진행되는 것을 바래서 사용했습니다. HashMap을 통해서도 문제를 풀 수 있습니다.)

 

• 순열 사이클 검증로직
  1. N만큼 반복하는 loop를 생성합니다.
  2. map의 key 값을 얻어서 value를 구합니다.
  3. 순열 사이클 첫 시작지점의 key 값은 따로 저장해줍니다.
  4. 구한 value 값을 key로 다시 세팅해서 map에 조회합니다.
  5. 이때 value 값을 한번 구하게 되면 map에서 삭제해주는 과정이 필요합니다. (다시 조회하지 않게 하기 위해)
  6. 처음에 저장했던 순열 사이클 첫 시작지점과 value값이 같으면 순열 사이클 1개가 완성된 것입니다.
  7. key 값과 순열 사이클 첫 시작지점은 map의 다음 값으로 초기화시켜 줍니다.

위의 검증로직을 코드로 구현하면 순열 사이클의 개수를 구할 수 있습니다.

 

2. 시간복잡도 파악하기

• 전체 시간 복잡도:
  • 각 테스트 케이스마다 loop안에서 순열 사이클을 탐색하면서 N개의 요소를 처리하며, 각 요소에 대해 작업을 수행해야합니다.
    따라서, 하나의 테스트 케이스에 대한 시간 복잡도는 O(N) 이 될 것 입니다.
  • T개의 테스트 케이스가 있으므로 전체 시간 복잡도는 O(T * N) 입니다.
  • N은 최대 1000까지 주어질 수 있으므로 T*1000건의 탐색이 이뤄질 것 이고 T는 크게 영향을 미치지 않을 값으로 생각해본다면 충분히 시간 내에 풀 수 있는 로직으로 작성할 수 있을 것 같습니다.

 

코드 설계하기

1. 순서를 보장하는 LinkedHashMap을 선언해서 순열을 저장합니다.
   1. key : 1 ~ N까지의 정수, value : key 에 맞는 순열
2. 초기값 세팅
   1. 사이클이 시작되는 지점의 key값을 저장하는 firstFlag 변수 선언 : int firstFlag = 0
   2. map의 key 값을 저장할 변수 선언 : int key = 0;
3. 순열 사이클 갯수를 카운팅하는 변수 선언
4. 순열 사이클 체크
   1. loop 첫번째 진행 : LinkedHashMap에 저장되어있는 첫번째 키값을 key 변수에 저장하고 firstFlag에 저장하게 합니다. 그리고 순열 사이클 카운팅 변수도 +1 진행합니다.
   2. map에서 key 값으로 찾은 value값을 다시 key 변수에 저장합니다.
   3. 반복문을 진행하면서 key 값과 순열사이클 시작 key값을 저장한 firstFlag 변수가 일치할때 순열 사이클이 완성된 것으로 처리하여 1번 처럼 map에 저장되어있는 키값을 가져와서 key와 firstFlag 변수를 초기화 해줍니다. (카운팅 변수 + 1)
5. 순열 사이클 갯수 출력

 

정답 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.StringTokenizer;

public class Graph {

    public static void main(String[] args) throws IOException {

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(reader.readLine());
        StringTokenizer st;

        StringBuilder sb = new StringBuilder();

        for(int i=0; i<T; i++){
            int N = Integer.parseInt(reader.readLine());
            st = new StringTokenizer(reader.readLine());

            // 1. 순서를 보장하는 LinkedHashMap을 선언해서 순열을 저장한다.
            Map<Integer, Integer> map = new LinkedHashMap<>();
            for(int j=0; j<N; j++){
                // 1-1. key : 1 ~ N까지의 정수, value : key에 맞는 순열
                map.put(j+1, Integer.parseInt(st.nextToken()));
            }

            // 2. 초기값 세팅
            int firstFlag = 0; // 2-1. 사이클이 시작되는 지점의 key값 저장하는 변수
            int key = 0; // 2-2. map의 key 값을 저장할 변수
            int value = 0; // 2-3. map의 value 값을 저장할 변수

            // 3. 순열사이클 갯수를 카운팅하는 변수
            int count = 0;

            // 4. 순열사이클 체크
            for(int k=0; k<N; k++){
                if(key == firstFlag){
                    /**
                     * key와 firstFlag에 저장된 변수가 같을 경우
                     * 순열사이클이 만들어졌다는 것이므로
                     * map에서 다음 키값을 가져와서 key에 다시 세팅하고
                     * firstFlag 역시 이 key값으로 초기화한다.
                     *
                     * 처음 for문을 진행할때 firstFlag = 0, key = 0 이기에
                     * 이 조건문을 타게된다. 즉, 순열사이클 카운트는 사이클이
                     * 시작할떄 +1 하며 진행된다.
                      */
                    key = map.entrySet().iterator().next().getKey();
                    firstFlag = key;
                    count++;
                }
                value = map.remove(key); // # 한번 for문을 돌면서 검증한 map의 원소는 삭제
                key = value; // # value를 다시 key에 저장
            }

            sb.append(count).append("\n");
        }

		// 5. 출력
        System.out.println(sb.toString());
    }
}