자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(복합적 문제_최대 길이 연속부분수열)

 

https://cote.inflearn.com/contest/10/problem/03-06

OnlineJudge

(위의 링크는 인프런 로그인 후, 해당 강의를 사지 않으면 접속이 되지 않습니다)

 

6. 최대 길이 연속부분수열

 

예시 입력 1 

14 2
1 1 0 0 1 1 0 1 1 0 1 1 0 1

예시 출력 1

8

 

 

내가 푼 풀이(Time: 734ms Memory: 35MB)

0을 만났을때 1로 바꿔주는데, lt가 따라오면서 0이었던건지 파악하기 위해 arr배열을 복사해서 ints[]배열을 만들었다.

그런데 강의 풀이를 보니까, 따로 배열 복사를 하지 않고 1로 바꿔주지 않아도 그냥 카운팅만 해서 단순하게 풀 수 있는 문제였다.

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public int solution(int n, int k, int[] arr) {
        int answer = 0, count = 0, lt = 0;
        int[] ints = Arrays.copyOf(arr, n);
        for (int rt = 0; rt < n; rt++) {
            if (arr[rt] == 0) {
                ints[rt] = 1;
                count++;
                while (count > k) {  // cnt = 3
                    if (arr[lt++] == 0) {
                        ints[lt] = 0;
                        count--;
                    }
                }
            }
            answer = Math.max(answer, rt - lt + 1);
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int k = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(T.solution(n, k, arr));
    }
}

 

강의 풀이 (Time: 725ms Memory: 34MB)

 

세번째 그림에서 lt는 0을 바꾸고 증가합니다. 증가하고 바꾸는게 아닙니다!!

바꾸고 증가하면 안되는 이유?

로직 상으로 lt가 0일때, 0번 인덱스가 0일 수도 있으니까 바꿔야하는지 체크한 뒤 증가시켜야함!!!!!

0에서 1로 바꿨다는 의미는 cnt++

1에서 0으로 되돌렸다는 의미는 cnt --

import java.util.Scanner;

public class Main {

    public int solution(int n, int k, int[] arr) {
        int answer = 0, cnt = 0, lt = 0;

        for (int rt = 0; rt < n; rt++) {
            if (arr[rt] == 0) cnt ++;
            while(cnt > k) {
                if (arr[lt] == 0) cnt --;
                lt++;
            }
            answer = Math.max(answer, rt-lt+1);
        }
        return answer;
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);
        int n = kb.nextInt();
        int k = kb.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = kb.nextInt();
        }
        System.out.println(T.solution(n,k,arr));
    }
}

 

 

내가 푼 풀이가 더 성능이 떨어지는 이유?

 

• 배열 복사: 첫 번째 코드에서는 Arrays.copyOf를 사용하여 배열을 복사하고 ints 배열에 복사된 배열을 저장합니다. 두 번째 코드에서는 별도의 배열 복사 작업 없이 원래 배열 arr을 직접 사용합니다. 이로 인해 메모리 사용량과 복사 작업이 추가로 발생하므로 첫 번째 코드에서는 약간의 성능 손실이 발생할 수 있습니다.

 

• 조건 확인 및 연산 순서: 두 코드는 조건 확인과 연산 순서가 다릅니다. 첫 번째 코드에서는 0을 만나면 ints 배열에 1을 설정하고 count를 증가시키며, 그 다음에 count가 k보다 큰지 확인하고 처리합니다. 반면 두 번째 코드에서는 0을 만나면 cnt를 증가시키고, 그 다음에 cnt가 k보다 큰지 확인하고 처리합니다. 첫 번째 코드는 추가적인 연산이 들어갔고, 두 번째 코드의 경우 조건 확인과 연산이 조금 더 단순하게 구성되어 있을 수 있으며, 이로 인해 성능이 더 좋을 수 있습니다.