[백준, Java] 2374번, 같은 수로 만들기(스택, 그리드)

문제 링크

2374번: 같은 수로 만들기

---

주의사항

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

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. Add(i)연산시 A[i] + 1이 진행되며, 좌우 인접한 같은 수의 그룹은 모두 증가됩니다.

2. A[n]에 대해서 모든 수가 같아지도록 Add연산을 할 때 최소 횟수를 결과로 출력합니다.

3. A[1], A[n]은 인접하지 않습니다.

 

알고리즘 진행 순서.

 

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

 

2. 스택을 이용해서 같은 수를 만드는 최소 횟수 Add 연산 횟수를 탐색합니다.

 

3. 탐색을 통해 Add 연산의 최소 횟수를 결과로 출력합니다.

 

Add 연산 최소 횟수 구하기(Stack, Greedy)

 

Add 연산을 최소로 진행하기 위해서는 2가지를 살펴보겠습니다.

 

1.   A[i]가 최소값이 아니면 Add 연산을 진행하지 않아야 한다.

 

만약, 최소값이 아닌 값에 대해서 Add 연산을 진행하게 된다면 그 보다 작은 값은 그 값과 동일해지기 위해서 Add 연산을 더 진행해야합니다.

 

예를 들어,

 

{ 3, 1 }이 존재할 때

 

Add(1) = A[1] + 1 = 3 + 1 = 4가 됩니다.

 

여기서 A[2] = 1의 값을 동일한 값으로 맞추기 위해서는 Add 연산을 3번이나 진행해야 합니다.

 

하지만, Add(1) 연산을 더 진행하지 않았다면 2번이면 { 3, 3 }으로 설정될 수 있습니다.

 

즉, 집합을 만드는 과정에서 동일한 집합을 바라보게 된다는 것은 사이클이 형성된다는 것입니다.

 

2. A[i] < A[i]일 때 A[i] 이전의 값들을 맞춰주어야 한다.

 

{ 2, 2, 2, 5 }이 존재할 때

 

A[3] = 2, A[4] = 5으로 더 큰 수를 만났을 때는 지금까지의 값들을 맞춰주기 위해서 Add연산을 진행해야 합니다.

 

Add()을 3번 진행하게 되면 { 5, 5, 5, 5 }으로 동일한 값으로 설정할 수 있습니다.

 

동일한 값들이 연속할 때에는 하나의 값으로 봐도 무방합니다. { 2, 2, 2, 5 } = { 2, 5 }와 동일하다고 볼 수 있습니다.

 

위 2가지를 Stack을 이용해서 A[1~n]의 값들을 맞추는 Add 연산을 진행하면 됩니다.

 

A[k-1] ≥ A[k]을 만족할 때

 

Stack.push(A[k]);

 

A[k-1] < A[k]을 만족할 때

 

Stack의 쌓인 이전 값들에 대해서 A[k]가 될 때까지 Add 연산을 진행합니다.

 

 

※예제 입력을 푸는 과정을 확인하시면 이해하기 편하실 것입니다.

 

예제입력 1.

 

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

 

i	1	2	3
A[i]	1	5	10

 

2. 스택을 이용해서 같은 수를 만드는 최소 횟수 Add 연산 횟수를 탐색합니다.

 

초기 Stack

 

 

A[1] = 1 탐색

 

 

1

 

Stack에 아무값도 없기 때문에 더 작을 수없으므로 Add 연산 Push!!

 

A[2] = 5 탐색

 

 

5

5

 

A[k-1] < A[k]을 만족하여 Add 연산 진행!

 

{ 1, 5 }

 

A[1] = Add(1) 4번 진행 = { 5, 5 }

 

 

A[3] = 10 탐색

 

10

10

10

 

A[k-1] < A[k]을 만족하여 Add 연산 진행!

 

{ 5, 5, 10 }

 

A[2] = Add(1) 5번 진행 = { 10, 10, 10 }

 

 

 

 

3. 탐색을 통해 Add 연산의 최소 횟수를 결과로 출력합니다.

 

Add(1) : 4번

 

Add(2) :5번

 

Add 연산 횟수 : 4 + 5 = 9번

 

9 결과로 출력합니다.

 

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• Stack을 이용해서 A[1 ~ n]까지 동일한 값이 되도록 탐색합니다.
• 탐색시 A[k-1], A[k]에 따라 Add연산 및 Stack.push()을 진행합니다.
• 탐색을 통해 Add 연산 횟수를 BufferedWriter 저장합니다.
• BufferedWriter에 저장된 결과를 출력합니다.

• calculate 함수는 스택 최대값과 현재 숫자 값을 기준으로 Add 연산이 최소가 되도록 진행합니다.

결과코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    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));
        int n = Integer.parseInt(br.readLine());
        //Add 연산 횟수
        BigInteger result = new BigInteger("0");
        Stack<Integer> stack = new Stack<>();
        int max = 0;
        //최소 연산 횟수 구하기
        for(int i=0;i<n;i++){
            int num = Integer.parseInt(br.readLine());
            max = Math.max(max, num);
            //스택에 아무값이 존재하지 않을 때
            if(stack.isEmpty()){
                stack.push(num);
                continue;
            }

            //스택 내부에 최대값보다 더 큰 값일 때
            if(stack.peek() < num){
                //Add 연산 진행
                BigInteger val = calculate(stack, num);
                //Add연산 횟수 더하기
                result = result.add(val);
            }
            //현재 값 스택에 저장
            stack.push(num);
        }
        //스택에 남은 값들 Add 연산 진행 및 횟수 더하기
        result = result.add(calculate(stack, max));
        //Add 연산 최소 횟수 BufferedWriter 저장
        bw.write(result.toString());
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //Add 연산을 진행하는 함수
    public static BigInteger calculate(Stack<Integer> stack, int num){
        BigInteger result = new BigInteger("0");
        //최소로 Add 연산 진행
        while(!stack.isEmpty() && stack.peek() < num){
            int peek = stack.pop();
            int nxtPeek = stack.isEmpty() ? num : Math.min(stack.peek(), num);
            result = result.add(BigInteger.valueOf(nxtPeek).subtract(BigInteger.valueOf(peek)));
        }
        return result;
    }
}