[๋ณตํฉ์ ๋ฌธ์ ] 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๋ฅผ ๋ง์ด ์ฐ๋๋ฐ ์ฝ๋ ์ค ์ค์ด๊ธฐ์ ์ ๋ง ์ข์๊ฑฐ ๊ฐ๋ค!!
๋๋ ํ์ฉ ์์ฃผํด์ผ์ฐ๊ฒ๋ค~~
*๋์ ํ์ด๊ฐ ์ ํ๋ ธ๋์ง ๊ผญ ์ฐพ์์์ ์ ๋ํ๊ฒ ๋ค.
'์ฝ๋ฉํ ์คํธ' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[HashMap] 2. ์๋๊ทธ๋จ (1) | 2023.12.31 |
---|---|
[ํด์ฌ] 1. ํ๊ธ ํ์ฅ (0) | 2023.12.30 |
[ํฌ ํฌ์ธํฐ] 5. ์ฐ์๋ ์์ฐ์์ ํฉ (0) | 2023.12.26 |
[๋ณตํฉ๋ฌธ์ ] 4. ์ฐ์ ๋ถ๋ถ์์ด (0) | 2023.12.24 |
[์ฌ๋ผ์ด๋ฉ ์๋์ฐ] 3. ์ต๋ ๋งค์ถ (0) | 2023.12.24 |
๋๊ธ