백준(Java)/23년 9월

[Java] 백준 - 1744번: 수 묶기

C0MPAS 2023. 9. 13. 13:18

9월 13일(수) - 그리디 알고리즘 (1744번)

 

1744번: 수 묶기

길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에

www.acmicpc.net

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 1

(풀이출처 -> https://rays-space.tistory.com/55)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

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());
        List<Integer> positive = new ArrayList<>();
        List<Integer> negative = new ArrayList<>();
        int[] zero_one = new int[2];

        for(int i=0; i<N; i++)
        {
            int x = Integer.parseInt(br.readLine());

            if(x > 1)
            {
                positive.add(x);
            }
            else if(x < 0)
            {
                negative.add(x);
            }
            else
            {
                zero_one[x]++;
            }
        }

        Collections.sort(positive, Collections.reverseOrder());
        Collections.sort(negative);
        long sum = 0;

        if(positive.size() > 1)
        {
            for(int i=0; i< positive.size()-1; i+=2)
            {
                sum = sum + ( positive.get(i) * positive.get(i+1) );
            }
        }
        if(positive.size() % 2 == 1)
        {
            sum = sum + positive.get(positive.size() - 1);
        }

        if(negative.size() > 1)
        {
            for(int i=0; i< negative.size()-1; i+=2)
            {
                sum = sum + ( negative.get(i) * negative.get(i+1));
            }
        }
        if(negative.size() % 2 == 1 && zero_one[0] == 0)
        {
            sum = sum + negative.get(negative.size() - 1);
        }

        sum = sum + zero_one[1];

        System.out.println(sum);
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이 - 2

(풀이출처 -> https://lotuslee.tistory.com/70)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

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());
        List<Integer> positive = new ArrayList<>();
        List<Integer> negative = new ArrayList<>();

        for(int i=0; i<N; i++)
        {
            int x = Integer.parseInt(br.readLine());

            if(x > 0)
            {
                positive.add(x);
            }
            else
            {
                negative.add(x);
            }
        }

        Collections.sort(positive, Collections.reverseOrder());
        Collections.sort(negative);

        int sum = 0;
        int i = 0;
        while (i < positive.size())
        {
            if(i+1 < positive.size() && positive.get(i) != 1 && positive.get(i+1) != 1)
            {
                sum = sum + ( positive.get(i++) * positive.get(i++) );
            }
            else
            {
                sum = sum + positive.get(i++);
            }
        }

        i = 0;
        while (i < negative.size())
        {
            if(i+1 < negative.size() && negative.get(i) != 1 && negative.get(i+1) != 1)
            {
                sum = sum + (negative.get(i++) * negative.get(i++));
            }
            else
            {
                sum = sum + negative.get(i++);
            }
        }

        System.out.println(sum);
    }
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

저작자표시 (새창열림)