코딩테스트 챌린지

[코딩테스트 챌린지] 백준 17204 죽음의 게임 (java)

zincah 2024. 9. 22. 16:01
반응형

문제

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

 

문제 탐색하기

1. 영기가 말해야하는 번호 

보성이가 게임에서 걸리게 하기 위해서는 영기부터 시작해서 보성이의 번호를 부르는 과정까지 총 몇번의 차례가 진행되는 지 알아내서 영기가 그 번호를 말하면 됩니다. 게임의 규칙에 따라 보성이가 걸리지 않을 수 있으므로 그 때에는 -1를 리턴하는 것을 고려해야 합니다.

 

즉, 한 곳에서 시작해서 결과값이 나올때까지 탐색하며 결과값이 나오지 않을 경우에는 -1을 리턴하면 되는 문제입니다.

 

2. 시간복잡도 탐색

보성이가 걸리지 않을 경우가 최대 탐색하는 경우이기 때문에 N회의 탐색 즉, O(N)의 시간복잡도를 가지게 됩니다.

 

코드 설계하기

  1. 게임 참가 수, 보성이의 번호를 각각의 변수에 저장
  2. i번째 사람이 지목하는 사람의 번호를 ArrayList에 저장
  3. 초기값 세팅 : list 의 인덱스를 저장할 변수 선언 int seq = 0
  4. 영기가 말해야하는 번호 변수를 -1로 선언 (보성이가 걸리지 않을 경우 -1을 그대로 리턴하기 위해 선언합니다.) int result = -1
  5. N회를 탐색할때 list에 seq로 얻어낸 값을 seq에 저장하는 과정을 반복합니다.
  6. 탐색하는 과정에서 i-1번째 사람이 가르킨 번호가 보성이의 번호일 경우 i를 result 변수에 저장하고 loop를 끝냅니다. 
  7. result 출력

 

정답 코드 

package backjun;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class TheGameOfDeath {

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

        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int N = Integer.parseInt(st.nextToken()); // 게임에 참가나는 사람 수 입력
        int K = Integer.parseInt(st.nextToken()); // 보성이의 번호

        List<Integer> list = new ArrayList<>();
        for(int i=0; i<N; i++){
            // i번사람이 지목하는 사람의 번호 --> list에 저장
            list.add(Integer.parseInt(reader.readLine()));
        }

        int seq = 0;
        int result = -1; // 보성이가 걸리지 않을 경우 -1 리턴하기 위해 초기값으로 저장
        for(int i=0; i<N; i++){
            // N회를 탐색하면서 i-1번째 사람이 가르킨 번호가 보성이의 번호일 경우 i를 return
            if(seq == K){
                result = i;
                break;
            }
            seq = list.get(seq);
        }

        System.out.println(result);
    }
}
반응형