[자바] 백준 Contest 참가

https://www.acmicpc.net/contest/view/952

2023 KSA Automata Winter Contest

 

백준을 이용하면서 처음으로 참가해본 콘테스트

결과는 아주 처참.

 

A번

https://www.acmicpc.net/contest/problem/952/1

A번: 소수가 아닌 수

소수가 아닌 수라고 해서

소수를 판별해서 해야하나

아주 심오하게 풀었는데...

 

소수가 아닌 수 아무거나 출력하면 되는 것이기 때문에

n이 100만 이하라면 그냥 100만을 출력해주면 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class C01 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		long n = Long.parseLong(br.readLine());

		if(n<=1000000000) {
			System.out.println(1000000000);
		}

	}

}

---

https://www.acmicpc.net/contest/problem/952/2

B번: 그래서 대회 이름 뭐로 하죠

B번

여기부터도 나는 좀 막혀서

거의 한시간가량을 풀었다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class C02 {

	public static void main(String[] args) throws IOException {

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

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		String original = br.readLine();
		StringBuffer sb = new StringBuffer();

		if(m<3) {
			System.out.println("NO");
			return;
		}
		
		boolean last_con = false;
		int A_count = 0;
		//boolean flag = false;
		for (int i = original.length() - 1; i >= 0; i--) {
			// 글자 뒤에서부터 출발
			if (last_con == false) {
				if ((original.charAt(i) != 'A') && (original.charAt(i) != 'E') && (original.charAt(i) != 'I')
						&& (original.charAt(i) != 'O') && (original.charAt(i) != 'U')) {
					last_con = true;
					sb.append(original.charAt(i));
				}
				continue;
				// 맨뒷 자음을 찾기전까진 여기만 반복
			}

			// 자음하나 발견 후부터
			if (A_count < 2) {
				if (original.charAt(i) == 'A') {
					A_count++;
					sb.insert(0, 'A');
				}
				continue;
				// A두개를 찾기전까진 여기만 반복
			}

			
			if (i < m - 3 -1) {
				// 글자수 부족
				break;
			} else {
				// 완성
				//flag = true;
				sb.insert(0, original.substring(0, m - 3));
				break;

			}
		}

		if ((A_count>=2 && last_con == true && sb.length()==m)) {
			System.out.println("YES");
			System.out.println(sb);
		} else {
			System.out.println("NO");
		}

	}

}

문자열의 끝에서부터

1. 우선 자음하나를 발견할 때까지 이동해서 해당 자음 하나를 sb에 옮김.

2. 자음을 발견했다면 A가 두개 나올때까지 이동하면서 A두개를 찾아 sb에 옮김.

3. 남은 문자열이 m-3글자 이상이면 필요한만큼 sb에 옮김.

 

좀 너저분하지만 100점 받았다.

---

D번

 

40점 받고 실패.

 

여기서 남은시간 모두 쓰고 처참하게 대회 끝.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class C04 {
	static int n;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());

		if (n == 3) {
			System.out.println("YES");
			System.out.println("1 3 2");
			return;
		} else if (n == 4) {
			System.out.println("YES");
			System.out.println("1 2 4 3");
			return;
		} else if (n == 5) {

			System.out.println("YES");
			System.out.println("1 2 4 3 5");
			return;
		} else if (n == 6) {

			System.out.println("YES");
			System.out.println("1 2 4 3 5 6");
			return;
		} else if (n == 7) {

			System.out.println("YES");
			System.out.println("1 3 2 4 5 7 6");
			return;
		} else if (n == 8) {
			System.out.println("YES");
			System.out.println("1 2 4 3 5 6 8 7");
			return;
		} else if (n == 9) {
			System.out.println("YES");
			System.out.println("1 2 4 3 5 6 8 7 9");
			return;
		} else if (n == 10) {
			System.out.println("YES");
			System.out.println("1 2 4 3 5 6 8 7 9 10");
			return;
		}

		// 위는 7점짜리 n<=10

		if (n % 4 == 0) {
			// 33점짜리. n이 4의 배수일 때
			StringBuffer sb = new StringBuffer();
			for (int i = 0; i < n / 4; i++) {
				sb.append((4 * i + 1) + " " + (4 * i + 2) + " " + (4 * i + 4) + " " + (4 * i + 3) + " ");
			}
			System.out.println("YES");
			System.out.println(sb);
			return;
		}

		/* 진짜시작 */

		backtracking(0, n);
		if (flag == false) {
			stack.clear();
			backtracking2(0, n);
		}

		if (flag == false && flag2 == false) {
			System.out.println("NO");
		}

	}

	static boolean flag = false;
	static boolean flag2 = false;
	static boolean[] visited = new boolean[2000001];
	static Stack<Integer> stack = new Stack<>();

	static void backtracking(int count, int goal) {
		if (count == goal) {
			System.out.println("YES");
			for (int i = 0; i < n; i++) {
				System.out.print(stack.get(i) + " ");
			}
			flag = true;
			return;
		} else {
			int gap = 1 + (count % 2);

			// 더하는경우
			int next = ((stack.isEmpty()) ? 0 : stack.peek());

			// next+gap;
			if (next + gap <= n) {

				if (visited[next + gap] == false) {

					visited[next + gap] = true;
					stack.add(next + gap);
					backtracking(count + 1, goal);

					stack.pop();
					visited[next + gap] = false;

				}

			}

			// next-gap
			if (next - gap >= 0) {

				if (visited[next - gap] == false) {

					visited[next - gap] = true;
					stack.add(next - gap);
					backtracking(count + 1, goal);

					stack.pop();
					visited[next - gap] = false;
				}
			}

		}
	}

	static void backtracking2(int count, int goal) {
		if (count == goal) {

			System.out.println("YES");
			flag2 = true;
			for (int i = 0; i < n; i++) {
				System.out.print(stack.get(i) + " ");
			}
			return;
		} else {
			int gap = 2 - (count % 2);

			// 더하는경우
			int next = ((stack.isEmpty()) ? 0 : stack.peek());

			// next+gap;
			if (next + gap <= n) {

				if (visited[next + gap] == false) {

					visited[next + gap] = true;
					stack.add(next + gap);
					backtracking(count + 1, goal);

					stack.pop();
					visited[next + gap] = false;

				}

			}

			// next-gap
			if (next - gap >= 0) {

				if (visited[next - gap] == false) {

					visited[next - gap] = true;
					stack.add(next - gap);
					backtracking(count + 1, goal);

					stack.pop();
					visited[next - gap] = false;
				}
			}

		}
	}
}

