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

2024. 8. 3. 22:13·알고리즘 (with JAVA)/코드트리 조별과제

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

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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);
    }
}
 
Colored by Color Scripter
cs

 

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

 

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

 

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

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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];
        }
    }
}
 
Colored by Color Scripter
cs

 

 

저작자표시 (새창열림)

'알고리즘 (with JAVA) > 코드트리 조별과제' 카테고리의 다른 글

코드트리 조별과제 6회차 (8.19 ~ 8.25)  (0) 2024.08.19
코드트리 조별과제 5회차 (8.12 ~ 8.18)  (0) 2024.08.12
코드트리 조별과제 4회차 (8.05 ~ 8.11)  (0) 2024.08.06
코드트리 조별과제 2회차(7.22 ~ 7.28)  (1) 2024.07.28
'알고리즘 (with JAVA)/코드트리 조별과제' 카테고리의 다른 글
  • 코드트리 조별과제 6회차 (8.19 ~ 8.25)
  • 코드트리 조별과제 5회차 (8.12 ~ 8.18)
  • 코드트리 조별과제 4회차 (8.05 ~ 8.11)
  • 코드트리 조별과제 2회차(7.22 ~ 7.28)
백_곰
백_곰
  • 백_곰
    친절한 코딩
    백_곰
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 알고리즘 (with JAVA)
        • 기본 알고리즘
        • 완전 탐색
        • 분할 정복 알고리즘
        • 동적 계획법
        • 탐욕법
        • 코딩 테스트 기출 문제
        • 코드트리 조별과제
      • 백준 (with JAVA)
        • 완전 탐색
        • 분할 정복
        • 그 외
      • 자바
        • 개발 환경 구축하기
        • 팁
        • 기본적인 개념
        • 컬렉션 프레임워크
        • 프로세스와 쓰레드
        • 지네릭스
        • 람다식
        • 스트림
        • 입출력 IO
        • 네트워킹
        • 열거형(enums)
        • java.lang 패키지
        • java.time 패키지
        • 유용한 클래스들
        • 형식화 클래스들
      • 안드로이드 with 자바
        • 응용 문제들
        • 자잘한 문제들
        • 오류 보고서
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

      코딩테스트
      Arrays
      불안정 정렬
      소켓 프로그래밍
      코딩트리조별과제
      file
      코드트리
      InputStream
      serializable
      Collections Framework
      TCP 소켓 프로그래밍
      ServerSocket
      snail
      java.time 패키지
      알고스팟
      outputstream
      안드로이드 스튜디오
      java.lang패키지
      제자리 정렬
      람다식
      문자 기반 스트림
      선택 정렬
      안정 정렬
      map()
      자바 개념
      중간연산
      다형성
      스트림
      역직렬화
      유용한 클래스
    • 최근 댓글

    • 최근 글

    • hELLO· Designed By정상우.v4.10.3
    백_곰
    코드트리 조별과제 3회차(7.29 ~ 8.04)
    상단으로

    티스토리툴바