[킥스타트] Google Kick Start 2020 Round B 문제 풀이

킥스타트 2020 라운드 B 문제 풀이를 해 보도록 한다. 내년 2021 킥스타트나 코드잼을 준비하시는 분들, 또는 알고리즘 공부를 하시는 분들에게 많은 도움이 되길 바란다.

 

1. Bike Tour

기초적인 탐색 문제이다. 전체 체크포인트 N개를 배열에 저장한 후 처음부터 끝까지 탐색하며 peak가 몇 개인지 파악하면 된다. 시간복잡도는 O(N).

import java.io.*;
import java.util.*;

public class KickStart_2020B_1 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int T = Integer.parseInt(st.nextToken());
		for (int i = 1; i <= T; i++) {
			int N = Integer.parseInt(br.readLine());
			st = new StringTokenizer(br.readLine());
			int[] arr = new int[N];
			int cnt = 0;
			for (int j = 0; j < N; j++) {
				arr[j] = Integer.parseInt(st.nextToken());
			}
			for (int j = 1; j < N - 1; j++) {
				if (arr[j - 1] < arr[j] && arr[j] > arr[j + 1]) cnt++;
			}
			System.out.println("Case #" + i + ": " + cnt);
		}
	}
}

 

2. Bus Routes

문제를 이해하는 데 조금 시간이 걸렸던 것 같다. N개 버스의 배차일이 각각 주어지고 D일까지 여정을 마무리 해야 하는데 첫 번째 예제가 N=3, D=10, X = [3, 7, 2] 인데 왜 답이 7이 아니고 6인지 이해하는 데 조금 어려움을 겪었다. 아래 그림을 통해서 설명을 하면 배차 간격 순서대로 버스를 타야 하는데, 하루에 탈 수 있는 버스의 수는 제한이 없다. 이 예제에서는 두 번째 버스가 7일째에만 오기 때문에(여정을 10일 안에 끝내야 하므로) 첫 번째 버스는 7일 또는 그 이전에 타야 하고, 세 번째 버스는 7일 또는 그 이후에 타야 한다. 그래서 첫 번째 버스를 6일에 타게 되고 답이 6인 것이다.

그냥 전체 버스가 언제언제 탈 수 있는지를 찾아서 탐색하면 O(N*D)로 풀 수 있지만 그렇게 풀면 두 번째 케이스는 통과할 수 없다. 따라서 약간 수학적인 방법을 사용했다. 마지막 버스부터 언제 가장 늦게 탈 수 있는지를 찾고 그 이전 버스는 그와 같거나 이른 날짜로 범위를 좁혀서 찾는 식으로 말이다. 예를 들면 이런 식이다.

이렇게 문제를 풀면 시간복잡도 O(N)으로 풀 수가 있다. 소스코드는 아래처럼 짤 수가 있다.

import java.io.*;
import java.util.*;

public class KickStart_2020B_2 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int T = Integer.parseInt(st.nextToken());
		for (int i = 1; i <= T; i++) {
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			long D = Long.parseLong(st.nextToken());
			long arr[] = new long[N];
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < N; j++) {
				arr[j] = Long.parseLong(st.nextToken());
			}
			for (int j = N - 1; j >= 0; j--) {
				D = (D / arr[j]) * arr[j];
			}
			System.out.println("Case #" + i + ": " + D);
		}
	}
}

 

3. Robot Path Decoding

일반적으로 괄호가 있는 문자열 문제는 Stack 자료구조로 해결이 되는 경우가 많다. 이 문제에서도 스택을 사용했고 두 개의 스택을 사용해서 하나는 괄호 앞에 곱해주는 숫자들을 넣는 스택, 다른 하나는 해당 괄호 안에서 점이 얼마나 이동하는지를 나타내는 스택으로 나누어서 처리해 주었다.

"3(N2(SE))W"라는 예제를 가지고 설명 해 보려고 한다. 먼저 숫자인 경우는 숫자 스택에 넣어준다.

N,W,S,E의 문자인 경우는 각각 좌표에 맞게 x,y 좌표값을 계산하여 Pair 스택에 넣어준다.

이러한 작업을 반복한다.

닫는 괄호가 나오면 그 때는 숫자 스택과 Pair 스택에서 하나씩 pop을 해서 곱해준 후 기존에 위치에 더해준다.

이렇게 두 개의 스택을 가지고 좌표를 구할 수 있다.

문자열의 길이를 N이라고 했을 때 시간복잡도는 O(N)이다. 문제에서 주어진 조건에 만족하기에는 충분하다.

import java.util.*;
import java.io.*;

public class KickStart_2020B_3 {

	public static final long M = 1000000000;

	public static void main(String[] args) {
		Scanner s = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
		int t = s.nextInt();
		for (int ti = 1; ti <= t; ti++) {
			String str = s.next();
			Stack<Pair> dis = new Stack<>();
			Stack<Integer> fact = new Stack<>();
			Pair d = new Pair(0, 0);
			int f = 1;
			for (int i = 0; i < str.length(); i++) {
				if (str.charAt(i) >= '1' && str.charAt(i) <= '9') {
					dis.push(d);
					fact.push(f);

					f = str.charAt(i) - '0';
					d = new Pair(0, 0);
					i++;
				} else if (str.charAt(i) == ')') {
					d.col = (d.col * f) % M;
					d.row = (d.row * f) % M;
					Pair dtillnow = dis.pop();
					dtillnow.col = (dtillnow.col + d.col) % M;
					dtillnow.row = (dtillnow.row + d.row) % M;

					d = dtillnow;
					f = fact.pop();
				} else {
					char cc = str.charAt(i);
					if (cc == 'N') {
						d.col--;
					} else if (cc == 'S') {
						d.col++;
					} else if (cc == 'E') {
						d.row++;
					} else {
						d.row--;
					}

					d.col %= M;
					d.row %= M;
				}
			}

			d.col += 1;
			d.row += 1;

			if (d.col <= 0) {
				d.col = M + d.col;
			}
			if (d.row <= 0) {
				d.row = M + d.row;
			}

			System.out.println("Case #" + ti + ": " + d.row + " " + d.col);
		}
	}

	static class Pair implements Comparable<Pair> {
		long col;
		long row;

		Pair(long col, long row) {
			this.col = col;
			this.row = row;
		}

		public int compareTo(Pair other) {
			if (this.col < other.col)
				return -1;
			else
				return 1;
		}
	}
}

 

4. Wandering Robot

이 문제는 못 풀었다 ㅠㅠㅠ

 

아직 갈 길이 먼 것 같다. 일단은 제한 시간 내에 3번 문제까지는 AC를 무리없이 하는 걸 목표로 잡고 그 다음 4번 문제에 도전해 보아야 할 것 같다.