๐ŸŒžAlgorithm/๐Ÿ”ฅBaekjoon

[Baekjoon] 10489_Even Up Solitaire

๋ฟŒ์•ผ._. 2025. 8. 21. 10:19
๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/10489)

< Even Up Solitaire >

 

๋ฌธ์ œ ํ’€์ด 

 

stack์„ ์‚ฌ์šฉํ•˜์—ฌ ์ธ์ ‘ํ•˜๋Š” ๋‘ ๊ฐœ์˜ ์นด๋“œ ํ•ฉ์ด ์ง์ˆ˜์ธ์ง€ ํŒ๋‹จํ•œ๋‹ค. ์˜ˆ์ œ๊ฐ€ ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค๋ฉด ๋‹ค์Œ ๊ณผ์ •์„ ๊ฑฐ์นœ๋‹ค.

10
1 3 3 4 2 4 1 3 7 1

 

stack : 1

stack :                     -> (3+1)์€ ์ง์ˆ˜์ด๋ฏ€๋กœ 1 ์ œ๊ฑฐ

stack : 3

stack : 3 4

stack : 3                  -> (4+2)๋Š” ์ง์ˆ˜์ด๋ฏ€๋กœ 4 ์ œ๊ฑฐ

stack : 3 4

stack : 3 4 1

stack : 3 4               -> (1+3)์€ ์ง์ˆ˜์ด๋ฏ€๋กœ 1 ์ œ๊ฑฐ

stack : 3 4 7

stack : 3 4               -> (7+1)์€ ์ง์ˆ˜์ด๋ฏ€๋กœ 7 ์ œ๊ฑฐ

 

my solution (Java)

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

public class _10489_ { // Even Up Solitaire

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int n = Integer.parseInt(bf.readLine());

		st = new StringTokenizer(bf.readLine());

		Stack<Integer> stack = new Stack<>();

		for (int i = 0; i < n; i++) {
			int num = Integer.parseInt(st.nextToken());

			if (stack.isEmpty() || (stack.peek() + num) % 2 == 1) {
				stack.add(num);
			} else {
				stack.pop();
			}
		}
		System.out.println(stack.size());
	}
}
๋ณ€์ˆ˜)
n : ์นด๋“œ ์ˆ˜
stack : Stack <Integer>
num : ์นด๋“œ ๊ฐ’

 

์นด๋“œ ์ˆ˜๋ฅผ ์ž…๋ ฅ๋ฐ›์•„ ์นด๋“œ ์ˆ˜๋งŒํผ ๋‹ค์Œ ๊ณผ์ •์„ ๊ฑฐ์นœ๋‹ค.

 

1) stack์ด ๋น„์–ด์žˆ๊ฑฐ๋‚˜ stack์˜ peek๊ฐ’๊ณผ ์ž…๋ ฅ๋œ ์นด๋“œ ๊ฐ’์˜ ํ•ฉ์ด ํ™€์ˆ˜๋ผ๋ฉด stack์— ์นด๋“œ ๊ฐ’ ์ €์žฅ

2) ํ•ฉ์ด ์ง์ˆ˜๋ผ๋ฉด stack์—์„œ ์ œ๊ฑฐ

 

์ตœ์ข… stack์˜ ํฌ๊ธฐ๋ฅผ ์ถœ๋ ฅํ•œ๋‹ค.