코딩문제풀이/Baekjoon

[Java] 백준 2374번 : 같은 수로 만들기

코딩하는 포메라니안 2023. 2. 7. 14:31

1. 문제

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

 

2374번: 같은 수로 만들기

n(1 ≤ n ≤ 1,000)개의 자연수 A[1], A[2], A[3], …, A[n]이 있다. 이 자연수에 Add(i)라는 연산을 하면, A[i]가 1만큼 증가한다. 이때, A[i]만 증가하는 것이 아니고, A[i]의 좌우로 인접한 같은 수의 그룹이 한

www.acmicpc.net

 

 

2. 풀이과정

문제 유형에 stack이 써있는 걸 보고 풀었다.

안 보고 풀었으면 생각해내기 어려웠을 것 같았다.

입력을 처음부터 끝까지 받으면서, 구간마다 최소값을 찾아서 큰 값에서 뺀 값을 결과에 더해주었다.

마지막에 최대값에서 stack의 top에 있는 값을 빼주는 이유는 값이 감소하면서 끝날 경우 앞서 나온 최댓값에서 빼주는 형식이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        long result = 0;
        Stack<Integer> stack = new Stack<>();
        stack.add(Integer.parseInt(br.readLine()));

        int max = stack.peek();
        for(int i=1; i<N; i++){
            int now = Integer.parseInt(br.readLine());
            max = Math.max(max, now);
            
            if(now < stack.peek()){
                stack.pop();
                stack.add(now);
            }
            else if(now > stack.peek()){
                result += now - stack.pop();
                stack.add(now);
            }
        }

        System.out.println(result + max - stack.peek());
    }
}

 

 

결과