[BAEKJOON] 1744번 : 수묶기 (JAVA)

2022. 12. 10. 19:36· Algorithm
반응형

- 알고리즘 분류 : 정렬, 우선순위 큐

- 사용 언어 : JAVA

- 문제 요점

    - 음수가 2개 이상인 경우, 음수끼리 곱해서 양수로 만들 수 있다.

    - 음수가 하나이고, 0이 있는 경우, 음수와 0을 곱해서 0으로 만들 수 있다.

    - 양수가 2개 이상인 경우, 양수끼리 곱해서 더 큰 양수로 만들 수 있다. (단, 1이 2개 인 경우 곱셈보단 더하기가 더 크다.)

 

 

소스 설명은 주석을 참고해주세요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());		// 수열의 길이
		int result = 0;		// 결과값
		
		// 양수를 모아둔 pq : 내림차순 정렬
		Queue<Integer> postive_pq = new PriorityQueue<>((x,y) -> (y-x));
		
		// 음수를 모아둔 pq : 오름차순 정렬
		Queue<Integer> negative_pq = new PriorityQueue<>((x,y) -> (x-y));
		
		// 0을 모아둔 q
		Queue<Integer> zero_q = new LinkedList<Integer>();
		
		for(int i=0; i<N; i++) {
			int num = Integer.parseInt(br.readLine());
			if(num > 0) {
				postive_pq.offer(num);
			}
			else if(num == 0) {
				zero_q.offer(num);
			}
			else {
				negative_pq.offer(num);
			}
		}
		
		/* 고려해야할 점
		 1. 음수가 2개 이상인 경우, 음수끼리 곱해서 양수로 만들 수 있다.
		 2. 음수가 하나이고, 0이 있는 경우, 음수와 0을 곱해서 0으로 만들 수 있다.
		 3. 양수가 2개 이상인 경우, 양수끼리 곱해서 더 큰 양수로 만들 수 있다. 
		 	(단, 1이 2개 인 경우 곱셈보단 더하기가 더 크다.)
		 */
		
		// 세 큐 중 하나의 큐라도 남아있으면 계속 반복
		while( !postive_pq.isEmpty() || !negative_pq.isEmpty() || !zero_q.isEmpty() ) {
			
			// 음수가 2개 이상인 경우, 두 수를 곱해서(양수로 만들어서) result에 넣기
			if(negative_pq.size() >= 2) {
				int num1 = negative_pq.poll();
				int num2 = negative_pq.poll();
				
				result += (num1*num2);
			}
			// 음수가 1개 있고, 0도 있을 때 이 두 수를 곱한다고 가정함
			else if(!zero_q.isEmpty() && !negative_pq.isEmpty()) {
				zero_q.poll();		// 0을 빼주고
				negative_pq.poll();	// 음수도 빼주고 

				// 곱한 결과가 0이므로, result에 굳이 더하진 않음
			
			} else {
				// 양수가 2개 이상인 경우
				if(postive_pq.size() >= 2) {
					int num1 = postive_pq.poll();
					int num2 = postive_pq.poll();
					
					// 일반적으로는 양수는 덧셈보다 두 수를 곱한 값이 더 크지만 
					// 두 수 중에서 하나라도 1이면 덧셈이 더 크다.
					if(num1 == 1 || num2 == 1) 
						result += num1+num2;
					else 
						result += (num1*num2);
				} else {
					// 마무리 단계
					// 남아있는 음수와 양수를 result에 더해준다.
					while(!negative_pq.isEmpty()) {
						result += negative_pq.poll();
					}
					
					while(!postive_pq.isEmpty()) {
						result += postive_pq.poll();
					}
					
					zero_q.clear();		// 0은 굳이 더하지 않고 clear만 해준다. (0은 음수 하나를 0으로 만들 때만 사용됨) 
				}
			}
		}
		
		System.out.println(result);
	}

}
반응형

'Algorithm' 카테고리의 다른 글

[BAEKJOON] 11403번 : 경로 찾기 (JAVA)  (0) 2022.12.17
[BAEKJOON] 11497번 : 통나무 건너뛰기 (JAVA)  (0) 2022.12.11
[BAEKJOON] 1202번 : 보석 도둑 (JAVA)  (0) 2022.12.09
[BAEKJOON] 18111번 : 마인크래프트 (JAVA)  (0) 2022.12.04
[BAEKJOON] 1182번 : 부분수열의 합 (JAVA)  (0) 2022.12.03
'Algorithm' 카테고리의 다른 글
  • [BAEKJOON] 11403번 : 경로 찾기 (JAVA)
  • [BAEKJOON] 11497번 : 통나무 건너뛰기 (JAVA)
  • [BAEKJOON] 1202번 : 보석 도둑 (JAVA)
  • [BAEKJOON] 18111번 : 마인크래프트 (JAVA)
멍목
멍목
개발 관련 새롭게 알게 된 지식이나 좋은 정보들을 메모하는 공간입니다.
반응형
멍목
김멍목의 개발블로그
멍목
전체
오늘
어제
  • 분류 전체보기 (514)
    • BE (190)
      • Spring (21)
      • Java (141)
      • Kotlin (6)
      • JPA (22)
    • FE (33)
      • Javascript (16)
      • Typescript (0)
      • React (5)
      • Vue.js (9)
      • JSP & JSTL (3)
    • DB (32)
      • Oracle (22)
      • MongoDB (10)
    • Algorithm (195)
    • Linux (8)
    • Git (6)
    • etc (42)
    • ---------------------------.. (0)
    • 회계 (4)
      • 전산회계 2급 (4)
    • 잡동사니 (2)

블로그 메뉴

  • 홈
  • 관리

공지사항

인기 글

태그

  • 더 자바 애플리케이션을 테스트하는 다양한 방법
  • JPA 공부
  • 알고리즘 공부
  • 코테 공부
  • MongoDB 기초부터 실무까지
  • 자바 개발자를 위한 코틀린 입문
  • 자바 공부
  • 자기공부
  • 이펙티브 자바
  • 프로젝트로 배우는 Vue.js 3
  • MongoDB with Node.js
  • 이펙티브자바
  • 자바공부
  • java 8
  • 코테공부
  • Java to Kotlin
  • 알고리즘공부
  • MongoDB 공부
  • 코틀린
  • 자기 개발
  • 자기 공부
  • junit5
  • Oracle
  • Effective Java
  • JPA
  • vue3 공부
  • 더 자바 Java 8
  • 전산회계 2급 준비
  • 자바 테스팅 프레임워크
  • 자기개발

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.0
멍목
[BAEKJOON] 1744번 : 수묶기 (JAVA)
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.