Codeforces Round #624 (Div. 3)

Codeforces Round #624 (Div. 3)

처음으로 코드포스에 참가해봤는데 Division 3라서 그런지 문제도 나름 풀만했다. 두 문제 풀어놓고 풀만했다고 하면 좀 웃기지만... 엄청 어려운 문제만 나올거라고 생각했던지라 그보단 덜 했다는 뜻이다.

A. Add Odd or Subtract Even
이 문제는 BFS로 완전탐색이 아닐까? 하고 바로 접근했다가 정말 단순한 구현 문제라는 것을 조금 늦게 깨달았다. 굉장히 다양한 경우가 나올거라고 생각했지만 다시 한번 생각해보니 홀수는 더하고 짝수는 빼는 연산을 했을 때 정수 A에서 정수 B에 도달하기까지 최고 수행횟수는 2회가 된다. 따라서 한번에 갈 수 있느냐 아니면 더하고 빼거나 빼고 더하느냐의 문제였다.

import java.util.Scanner;
 
public class Solution {
 
	static int T, start, end;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		T = sc.nextInt();
		
		for(int i = 0 ; i < T ; ++i) {
			start = sc.nextInt();
			end = sc.nextInt();
			
			int move = 0;
			int gap = 0;
			if(start == end) {
				System.out.println(move);
				continue;
			} else if(start > end) {
				gap = start - end;
				
				if(gap % 2 == 0) {
					move++;
				} else {
					move += 2;
				}
			} else {
				gap = end - start;
				
				if(gap % 2 == 0) {
					move += 2;
				} else {
					move++;
				}
			}
			
			System.out.println(move);
		}
	}
}

B. WeirdSort
이상한 정렬이라고해서 잔뜩 겁을 먹고 문제를 읽기 시작했는데 읽다보니 그냥 버블정렬이였다. 따라서 주어진 배열과 인덱스들을 통해서 버블정렬이 가능한지 불가능한지를 판단하면 되는 문제였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.StringTokenizer;
 
public class Solution {
 
	static HashSet<Integer> P;
	static int[] A;
	static int T, N, M;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		T = stoi(br.readLine());
		
		for(int t = 0 ; t < T ; ++t) {
			st = new StringTokenizer(br.readLine());
			
			N = stoi(st.nextToken());
			M = stoi(st.nextToken());
			
			A = new int[N + 1];
			P = new HashSet<>();
			
			st = new StringTokenizer(br.readLine());
			for(int i = 1 ; i <= N ; ++i) {
				A[i] = stoi(st.nextToken());
			}
			
			st = new StringTokenizer(br.readLine());
			for(int i = 0 ; i < M ; ++i) {
				P.add(stoi(st.nextToken()));
			}
			
			if(bubbleSort()) {
				System.out.println("YES");
			} else {
				System.out.println("NO");
			}
		}
	}
	
	private static boolean bubbleSort() {
		for(int i = 1 ; i < N ; ++i) {
			for(int j = 1 ; j < N ; ++j) {
				if(A[j] > A[j + 1]) {
					if(!P.contains(j)) return false;
					swap(j, j + 1);
				}
			}
		}
		
		return true;
	}
 
	private static void swap(int i, int j) {
		int temp = A[i];
		A[i] = A[j];
		A[j] = temp;
	}
 
	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}

C. Perform the Combo
단순히 카운팅하면 되는거 아냐!? 라고 접근했지만 시간초과를 받게되었고 계속 수정했지만 결국엔 시간 내에 통과하지 못했다. 근데 야속하게도 컨테스트가 끝나니까 바로 풀이법이 생각났다. 바로 카운팅을 위해 2중 반복문을 돌던 것을 콤보의 끝에서부터 시작하여 횟수를 중첩시켜오면서 갱신하면 되는 문제였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
	
	static char[] combo;
	static int[] alphabet, count, mistake;
	static int T, N, M;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		StringBuilder sb = new StringBuilder();
		
		T = stoi(br.readLine());
		for(int t = 0 ; t < T ; ++t) {
			st = new StringTokenizer(br.readLine());
			N = stoi(st.nextToken());
			M = stoi(st.nextToken());
			
			mistake = new int[N];
			count = new int[N];
			alphabet = new int[26];
			combo = br.readLine().toCharArray();
			
			st = new StringTokenizer(br.readLine());
			for(int i = 0 ; i < M ; ++i) {
				mistake[stoi(st.nextToken())]++;
			}
 
			int cnt = 1;
			for(int i = N - 1 ; i >= 0 ; --i) {
				count[i] = cnt;
				cnt += mistake[i];
			}
			
			for(int i = 0 ; i < N ; ++i) {
				alphabet[combo[i] - 'a'] += count[i];
			}
			
			for(int i = 0 ; i < 26 ; ++i) {
				sb.append(alphabet[i] + " ");
			}
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}
	
	private static int stoi(String s) {
		return Integer.parseInt(s);
	}
}

첫 컨테스트를 2문제 밖에 못 풀며 아쉽게 마무리했지만 그래도 처음 코드포스 컨테스트를 경험해보니 재밌었다. 다음에는 좀 더 많이 풀어봐야겠다. 나머지 문제는 풀 문제들이 많아서 패스!

---

만세 첫 시도에 민트면 대박아니겠는가?