[킥스타트] 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번 문제에 도전해 보아야 할 것 같다.