mingssssss

1. 문제

https://www.acmicpc.net/submit/11060/43023128

2. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

	static ArrayList<Integer> list;
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int N = Integer.parseInt(st.nextToken());
		visited = new boolean[N];
		list = new ArrayList<Integer>();

		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			list.add(Integer.parseInt(st.nextToken()));
		}
		// 입력 종료
        
        // N == 1일 경우, 어떤 숫자가 있어도 도착이므로 0 출력
		if (N == 1) {
			System.out.println(0);
		} else {
			Queue<Integer> q = new LinkedList<Integer>();

			q.add(0);
			visited[0] = true;

			int cnt = 0;
			while (!q.isEmpty()) {

				int size = q.size();

				for (int k = 0; k < size; k++) {

					int v = q.poll();
					for (int i = 0; i <= list.get(v); i++) {

						if (v + i >= list.size() - 1) {
							if (list.get(v) == 0) {
								System.out.println(-1);
								return;
							}
							System.out.println(cnt + 1);
							return;
						}

						if (visited[v + i] == false) {
							visited[v + i] = true;
							q.add(v + i);
						}
					}
				}
				cnt++;

			}

			System.out.println(-1);

//		// 출력
//		for (int i = 0; i < N; i++) {
//			System.out.printf("%d ", list.get(i));
//		}

		}
	}
}

3. 리뷰

첫 번째 칸부터 시작해서 해당 칸에 있는 숫자만큼 오른쪽으로 점프해서

가장 끝의 칸에 도달하거나 넘어가는 최솟값을 출력하는 문제이다.

큐에 시작좌표를 넣고 해당 칸에 있는 숫자만큼 오른쪽으로 이동했다.

구현이 생각보다 쉬워서 제출했는데, 100%에서 실패가 떴다.

edge 케이스에서 문제가 생기는 것 같아 고민해보니

N이 1일 경우에는 칸의 숫자와 상관없이 무조건 도착이니

0을 출력해야 했다.

다른 사람들이 제출한 코드의 메모리와 시간을 보니 내가 제출한 것보다 절반밖에 안 됐다.

코드를 분석해보니 while문 안에 for문이 문제였다.

현재 작성한 코드 스타일이 익숙해서 굳이 바꾸지는 않겠지만..

나중에 메모리나 시간측면에서 문제가 발생하면 그때 바꿔봐야 겠다.