[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1461번, 도서관

문제 링크

1461번: 도서관

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 세준이의 초기위치는 0입니다.

2. 세준이는 한 번에 M개를 들 수 있으며, 좌우로 한 걸음에 1씩 이동이 가능합니다.

3. 책을 모두 제자리에 놔둔 후 0으로 돌아올 필요가 없습니다.

4. 책을 모두 제자리에 놔두는 최소 이동 횟수를 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 책의 위치를 양수, 음수별로 나누고 정렬한 뒤, 책을 제자리에 놓는 과정을 진행합니다.

 

3. 모든 책을 제자리에 놓은 후 이동한 거리를 결과로 출력합니다.

 

 

책 제자리에 놓기.

 

세준이는 M개에 책을 놓고 온 뒤에 제자리에 돌아와야합니다.

 

0에서 가장 멀리있는 위치에 있는 책을 맨 마지막에 놓아야합니다.

 

제자리에서 양수, 음수 방향 각각 작은 위치부터 책을 놓습니다.

 

가장 큰 값이 음수일 때

 

음수의 가장 큰 값에 도착했을 때 되돌아갈 필요가 없습니다.

 

가장 큰 값이 양수일 때

 

양수의 가장 큰 값에 도착했을 때 되돌아갈 필요가 없습니다.

 

예를 들어

 

M = 3

 

-1 2 3 7 -2

 

음수

 

-1 -2

 

양수

 

2 3 7

 

가장 큰 값 : 7(양수)

 

※가장 큰 값이 양수이기 때문에 음수부터 놓은 뒤 양수를 놓았습니다.

 

-1 ▶ -2 ▶ 0 = 4회 이동

 

2 ▶ 3 ▶ 7 = 7회 이동

 

총 11회 이동

 

 

예제입력 3.

 

1. 입력된 정보를 저장합니다.

 

N = 6

 

M = 2

 

책의 위치

	책 1	책 2	책 3	책 4	책 5	책 6
위치	3	4	5	6	11	-1

 

2. 책의 위치를 양수, 음수별로 나누고 정렬한 뒤, 책을 제자리에 놓는 과정을 진행합니다.

 

양수 정렬

	책 1	책 2	책 3	책 4	책 5
위치	3	4	5	6	11

 

음수 정렬

	책 6
위치	-1

가장 큰 값 : 11 (양수)

 

음수부터 제자리에 놓기 진행!

 

-1 (책6) ▶ 0 (초기 위치)

 

이동 횟수 : 2

 

양수 제자리에 놓기 진행

※M이 2이기 때문에 2개의 책을 순서대로 제자리에 놓을 수 있습니다.

 

3 (책 1) ▶ 0 (초기 위치)

 

이동 횟수 : 6

 

4 (책 2) ▶ 5 (책 1) ▶ 0 (초기 위치)

 

이동 횟수 : 10

 

 ▶ 6 (책 2) ▶11 (책 5)  ▶ 완료!

 

이동 횟수 : 11

 

 

3. 모든 책을 제자리에 놓은 후 이동한 거리를 결과로 출력합니다.

 

음수 위치 이동한 횟수 : 2

 

양수 위치 이동한 횟수 : 6 + 10 + 11 = 27

이동한 횟수 29(2 + 27)를 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 입력되는 정보를 띄어쓰기 기준 나누었습니다.
• 책을 양수와 음수로 나눈 뒤, Collections.sort를 이용하여 정렬하였습니다.
• 최대값에 따라 양수와 음수 위치에 책들을 제자리에 놓습니다.
• 이동한 횟수를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• plusSearch함수는 양수의 위치인 책들을 제자리에 놓는 과정을 진행하는 함수입니다.
• minusSearch함수는 음수의 위치인 책들을 제자리에 놓는 과정을 진행하는 함수입니다.

 

import java.io.*;
import java.util.*;

public class Main{
    static ArrayList<Integer> plus = new ArrayList<>();	//양수 저장 리스트
    static ArrayList<Integer> minus = new ArrayList<>();	//음수 저장 리스트
    static int N, M;
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine()," ");
        int max = -1;
        boolean check = false;
        //각 책의 위치 저장
        for(int i=0;i<N;i++){
            int n = Integer.parseInt(st.nextToken());
            //책의 위치 최대값 구하기
            if(Math.abs(n) > max){
                max = Math.abs(n);
                check = n > 0;
            }
            //양수, 음수별 나눠서 저장하기
            if(n>0)
                plus.add(n);
            else
                minus.add(n);
        }
        Collections.sort(plus);	//오름차순 정렬
        Collections.sort(minus, Collections.reverseOrder());	//내림차순 정렬
        int answer = 0;
        //양수가 최대값일 때
        if(check){
            answer += minusSearch(false);	//음수 탐색
            answer += plusSearch(true);	//양수 탐색
        }else{		//음수가 최대값일 때
            answer += minusSearch(true);	//음수 탐색
            answer += plusSearch(false);	//양수 탐색
        }
        bw.write(answer + "");	//이동한 횟수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //양수 위치인 책을 놓는데 이동하는 횟수 구하는 함수
    static int plusSearch(boolean check){
        int c = plus.size()%M;
        int result = 0;
        //M으로 나누어 떨어지지 않을 때 가장 가까운 책들 나머지값 먼저 놓기
        if(c != 0){
            if(plus.size()/M > 0)
                result = plus.get(c-1)*2;
            else
                result = plus.get(c-1);
        }
        //남은 책 제자리에 놓기
        if(plus.size()/M > 0){
            int count = 0;
            for(int i=c;i<plus.size();i++){
                count++;
                if(count == M){
                    count = 0;
                    if(i == plus.size()-1)
                        result += plus.get(i);
                    else
                        result += plus.get(i)*2;
                }
            }
        }
        //최대값이 양수가 아닐 때 되돌아간다.
        if(!check && !plus.isEmpty())
            result += plus.get(plus.size()-1);
        return result;
    }
    static int minusSearch(boolean check){
        int c = minus.size()%M;
        int result = 0;
        //M으로 나누어 떨어지지 않을 때 가장 가까운 책들 나머지값 먼저 놓기
        if(c != 0){
            if(minus.size()/M > 0)
                result = minus.get(c-1)*2;
            else
                result = minus.get(c-1);
        }
        //남은 책 제자리에 놓기
        if(minus.size() / M > 0){
            int count = 0;
            for(int i=c;i<minus.size();i++){
                count++;
                if(count == M){
                    count = 0;
                    if(i == minus.size()-1)
                        result += minus.get(i);
                    else
                        result += minus.get(i) * 2;
                }
            }
        }
        //최대값이 음수가 아닐 때 되돌아간다.
        if(!check && !minus.isEmpty())
            result += minus.get(minus.size()-1);
        return Math.abs(result);
    }
}