[백준] 18917번 수열과 쿼리 38 (구현_JAVA)

알고리즘보다 자료구조에 대해 생각해본 문제!

시간이 된다면 자료구조도 정리해 볼 참이다.

 

시작-!

 

---

문제

 

https://www.acmicpc.net/problem/18917

18917번: 수열과 쿼리 38

 

 

---

설계

 

알고리즘 설계 [접근방법] : 구현

정수를 입력받아 추가하고 제거하는 것을 ArrayList()로 설계했다. 하지만 remove를 하는 과정에서 시간복잡도가 O(n)이 걸려 LinkedList()로 변경했다. 하지만 그럼에도 시간초과가 발생했다.

생각해보면, 값이 추가될 때마다 덧셈을 하고, 제거될 때 뺄셈을 하면 값을 저장할 자료구조는 사용하지 않아도 된다.

그래서 값이 추가될 때마다 변수 sum에 값을 더하고 xor 변수에 xor비트연산을 했다. 그 후 값이 제거되어야 할 때는 sum에서 값을 빼주고, 또다시 xor을 했다.

 

풀이 과정

 1.

쿼리의 개수 n을 입력받는다.

 

2.

값의 합인 sum과 비트연산 xor을 할 변수 xor를 초기화한다.

그후 값을 저장할 StringBuilder도 생성한다.

 

3.

쿼리 타입을 입력받고, 1이면 sum에 값을 더하고 xor에 xor연산을 해준다.

쿼리 타입이 2라면, sum에서 값을 빼고, xor와 값을 xor연산을 해준다. 이미 값이 xor와 값과 연산이 되어 있으므로 똑같은 값을 다시 연산해서 그 값의 비트를 0으로 만드는 방법이다.

쿼리 타입이 3이면, sum의 값을 StringBuilder에 저장하고, 쿼리 타입이 4면 xor값을 StringBuilder에 저장한다.

 

4.

모든 쿼리의 명령이 종료되면 StringBuidler에 저장되었던 값을 출력한다.

 

 

---

코드

 

import java.util.*;

public class Test_18917_수열과쿼리38 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		
		long sum = 0;
		long xor = 0;
		
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<n; i++) {
			int type = sc.nextInt();
			
			if(type==1) {
				long num = sc.nextLong();
				
				sum+=num;
				xor = xor^num;
			}
			
			else if(type==2) {
				long num = sc.nextLong();
				
				sum-=num;
				xor = xor^num;
			}
			
			else if(type==3) {
				sb.append(sum+"\n");
			}
			
			else if(type==4) {
				sb.append(xor+"\n");
			}
		}
		
		//출력
		System.out.println(sb.toString());
	}
}

 

 

(❁´◡`❁)

끝!