๋ฌธ์ (์ถ์ฒ: 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 ์ถ๋ ฅ
'๐Algorithm > ๐ฅBaekjoon' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Baekjoon] 17616_๋ฑ์ ์ฐพ๊ธฐ (0) | 2023.08.18 |
---|---|
[Baekjoon] 12764_์ธ์ง๋ฐฉ์ ๊ฐ ์คํ (0) | 2023.08.17 |
[Baekjoon] 1379_๊ฐ์์ค 2 (0) | 2023.08.15 |
[Baekjoon] 1374_๊ฐ์์ค (0) | 2023.08.15 |
[Baekjoon] 19598_์ต์ ํ์์ค ๊ฐ์ (0) | 2023.08.14 |