코드트리 조별과제 3회차(7.29 ~ 8.04)

PreProcessing

 

[ 문제 ]

[4, 2, 1, 5, 7, 3] 와 같이 숫자들이 주어졌을 때, 특정 위치를 적절하게 선택하여 해당 위치에 놓여있는 숫자와 그 숫자를 포함하여 뒤에 놓여 있는 숫자들 중 최솟 값을 곱한 값이 최대가 되도록 프로그램을 작성하시오.

 

[ 해결책(1) - O(N^2) ]

1번째 위치를 선택하게 되면, 1이 최솟값이므로 4*1 = 4 가 된다. 5번째 위치를 선택하게 되면, 3이 최솟값이므로 7*3 = 21 이 된다. 그러므로, 5번째 위치가 나오도록 하면 된다.

무작정 코드를 작성하게 되면, 각 위치를 한번 씩 잡아보면서 그 뒤에 있는 숫자 전부를 확인하면 O(N^2)이 된다.

 

 

[ 해결책(2) - O(N) ]

그러나, 만약 R이라는 배열을 R(i) = i 번째부터 N 번째까지 미리 구해 놓는다면, 각 위치를 체크하면서 구하면 되므로, O(N)으로 구할 수 있게 된다.

그러면 R 배열을 어떻게 구할 수 있을까? 먼저, R(N)은 Arr(N)과 같으므로 초기화하고 N-1 ~ 1까지 R(i) = min(R(i+1), Arr(i)) 로 계산하게 되면, O(N)이 된다.

그러면 이제 위 문제를 토대로 한번 R 배열과 실제 코드를 만들어보자!

 

	1	2	3	4	5	6
Arr	4	2	1	5	7	3
R	1	1	1	3	3	3

import java.util.*;
import java.io.*;
 
public class Main {
    public static final int INT_MIN = Integer.MIN_VALUE;
 
    public static void main(String[] args) {
        int N = 6;
 
        int[] arr = new int[]{0, 4, 2, 1, 5, 7, 3};
        int[] R = new int[N+1];
 
        // R 배열을 채워줍니다.
        R[N] = arr[N];
        for(int i = N - 1; i >= 1; i--)
            R[i] = Math.min(R[i + 1], arr[i]);
 
        // 답을 구해줍니다.
        int ans = INT_MIN;
        for(int i = 1; i <= N; i++)
            ans = Math.max(ans, arr[i] * R[i]);
 
        // 가능한 최댓값 = 21
        System.out.print(ans);
    }
}
 

이러한 R 배열 생성 및 작업을 전처리 작업이라고 부른다.

 

연습문제 - (코드트리) 괄호 쌍 만들어주기

 

https://www.codetree.ai/missions/8/problems/pair-parentheses?&utm_source=clipboard&utm_medium=text

 

 

import java.util.*;
import java.io.*;
 
public class Main {
    static String input;
    static int N, R[];
    static long ans;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        input = br.readLine();
 
        N = input.length();
 
        R = new int[N];
 
        solve();
 
        System.out.println(ans);
    }
 
    static void solve(){
 
        // 전처리 작업
        R[N-1] = 0;
 
        for(int i=N-2; i>=0; i--){
            if(input.charAt(i) == ')' && input.charAt(i+1) == ')') R[i] = R[i+1] + 1;
            else R[i] = R[i+1];
        }
 
        // 답 도출 
        for(int i=0; i<N-2; i++){
            if(input.charAt(i)=='(' && input.charAt(i+1)=='(') ans += R[i+2];
        }
    }
}