백준 1744. 수 묶기

🅰 백준 1744. 수 묶기

1744번: 수 묶기

 

✏️ 문제 풀이

• 두 수를 묶기위한 조건으로는 음수일때는 (큰수,큰수)를 묶어서 서로 곱해주고, 0이 있으면 곱해주고, 양수일때는 (큰수,큰수) 묶어서 서로 곱해주고 1은 곱하지 않는게 좋으므로 1이 있다면 따로 개수를 count해서 더해준다.
• 데이터를 음수와 0, 양수로 따로 나눠서 list에 저장하였다.
• 음수일때는 오름차순, 양수일때는 내림차순으로 정렬하였다.
• 음수와 양수일때 반복문을 따로 구성해주었고 데이터를 2개씩 묶어서 다루기 때문에 i+=2를 해주었다.
• 양수는 내림차순으로 되어있어 1이 제일 마지막에 있기 때문에 (list.size() - 1을 count한 개수) 만큼 반복문을 수행하고 최종 sum에 1의 개수만큼 더해주었다.

✏️ 소스코드

package greedy;

import java.util.*;
import java.io.*;
/*
 * 수 묶기 문제
 * 음수와 양수 따로 나눠서 들어오는 데이터 만큼 생성하기 위해 LinkedList 사용
 * 음수는 오름차순 정렬로 큰수*큰수, 0이 있으면 곱해줌
 * 양수는 내림차순 정렬로 큰수*큰수, 1은 곱하지 않는게 좋으므로 1을 count해서 따로 더해줌*/

public class Main_골드4_1744_손은성 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		List<Integer> negNum = new LinkedList<>();
		List<Integer> posNum = new LinkedList<>();

		int sum = 0;
		int oneCnt = 0;
		for (int i = 0; i < n; i++) {
			int data = Integer.parseInt(br.readLine());
			if (data <= 0) {
				negNum.add(data);
				// nCnt++;
			} else {
				if (data == 1)
					oneCnt++;
				posNum.add(data);
				// pCnt++;
			}
		}

//		리스트 오름차순, 내림차순 정렬
		Collections.sort(negNum);
		Collections.sort(posNum, Comparator.reverseOrder());

//		음수일 때
		for (int i = 0; i < negNum.size(); i += 2) {
			if (negNum.size() - i > 1) { // 남아있는 데이터가 2개 이상일 때
				sum += negNum.get(i) * negNum.get(i + 1);
			} else { // 남아있는 데이터가 1개일 때
				sum += negNum.get(i);
			}
		}

//		양수일 때
		for (int i = 0, end = posNum.size() - oneCnt; i < end; i+=2) {
			if (end - i > 1) { // 남아있는 데이터가 2개 이상일 때
				sum += posNum.get(i) * posNum.get(i + 1);
			} else { // 남아있는 데이터가 1개일 때
				sum += posNum.get(i);
			}
		}
		sum += oneCnt;
		System.out.println(sum);
	}
}

 

✅ 후기

• 골드문제라 그런지 복잡했지만 그리디 방식으로 규칙을 생각하고 정리해서 풀었을 때 원하는 답이 나올 수 있었다.