[백준 17827번][Java] 달팽이 리스트 - offset이 있는 모드 연산

www.acmicpc.net/problem/17827

17827번: 달팽이 리스트

 

전체 배열에서 어느 부분만 순환하는 부분 구조를 지니는 부분에서 K번째 요소를 찾으려고 합니다.

순환하는 크기만큼만 나머지 연산을 해주고 순환하지 않는 부분만큼 자리 이동해주면 해당 요소를 찾을 수 있습니다.  

 

자세한 건 코드 주석을 확인하세용

 

팁) 개인적으로 배열에 나머지 연산을 할 때, 처음 인덱스를 1로 하는것보다 0으로 하는게 더 편했습니다.

1로 시작하는 경우 마지막 요소의 나머지가 0이 되는데 이렇게 되면 순서가 1234567890 처럼 0이 맨 뒤로 가게 돼 

따로 처리해줘야 됩니다. 그냥 0으로 시작하는 경우 0123456789 로 나머지가 오름차순으로 정렬되면서 인덱스에 그대로 대응하기 때문에 더 편합니다.

 

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

/*
달팽이 리스트
https://www.acmicpc.net/problem/17827
 */
public class Main {
	static int n,m,v;
	static int[] snailArray;
	public static void main(String[] args) throws IOException {
		InputReader reader = new InputReader();
//		InputReader reader = new InputReader("testcase.txt");
		StringTokenizer st = new StringTokenizer(reader.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		v = Integer.parseInt(st.nextToken());

		snailArray = new int[n];
		st = new StringTokenizer(reader.readLine());
		for (int i = 0; i < n; i++) {
			snailArray[i] = Integer.parseInt(st.nextToken());
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < m; i++) {
			int k = reader.readInt();
			sb.append(getKthValue(k)+"\n");
		}
		sb.deleteCharAt(sb.length()-1);
		System.out.println(sb.toString());
	}
	//k번째 요소를 반환한다.
	private static int getKthValue(int k) {
		//k번째 요소가 n보다 작은 경우 바로 반환
		if(k < n) {
			return snailArray[k];
		}
		//k번째 요소가 n보다 크거나 같은 경우동
		int snailLength = n-v+1; // 순환되는 부분 길이
		k -= v-1; // 순환되지 않은 크기만큼 빼준다.
		return snailArray[k%snailLength + v-1]; //snailLength로 나머지 연산 후 v-1만큼 자리이
	}
}
class InputReader {
	private BufferedReader br;

	public InputReader() {
		br = new BufferedReader(new InputStreamReader(System.in));
	}

	public InputReader(String filepath) {
		try {
			br = new BufferedReader(new FileReader(filepath));
		} catch (FileNotFoundException e) {
			e.printStackTrace();
		}
	}

	public List<Character> readLineIntoCharList() throws IOException {
		List<Character> l = new ArrayList<>();
		while(true) {
			int readVal = br.read();
			if(readVal == '\n' || readVal == -1) break;
			l.add((char)readVal);
		}
		return l;
	}

	public boolean ready() throws IOException {
		return br.ready();
	}

	public String readLine() throws IOException {
		return br.readLine();
	}
	public int readInt() throws IOException {
		return Integer.parseInt(readLine());
	}
	public Long readLong() throws IOException {
		return Long.parseLong(readLine());
	}
}