달팽이 리스트 (백준 17827번) [JAVA]

문제는 결과 표에 링크 있습니다.

 

문제

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	256 MB	586	212	169	40.334%

영진이는 달팽이를 좋아한다. 달팽이를 너무너무 좋아하기 때문에 특정한 모양의 단방향 연결리스트에 달팽이 리스트라는 이름을 붙여주었다.

일반적인 선형 단방향 연결리스트의 각 노드 번호를 연결된 순서대로 1, 2, ..., N이라 하자. 이때 N번 노드는 아무 노드도 가리키지 않는데, 여기서 N번 노드가 1번 노드를 제외한 임의의 노드를 가리켜 사이클을 이루게 되는 리스트를 달팽이 리스트라고 한다. 달팽이 리스트는 각 노드당 하나의 정수를 저장한다.

즉, 달팽이 리스트는 다음과 같이 생긴 연결리스트이다. 노드 안의 수는 저장된 값을 뜻한다.

"달팽아 달팽아 1번 노드부터 한 칸씩 총 K번 이동해 도착한 노드엔 어떤 값이 있을까?"
영진이는 어두운 방 안에서 달팽이 리스트 하나를 쓱쓱 그리더니, 같은 말을 K만 바꿔가며 계속 중얼거렸다.
영진이의 상태가 심상치 않아 보인다... 상황이 더 악화되기 전에 영진이의 모든 질문에 대답해주도록 하자.

입력

첫째 줄에 노드의 개수 N(2 ≤ N ≤ 200,000), 질문의 횟수 M(1 ≤ M ≤ 200,000), N번 노드가 가리키는 노드의 번호 V(2 ≤ V ≤ N)가 공백으로 구분되어 주어진다.
둘째 줄에 N개의 정수 C1, C2, …, CN이 공백으로 구분되어 주어진다. 이때 *Ci는 i번 노드에 저장된 값을 뜻한다. (1 ≤ *Ci ≤ 1,000,000)
셋째 줄부터 M개의 줄에 걸쳐 각 질문에 해당하는 K(1 ≤ K ≤ 109)가 주어진다.

출력

M개의 줄에 걸쳐 각 질문의 답을 출력한다.

 

풀이

n을 넘어서면 q마다 새로 도는 루프이므로 그에 맞게 계산해서 호출해준다.

 

코드

import java.io.IOException;

public class Main {
	public static StringBuilder sb = new StringBuilder();
	public static java.io.BufferedReader br = new java.io.BufferedReader(new java.io.InputStreamReader(System.in));
	public static void main(String[] args) throws IOException {
		String s = br.readLine().trim();
		String str1[] = s.split(" ");	
		int n = Integer.parseInt(str1[0]);
		int m = Integer.parseInt(str1[1]);
		int v = Integer.parseInt(str1[2]);
		
		s = br.readLine().trim();
		str1 = s.split(" ");
		
		for(int i = 0; i < m; i++) {
			int q = Integer.parseInt(br.readLine().trim());
			sb.append(str1[check(n,q,v)]).append("\n");
		}
		
		System.out.println(sb.toString());
	}
	
	public static int check(int n, int q, int v) {
		int num = 0;
        //n보다 작으면 그대로 그 번호애
		if(q < n) {
			return q;
		}
        //n이면 계속 맨 끝에 애
		if(v == n) {
			return n-1;
		}
		//v-1 하는이유 : 배열에서 호출하는거라 1 빼줌.
		num = (q-n)%(n-v+1) + v-1;
		return num;
	}
}

 

결과

아이디	문제 번호	결과	메모리	시간	언어	코드 길이	제출 시간
howtolivelikehuman	17827	맞았습니다!!	64960KB	500ms	Java	875B	3달 전