๐ŸŒžAlgorithm/๐Ÿ”ฅBaekjoon

[Baekjoon] 18917_์ˆ˜์—ด๊ณผ ์ฟผ๋ฆฌ 38

๋ฟŒ์•ผ._. 2023. 8. 16. 09:55

Silver III

๋ฌธ์ œ(์ถœ์ฒ˜: https://www.acmicpc.net/problem/18917)

< ์ˆ˜์—ด๊ณผ ์ฟผ๋ฆฌ 38 >

 

๋ฌธ์ œ ํ’€์ด 

 

๋ฌธ์ œ์—์„œ ๋ฐฐ์—ด์„ ์‚ฌ์šฉํ•œ๋‹ค๊ณ  ํ•ด์„œ ๋‹น์—ฐํ•˜๊ฒŒ ArrayList๋ฅผ ์‚ฌ์šฉํ•ด์„œ ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ–ˆ์—ˆ๋‹ค.

ํ•˜์ง€๋งŒ ์ตœ๋Œ€ 500000๋ฒˆ์˜ add์™€ remove๋ฅผ ์ˆ˜ํ–‰ํ•˜๋ฉด ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ•œ๋‹ค๋Š” ๊ฒƒ์„ ์•Œ๊ฒŒ ๋˜์—ˆ๋‹ค. 

๋˜ํ•œ, sum๊ณผ xor ์—ฐ์‚ฐ์„ ๊ฐ’์ด ๋“ค์–ด์˜ค๊ณ  ๋‚˜๊ฐˆ ๋•Œ๋งˆ๋‹ค ๊ณ„์‚ฐํ•ด ์ฃผ๋ฉด ๋”ฐ๋กœ ๊ฐ’๋“ค์„ ์ €์žฅํ•  ๊ณต๊ฐ„์ด ํ•„์š” ์—†์—ˆ๋‹ค. 

 

* 1000000000์„ ์ตœ๋Œ€ 500000๋ฒˆ ๋”ํ•œ๋‹ค๊ณ  ํ•˜๋ฉด Integer ๋ฒ”์œ„๋ฅผ ๋ฒ—์–ด๋‚˜๋ฏ€๋กœ long์„ ์จ์•ผ ํ•œ๋‹ค.

 

 ์‹œ๊ฐ„์ดˆ๊ณผ ์ฝ”๋“œ (Java)

๋”๋ณด๊ธฐ

์ฒ˜์Œ์—๋Š” ๊ฐ’์ด ์ œ๊ฑฐ๋  ๋•Œ xor ์—ฐ์‚ฐ์„ ์–ด๋–ป๊ฒŒ ํ•ด์•ผ ํ•˜๋Š”์ง€ ๋ชฐ๋ผ xor ์—ฐ์‚ฐ์„ ์œ„ํ•ด 4๊ฐ€ ์ž…๋ ฅ๋  ๋•Œ๋งˆ๋‹ค ArrayList ์ฒ˜์Œ๋ถ€ํ„ฐ ๋๊นŒ์ง€ ํƒ์ƒ‰ํ•˜๋ฉฐ ์—ฐ์‚ฐ์„ ํ–ˆ์—ˆ๋‹ค. ํ•˜์ง€๋งŒ, ๊ฐ’์„ ์ œ๊ฑฐํ•  ๋•Œ๋„ ๋˜‘๊ฐ™์ด ํ•œ๋ฒˆ ๋” xor ์—ฐ์‚ฐ์„ ํ•˜๋ฉด ๋˜๋Š” ๊ฒƒ์„ ์•Œ๊ณ  ์•„๋ž˜์™€ ๊ฐ™์ด ๊ณ ์ณค์ง€๋งŒ ArrayList์˜ add์™€ remove ์—ฐ์‚ฐ์œผ๋กœ ์ธํ•ด ์‹œ๊ฐ„์ดˆ๊ณผ๊ฐ€ ๋ฐœ์ƒํ–ˆ๋‹ค.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main { // ์ˆ˜์—ด๊ณผ ์ฟผ๋ฆฌ 38

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

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

		ArrayList<Integer> list = new ArrayList<>();

		int sum = 0;
		int xor = 0;

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int num = Integer.parseInt(st.nextToken());

			if (num == 1) {
				int x = Integer.parseInt(st.nextToken());
				sum += x;
				if (xor == 0)
					xor = x;
				else {
					xor=xor^x;
				}
				list.add(x);
			} else if (num == 2) {
				int x = Integer.parseInt(st.nextToken());
				sum -= x;
				xor=xor^x;
				list.remove(Integer.valueOf(x));
			} else if (num == 3) {
				bw.write(sum + "\n");
			} else {
				bw.write(xor + "\n");
			}
		}
		bw.flush();
	}
}

 

 

 my solution (Java)

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

public class _18917_ { // ์ˆ˜์—ด๊ณผ ์ฟผ๋ฆฌ 38

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

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

		long sum = 0;
		long xor = 0;

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int num = Integer.parseInt(st.nextToken());

			if (num == 1) {
				int x = Integer.parseInt(st.nextToken());
				sum += x;
				xor = xor ^ x;
			} else if (num == 2) {
				int x = Integer.parseInt(st.nextToken());
				sum -= x;
				xor = xor ^ x;
			} else if (num == 3) {
				bw.write(sum + "\n");
			} else {
				bw.write(xor + "\n");
			}
		}
		bw.flush();
	}
}

 

Main

๋ณ€์ˆ˜)
m : ์ฟผ๋ฆฌ์˜ ๊ฐœ์ˆ˜
sum : ๋ชจ๋“  ์›์†Œ๋ฅผ ๋”ํ•œ ๊ฐ’
xor : ๋ชจ๋“  ์›์†Œ๋ฅผ xor ํ•œ ๊ฐ’
num : ์ฟผ๋ฆฌ ๊ฐ’

 

- ์ฟผ๋ฆฌ์˜ ๊ฐœ์ˆ˜(m) ์ž…๋ ฅ

- ์ฟผ๋ฆฌ์˜ ๊ฐœ์ˆ˜(m)๋งŒํผ ๋ฐ˜๋ณต

: ์ฟผ๋ฆฌ ๊ฐ’์œผ๋กœ 1์ด ๋“ค์–ด์˜ค๋ฉด x๋ฅผ sum์— ๋”ํ•ด์ฃผ๊ณ  xor์— xor ์—ฐ์‚ฐ(^) ํ•ด์คŒ

: ์ฟผ๋ฆฌ ๊ฐ’์œผ๋กœ 2๊ฐ€ ๋“ค์–ด์˜ค๋ฉด x๋ฅผ sum์—์„œ ๋นผ์ฃผ๊ณ  xor์— xor ์—ฐ์‚ฐ(^) ํ•ด์คŒ

: ์ฟผ๋ฆฌ ๊ฐ’์œผ๋กœ 3์ด ๋“ค์–ด์˜ค๋ฉด sum ์ถœ๋ ฅ

: ์ฟผ๋ฆฌ ๊ฐ’์œผ๋กœ 4๊ฐ€ ๋“ค์–ด์˜ค๋ฉด xor ์ถœ๋ ฅ