๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

[๋ณตํ•ฉ์  ๋ฌธ์ œ] 6.์ตœ๋Œ€ ๊ธธ์ด ์—ฐ์†๋ถ€๋ถ„์ˆ˜์—ด

์‹œํ๋ฆฌํ‹ฐ์ง€ํ˜ธ 2023. 12. 28.
6. ์ตœ๋Œ€ ๊ธธ์ด ์—ฐ์†๋ถ€๋ถ„์ˆ˜์—ด
 

์„ค๋ช…

0๊ณผ 1๋กœ ๊ตฌ์„ฑ๋œ ๊ธธ์ด๊ฐ€ N์ธ ์ˆ˜์—ด์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. ์—ฌ๋Ÿฌ๋ถ„์€ ์ด ์ˆ˜์—ด์—์„œ ์ตœ๋Œ€ k๋ฒˆ์„ 0์„ 1๋กœ ๋ณ€๊ฒฝํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์—ฌ๋Ÿฌ๋ถ„์ด ์ตœ๋Œ€ k๋ฒˆ์˜ ๋ณ€๊ฒฝ์„ ํ†ตํ•ด ์ด ์ˆ˜์—ด์—์„œ 1๋กœ๋งŒ ๊ตฌ์„ฑ๋œ ์ตœ๋Œ€ ๊ธธ์ด์˜ ์—ฐ์†๋ถ€๋ถ„์ˆ˜์—ด์„ ์ฐพ๋Š” ํ”„๋กœ๊ทธ๋žจ์„ ์ž‘์„ฑํ•˜์„ธ์š”.

๋งŒ์•ฝ ๊ธธ์ด๊ฐ€ ๊ธธ์ด๊ฐ€ 14์ธ ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์ˆ˜์—ด์ด ์ฃผ์–ด์ง€๊ณ  k=2๋ผ๋ฉด

1 1 0 0 1 1 0 1 1 0 1 1 0 1

์—ฌ๋Ÿฌ๋ถ„์ด ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” 1์ด ์—ฐ์†๋œ ์—ฐ์†๋ถ€๋ถ„์ˆ˜์—ด์€

์ด๋ฉฐ ๊ทธ ๊ธธ์ด๋Š” 8์ž…๋‹ˆ๋‹ค.

์ž…๋ ฅ

์ฒซ ๋ฒˆ์งธ ์ค„์— ์ˆ˜์—ด์˜ ๊ธธ์ด์ธ ์ž์—ฐ์ˆ˜ N(5<=N<100,000)์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.

๋‘ ๋ฒˆ์งธ ์ค„์— N๊ธธ์ด์˜ 0๊ณผ 1๋กœ ๊ตฌ์„ฑ๋œ ์ˆ˜์—ด์ด ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค.

์ถœ๋ ฅ

์ฒซ ์ค„์— ์ตœ๋Œ€ ๊ธธ์ด๋ฅผ ์ถœ๋ ฅํ•˜์„ธ์š”.

์˜ˆ์‹œ ์ž…๋ ฅ 1 

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

์˜ˆ์‹œ ์ถœ๋ ฅ 1

8

 

 

 

<<ํ’€์ด>>

 

-๋‚˜์˜ ํ’€์ด-

 

์‹œ๊ฐ„ ๋ณต์žก๋„ : O(N)

 

์•Œ๊ณ ๋ฆฌ์ฆ˜ : ํˆฌ ํฌ์ธํ„ฐ

 

์šฐ์„ , ใ…‹ใ…‹ ํ‹€๋ ธ๋‹ค. ์˜ˆ์‹œ ์ž…๋ ฅ๊ณผ ์ถœ๋ ฅ์€ ์ •๋‹ต์ด์ง€๋งŒ ๋Œ๋ ค๋ณด๋‹ˆ ์–ด๋””์„ ๊ฐ€ ์˜ค๋ฅ˜๊ฐ€ ์žˆ๋Š” ๊ฒƒ ๊ฐ™๋‹ค.

๋‚ด ๋…ผ๋ฆฌ์ƒ ๋งž๋Š”๊ฑฐ ๊ฐ™์€๋ฐ,, ์–ด๋””์„œ ๋ฌธ์ œ์ผ๊นŒ ใ… ใ… 

import java.util.*;

class Main {
    public int solution(int n, int m, int[] arr) {
        int lt = 0, sum = 0, max = 0, count = 0;
        for(int rt = 0; rt < n; rt++) {
            if(arr[rt] == 1) {
                sum += arr[rt];
            } else if (arr[rt] == 0) {
                if(count++ < m) {
                    sum += 1;
                } else {
                    if (sum > max) {
                        max = sum;
                        sum = 0;
                        lt ++;
                        rt = lt;
                        count = 0;
                    }
                }
            }
        }
        return max;
    }

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

 

-๊ฐ•์‚ฌ๋‹˜ ํ’€์ด-

 

์‹œ๊ฐ„ ๋ณต์žก๋„ : O(N)

 

์•Œ๊ณ ๋ฆฌ์ฆ˜ : ํˆฌ ํฌ์ธํ„ฐ

import java.util.*;

class Main {
    public int solution(int n, int m, int[] arr) {
        int lt = 0,  cnt = 0, answer = 0;
        for(int rt = 0; rt < n; rt++) {
            if(arr[rt] == 0) cnt++;
            while(cnt > m) {
                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 in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        System.out.print(T.solution(n, m, arr));
    }
}

 

ใ…‹ใ…‹ใ…‹ ์บฌ  ~ ๋ฉ‹์ง€๊ฒŒ ํ‘ธ์…จ๋‹ค. ใ…‹ใ…‹ ์•„๋‹ˆ rt - lt + 1์„ ํ•  ์ƒ๊ฐ์„ ํ•˜๋‹ค๋‹ˆ..

 

์ผ๋‹จ์€ ๋‚˜์˜ ์œ— ๋ฌธ์ œ๊ฐ€ ์™œ ํ‹€๋ ธ๋Š”์ง€๋Š” ๋ชจ๋ฅด๊ฒ ์ง€๋งŒ ํ™•์‹คํžˆ ๊ฐ•์‚ฌ๋‹˜ ๋ฐฉ๋ฒ•์€ ์ง๊ด€์ ์ธ ๊ฒƒ์€ ๋ถ„๋ช…ํ•˜๋‹ค. ใ… ใ… 

 

๊ทธ๋ฆฌ๊ณ  ๋‚ด์žฅ ํด๋ž˜์Šค Math๋ฅผ ๋งŽ์ด ์“ฐ๋Š”๋ฐ ์ฝ”๋“œ ์ค„ ์ค„์ด๊ธฐ์— ์ •๋ง ์ข‹์€๊ฑฐ ๊ฐ™๋‹ค!!

 

๋‚˜๋„ ํ™œ์šฉ ์ž์ฃผํ•ด์•ผ์“ฐ๊ฒ„๋‹ค~~

 

*๋‚˜์˜ ํ’€์ด๊ฐ€ ์™œ ํ‹€๋ ธ๋Š”์ง€ ๊ผญ ์ฐพ์•„์™€์„œ ์—…๋Žƒํ•˜๊ฒ ๋‹ค.

๋Œ“๊ธ€