[BOJ/백준 - 1744] 수 묶기

문제 출처: https://www.acmicpc.net/problem/1744

1744번: 수 묶기

---

	public class BOJ_TEMP {
	public static void main(String[] args) throws Exception{
	// INPUT & INIT
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	int cnt = Integer.parseInt(br.readLine());
	int[] arr = new int[cnt];
	for(int i=0; i<arr.length; i++) {
	arr[i] = Integer.parseInt(br.readLine());
	}
	Arrays.sort(arr);
	Queue<Integer> minusQ = new LinkedList<>();
	Queue<Integer> zeroQ = new LinkedList<>();
	Queue<Integer> oneQ = new LinkedList<>();
	PriorityQueue<Integer> plusQ = new PriorityQueue<>(Collections.reverseOrder());
	for(int i=0; i<arr.length; i++) {
	int n = arr[i];
	if(arr[i]<0) {
	minusQ.add(n);
	}else if(arr[i]==0) {
	zeroQ.add(n);
	}else if(arr[i]==1) {
	oneQ.add(n);
	}else {
	plusQ.add(n);
	}
	}
	// CALCULATE
	int answer = 0;
	// 곱할 숫자 체크용 배열
	int[] checker = new int[2];
	// 음수체크
	while(!minusQ.isEmpty()) {
	if(checker[0] == 0) {
	checker[0] = minusQ.poll();
	}else {
	checker[1] = minusQ.poll();
	answer += checker[0] * checker[1];
	// 초기화
	checker[0] = 0;
	checker[1] = 0;
	}
	}
	// 음수가 남았는데 0이 없을 경우 : 최대음수값을 더해줌 (0이 있으면 0곱하면서 +0이됨)
	if(checker[0] != 0 && zeroQ.isEmpty()) {
	answer += checker[0];
	checker[0] = 0;
	}
	// 초기화
	checker[0] = 0;
	checker[1] = 0;
	// 양수 체크
	while(!plusQ.isEmpty()) {
	if(checker[0] == 0) {
	checker[0] = plusQ.poll();
	}else {
	checker[1] = plusQ.poll();
	answer += checker[0] * checker[1];
	// 초기화
	checker[0] = 0;
	checker[1] = 0;
	}
	}
	// 양수가 남아있다면 더해줌
	if(checker[0] != 0) {
	answer += checker[0];
	}
	// 나머지 1을 더해줌
	while(!oneQ.isEmpty()) {
	answer += oneQ.poll();
	}
	System.out.println(answer);
	}
	}

view raw BOJ_1744.java hosted with ❤ by GitHub

---

 

숫자를 오름차순으로 정렬한다

 

음수, 0, 1, 양수 부분을 나눠서 큐에 저장한다.

양수부분 큐는 poll을 했을때 제일 큰 값이 올 수 있도록 셋팅해준다

 

음수부분 큐를 하나씩 빼면서 2개 빠질때마다 곱해서 답에 더해준다

음수부분 큐가 비었을 경우 음수 1개가 남아 있다면

0부분 큐를 확인해 0이 존재하면 그냥 넘어가고 0이 존재하지 않으면 나머지 음수1개를 답에 더해준다

 

양수부분 큐를 하나씩 빼면서 2개 빠질때마다 곱해서 답에 더해준다

양수부분 큐가 비었을 경우 양수 1개가 남아 있다면 답에 더해준다

 

1부분 큐를 꺼내면서 답에 더해준다

 

코드에 있는 checker 배열은 숫자가 2개 들어오는지 확인 하고

큐에서 다 제거되었을 때 1개가 남아있는지 확인하는 배열이다