[BOJ] 17827번 달팽이 리스트

문제

www.acmicpc.net/problem/17827

17827번: 달팽이 리스트

풀이

1) 시간 초과 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
import java.util.StringTokenizer;
import java.util.Map.*;


class Node{
    int num;
    int next;
    public Node(int num, int next){
        this.num = num;
        this.next = next;
    }
}
public class Main {
    static int answer(Node[] nodes,int K){
        Node move = nodes[1];
        int next = -1;
        for(int i=0;i<K;i++){
            next = move.next;
            move = nodes[next];
        }
        return nodes[next].num;
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());//N노드가 가리키는 노드
        Node[] nodes = new Node[N+1];
        //노드
        st = new StringTokenizer(br.readLine());
        nodes[1] = new Node(Integer.parseInt(st.nextToken()),0);
        for(int i=2;i<=N;i++){
            nodes[i] = new Node(Integer.parseInt(st.nextToken()),0);
            nodes[i-1].next = i;
        }
        nodes[N].next = V;
        //질문
        for(int i=0;i<M;i++)
            sb.append(answer(nodes,Integer.parseInt(br.readLine()))+"\n");
        System.out.println(sb);
    }
}

2) 수정 코드

1) k < n 경우엔 k번째 요소를 바로 리턴하면 된다.

2) 이외 경우

2-1) 순환되는 부분 길이 : n - (v-1)

2-2) 순환되지 않는 크기만큼 k값에서 빼주기 : k - (v-1)

3) 원하는 k 번쨰 값의 인덱스 : (k-(v-1))%(n-(v-1)) +v-1

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;
import java.util.StringTokenizer;
import java.util.Map.*;


public class Main {
    static int getAnswer(int[] list, int n, int v, int k){
        if(k<n)
            return list[k];
        else
            return list[(k-(v-1))%(n-(v-1))+v-1];
    }
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int V = Integer.parseInt(st.nextToken());//N노드가 가리키는 노드
        int[] list = new int[N+1];
        st = new StringTokenizer(br.readLine());
        list[0] = Integer.parseInt(st.nextToken());
        for(int i=1;i<N;i++)
            list[i] = Integer.parseInt(st.nextToken());
        for(int i=0;i<M;i++){
            int k = Integer.parseInt(br.readLine());
            sb.append(getAnswer(list,N,V,k)+"\n");
        }
        System.out.println(sb);
    }
}