[자바] 1744 수 묶기

자바 / 골4 / 그리디 알고리즘

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

으악!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 

맨 마지막에 답 출력하는 부분을

        System.out.println(sum);

을 tab 자동완성으로 쓰다가

        System.err.println(sum);

로 써버려서

런타임 에러가 나는데 백준에서 제공하는 어떤 런타임 에러인지 나오는 기능도 안먹히고 

내가 짠 코드에서 런타임 에러가 날 만한 부분은 인덱스에서 밖에 없는데 하면서 인덱스 부분을 한시간 넘게 들여다 보고 고민하다가.. 결국 지피티한테 코드 붙여넣기 하고 어디서 런타임 에러가 났을까? 하고 물어봤더니 그제서야......

그런...

문제였다...

 

그래도 교훈을 얻었으니... (다음부터는 런타임 에러가 난다면 System.out.println부분을 잘 작성하였는지 보도록 한다)

왜 vscode에서는 제대로 잘 돌아가는거야 ㅜㅜ 절대 못찾게..

 

내가 푼 알고리즘을 소개 하겠다...

하나의 배열에 입력 받는 모든 수를 저장하고, 내림차순으로 정렬한 후

        int i = 0;
        while (i < N && arr[i] > 0) {
            if (i + 1 < N && arr[i + 1] > 0){
                if (arr[i] == 1 || arr[i + 1] == 1) {
                    sum += arr[i];
                    sum += arr[i + 1];
                }
                else {
                    sum += arr[i] * arr[i + 1];
                }
                i += 2;
            }
            else {
                sum += arr[i];
                i++;
            }
        }

양수 부분의 절대값이 큰 부분부터 검사해주었다. 

현재 값이 양수인 조건 하에서 반복문을 돌리고, 다음 값도 양수라면 두 수를 곱해서 더해준다.

만약 두 수 중에 1인 값이 하나라도 있다면, 1은 곱해서 더하는 것 보다 단독으로 더해주는 것이 더 큰 수를 갖게 되므로, 두 값을 각기 더해준다.

만약 현재 값은 양수인데 다음 값은 아니라면, 현재 값만 더해주고 반복문이 종료되도록 해 준다.

 

다음으로는 음수 부분의 절대값이 큰 부분부터(즉, 배열의 뒤에서부터) 검사해주었다.

음수인 수가 홀수 개라면, 가장 절대값이 작은 녀석을 더해 주는 것이 총 합이 커지는 방법이기 때문이다.

        int j = N - 1;
        while (j >= 0 && arr[j] <= 0) {
            if (j - 1 >= 0 && arr[j - 1] <= 0) {
                sum += arr[j] * arr[j - 1];
                j -= 2;
            }
            else {
                sum += arr[j];
                j--;
            }
        }

 

그리디 알고리즘이 사용된 부분은, 현재 값과 다음 값이 부호가 같다면 각기 더해주는 것이 아닌 곱해서 더해주는 것을 선택한다는 부분이다.

 

다음은 전체 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collections;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N, sum = 0;
        Integer [] arr;

        N = Integer.parseInt(br.readLine());
        
        arr = new Integer[N];

        for(int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr, Collections.reverseOrder());

        int i = 0;
        while (i < N && arr[i] > 0) {
            if (i + 1 < N && arr[i + 1] > 0){
                if (arr[i] == 1 || arr[i + 1] == 1) {
                    sum += arr[i];
                    sum += arr[i + 1];
                }
                else {
                    sum += arr[i] * arr[i + 1];
                }
                i += 2;
            }
            else {
                sum += arr[i];
                i++;
            }
        }

        int j = N - 1;
        while (j >= 0 && arr[j] <= 0) {
            if (j - 1 >= 0 && arr[j - 1] <= 0) {
                sum += arr[j] * arr[j - 1];
                j -= 2;
            }
            else {
                sum += arr[j];
                j--;
            }
        }

        System.out.println(sum);
    }
}