D번을 처음엔 7점,33점짜리 먹으려고 하다가

백트래킹으로 하면 어떨까 싶어서 짜봤는데

스택오버플로우가 나서 실패

(아마 오버플로우가 안났어도 실패했지 않았나 싶다)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class C04 {
	static int n;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());

		if (n == 3) {
			System.out.println("YES");
			System.out.println("1 3 2");
			return;
		} else if (n == 4) {
			System.out.println("YES");
			System.out.println("1 2 4 3");
			return;
		} else if (n == 5) {

			System.out.println("YES");
			System.out.println("1 2 4 3 5");
			return;
		} else if (n == 6) {

			System.out.println("YES");
			System.out.println("1 2 4 3 5 6");
			return;
		} else if (n == 7) {

			System.out.println("YES");
			System.out.println("1 3 2 4 5 7 6");
			return;
		} else if (n == 8) {
			System.out.println("YES");
			System.out.println("1 2 4 3 5 6 8 7");
			return;
		} else if (n == 9) {
			System.out.println("YES");
			System.out.println("1 2 4 3 5 6 8 7 9");
			return;
		} else if (n == 10) {
			System.out.println("YES");
			System.out.println("1 2 4 3 5 6 8 7 9 10");
			return;
		}

		// 위는 7점짜리 n<=10

		if (n % 4 == 0) {
			// 33점짜리. n이 4의 배수일 때
			StringBuffer sb = new StringBuffer();
			for (int i = 0; i < n / 4; i++) {
				sb.append((4 * i + 1) + " " + (4 * i + 2) + " " + (4 * i + 4) + " " + (4 * i + 3) + " ");
			}
			System.out.println("YES");
			System.out.println(sb);
			return;
		}

		/* 진짜시작 */

		boolean[] visited = new boolean[2000001];
		Stack<Integer> stack = new Stack<>();

		int num = 1;
		stack.add(num);
		int count = 1;
		while (count < n) {
			int gap = 1 + (count % 2);

			if (num - gap > 0) {
				if (visited[num - gap] == false) {

					num = num - gap;
					visited[num] = true;
					stack.add(num);
					count++;
					continue;
				}
			}
			if (num + gap <= n) {
				if (visited[num + gap] == false) {
					num = num + gap;
					visited[num] = true;
					stack.add(num);
					count++;
					continue;
				}
			}

			break;
		}

		if (stack.size() == n) {
			System.out.println("YES");
			for (int i = 0; i < stack.size(); i++) {
				System.out.print(stack.get(i) + " ");
			}
			return;
		}

		stack.clear();

		num = 1;
		stack.add(num);
		count = 1;
		while (count < n) {
			int gap = 2 - (count % 2);

			if (num - gap > 0) {
				if (visited[num - gap] == false) {

					num = num - gap;
					visited[num] = true;
					stack.add(num);
					count++;
					continue;
				}
			}
			if (num + gap <= n) {
				if (visited[num + gap] == false) {
					num = num + gap;
					visited[num] = true;
					stack.add(num);
					count++;
					continue;
				}
			}

			break;
		}

		if (stack.size() == n) {
			System.out.println("YES");
			for (int i = 0; i < stack.size(); i++) {
				System.out.print(stack.get(i) + " ");
			}
			return;
		} else {
			System.out.println("NO");
		}

	}

}

왜냐면 반복문으로 비슷하게 풀었는데도 실패했기 때문이다

 

이 한문제에만 두시간넘게 매달렸고 결국 못 풀었다.

 

 

가야할 길이 멀다는걸 느낀다.