코드트리 조별과제 4회차 (8.05 ~ 8.11)

2024. 8. 6. 11:15·알고리즘 (with JAVA)/코드트리 조별과제

Two Pointer

 

[ 문제 ]

[4, 2, 1, 5, 7, 3] 와 같이 숫자들이 주어졌을 때, 특정 구간을 선택하여 구간 내 숫자의 합이

10이
넘지 않으면서 가장 큰 구간의 크기를 구하는 프로그램을 작성하시오.

 

 

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

무작정 코드를 작성한다면, 아래 코드처럼 모든 구간 O(N^2)개를 잡아보면서 합이 10을

넘지 않는 경우 중 구간 크기의 최댓값을 구한다.
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
public class Main {
    public static void main(String[] args) {
        int[] arr = new int[]{0, 4, 2, 1, 5, 7, 3};
        int k = 10;
        int n = 6;
 
        // 가능한 구간 중 최대 크기를 구합니다.
        int ans = 0;
 
        // 모든 구간을 탐색합니다.
        for(int i = 1; i <= n; i++) {
            // 구간 내 합이 10을 넘지 않을때까지 계속 진행합니다.
            int sumVal = 0;
            for(int j = i; j <= n; j++) {
                sumVal += arr[j];
 
                // 구간 내 합이 10을 넘게되면 그만 진행합니다.
                if(sumVal > k)
                    break;
 
                // 현재 구간 [i, j]는 
                // 유효한 구간이므로
                // 구간 크기 중 최댓값을 갱신합니다.
                ans = Math.max(ans, j - i + 1);
            }
        }
 
        // 조건을 만족하는 가장 큰 구간의 크기는
        // [4, 2, 1]로 3이 됩니다.
        System.out.print(ans);
    }
}
 
Colored by Color Scripter
cs
 

 

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

O(N^2)의 풀이법에서 알 수 있듯이 i가 1씩 증가할 때마다, 최대로 뻗어나갈 수 있는 j의 위치는

항상 같거나 증가한다는 것을 확인할 수 있다.

그 이유는 i가 1이 증가하면 Arr[i]만큼 감소하기 때문에 그만큼 뒤로 이동할 수 있는 여유 공간이

존재하기 때문이다.
이렇듯 문제에서의 특정 조건에 의해 원하는 구간의 양 끝을 나타내는 2개의 포인터가 한 방향으로만

계속 전진하는 형태의 테크닉을 Two Pointer라고 부른다.
Two Pointer를 이용해 i가 1 증가했을 때 j는 이전 값에서 시작하여 감소시키지 않고 최대로 뻗어

나가도록 하면 i, j 모두 한 방향으로만 진행하기 때문에 O(N)이 된다.

아래의 코드를 통해 이해하자.

 

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
public class Main {
    public static void main(String[] args) {
        int[] arr = new int[]{0, 4, 2, 1, 5, 7, 3};
        int k = 10;
        int n = 6;
 
        // 가능한 구간 중 최대 크기를 구합니다.
        int ans = 0;
 
        // 구간을 잡아봅니다.
        int sumVal = 0;
        int j = 0;
        for(int i = 1; i <= n; i++) {
            // 구간 내 합이 10을 넘지 않을때까지 계속 진행합니다.
            while(j + 1 <= n && sumVal + arr[j + 1] <= k) {
                sumVal += arr[j + 1];
                j++;
            }
 
            // 현재 구간 [i, j]는
            // i를 시작점으로 하는
            // 가장 긴 구간이므로
            // 구간 크기 중 최댓값을 갱신합니다.
            ans = Math.max(ans, j - i + 1);
 
            // 다음 구간으로 넘어가기 전에
            // arr[i]에 해당하는 값은 구간에서 제외시킵니다.
            sumVal -= arr[i];
        }
 
        // 조건을 만족하는 가장 큰 구간의 크기는
        // [4, 2, 1]로 3이 됩니다.
        System.out.print(ans);
    }
}
 
Colored by Color Scripter
cs

 

실제로 2중 포문으로 작성되어 있지만, ( i, j )는 모두 한 방향으로만 진행하기 때문에 시간복잡도가

이중 포문이 아닌 합으로 나타내짐에 유의하자.

 

연습문제 - (코드트리) 가장 짧은 부분

 

https://www.codetree.ai/missions/8/problems/shortest-subtotal?&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
40
41
42
43
44
45
46
47
48
49
import java.util.*;
import java.io.*;
 
public class Main {
    static int N, S, Arr[], ans;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
 
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
 
        Arr = new int[N+1];
 
        st = new StringTokenizer(br.readLine());
        for(int i=1; i<=N; i++){
            Arr[i] = Integer.parseInt(st.nextToken());
        }
 
        ans = Integer.MAX_VALUE;
 
        solve();
 
        if(ans == Integer.MAX_VALUE) ans = -1;
        System.out.println(ans);
    }
 
    static void solve(){
        long sum = 0;
        int j = 0;
 
        for(int i=1; i<=N; i++){
 
            while(j+1<=N && sum<S){
                sum += Arr[j+1];
                j++;
            }
 
            if(sum<S) break;
 
            ans = Math.min(ans, j-i+1);
 
            sum -= Arr[i];
        }
    }
}
 
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
코드트리 조별과제 3회차(7.29 ~ 8.04)  (1) 2024.08.03
코드트리 조별과제 2회차(7.22 ~ 7.28)  (1) 2024.07.28
'알고리즘 (with JAVA)/코드트리 조별과제' 카테고리의 다른 글
  • 코드트리 조별과제 6회차 (8.19 ~ 8.25)
  • 코드트리 조별과제 5회차 (8.12 ~ 8.18)
  • 코드트리 조별과제 3회차(7.29 ~ 8.04)
  • 코드트리 조별과제 2회차(7.22 ~ 7.28)
백_곰
백_곰
  • 백_곰
    친절한 코딩
    백_곰
  • 전체
    오늘
    어제
    • 분류 전체보기
      • 알고리즘 (with JAVA)
        • 기본 알고리즘
        • 완전 탐색
        • 분할 정복 알고리즘
        • 동적 계획법
        • 탐욕법
        • 코딩 테스트 기출 문제
        • 코드트리 조별과제
      • 백준 (with JAVA)
        • 완전 탐색
        • 분할 정복
        • 그 외
      • 자바
        • 개발 환경 구축하기
        • 팁
        • 기본적인 개념
        • 컬렉션 프레임워크
        • 프로세스와 쓰레드
        • 지네릭스
        • 람다식
        • 스트림
        • 입출력 IO
        • 네트워킹
        • 열거형(enums)
        • java.lang 패키지
        • java.time 패키지
        • 유용한 클래스들
        • 형식화 클래스들
      • 안드로이드 with 자바
        • 응용 문제들
        • 자잘한 문제들
        • 오류 보고서
  • 블로그 메뉴

    • 링크

    • 공지사항

    • 인기 글

    • 태그

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

    • 최근 글

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

    티스토리툴바