[JAVA] 17204번 - 죽음의 게임

문제 탐색하기

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

 

어제 풀었던 순열사이클이랑 비슷한 원리로 접근하면 된다.

그리고 보성이가 걸리지 않는건 그림처럼 보성이 번호 K 빼고 사이클이 형성될때이다!

배열의 인덱스로 접근을 하되 경우의 수를 나눠서 접근하면 된다.

1. 보성이를 가리킬때

2. 보성이빼고 싸이클 형성될때

3. 아직 보성이한테 도착하지 않았을때(사이클도 형성X) 계속 지목하는 상황

시간복잡도

각 사람을 탐색하고 사이클을 확인헤야하니까 O(N) = O(150)이다 

 

 

 

코드 설계하기

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

1.배열을 입력받는다.

2. 각 경우의 수대로 탐색을 수행한다.

3. 출력한다.

 

시도 회차 수정 사항

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

 

1회차 시도

=> for문으로 배열크기만큼 돌면서 각각의 경우를 수행하려고 했는데 출력이 이상해서 다른방법을 씀 

        for(int i=0; i<arr.length; i++) {
        	if(!isVisited[i]) {
        		isVisited[i] = true;
        		int tmp = arr[i];
        		while(arr[i]!=k) {
        			if(isVisited[tmp]) 
        				System.out.println(-1);
        				break;
        			}
        			System.out.println(arr[i]);
        	}
        }

 

정답코드

=> while문을 돌면서 각 경우의 수대로 처리했다.

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 boolean[]isVisited;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
             
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        arr=new int[n];
        
        for(int i=0; i<n; i++) {
        	st = new StringTokenizer(br.readLine());
        	arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int m = 0;
        int cnt=0;
        int tmp = 0;
        boolean flag = false;
        isVisited = new boolean[n+1];

        
        while(true) {
        	if(arr[tmp]==k) { //보성이 번호에 걸리는경우 문제예시에서는 인덱스1이 3(보성)을 가리킬때
        		cnt++;
        		break;
        	}
        	else if(isVisited[arr[tmp]]) { //k없는 싸이클생성
        		flag = true;
        		break;
        	}
        	else {
        		tmp=arr[tmp];
        		isVisited[tmp]= true;
        		cnt++;
        	}
        }
        if(flag) {
        	System.out.println(-1);
        }
        else {
        	System.out.println(cnt);
        }
        
    }
}