Tags
- ๊ทธ๋ํ ์ด๋ก
- LV2
- Brute Force Algorithm
- greedy
- ์ ๋ ฌ
- BOJ
- CodingTest
- PGM
- Python
- ๊ทธ๋ํ ํ์
- Dynamic Programming
- queue
- Study
- stack
- ๊ตฌํ
- ๊น์ด ์ฐ์ ํ์
- BFS
- ๋ฌธ์์ด
- sort
- SpringBoot
- ์๋ฎฌ๋ ์ด์
- DP
- ์๋ฃ๊ตฌ์กฐ
- dfs
- Java
- ์ํ
- ๋๋น ์ฐ์ ํ์
- ๋ฐฑํธ๋ํน
- ๊ต์ฌ
- ์ ์๋ก
Archives
๊ธฐ๋ก๋ฐฉ
Lv.2 : ์ฐ์๋ ๋ถ๋ถ ์์ด์ ํฉ ๋ณธ๋ฌธ
ํ๋ก๊ทธ๋๋จธ์ค
์ฝ๋ ์ค์ฌ์ ๊ฐ๋ฐ์ ์ฑ์ฉ. ์คํ ๊ธฐ๋ฐ์ ํฌ์ง์ ๋งค์นญ. ํ๋ก๊ทธ๋๋จธ์ค์ ๊ฐ๋ฐ์ ๋ง์ถคํ ํ๋กํ์ ๋ฑ๋กํ๊ณ , ๋์ ๊ธฐ์ ๊ถํฉ์ด ์ ๋ง๋ ๊ธฐ์ ๋ค์ ๋งค์นญ ๋ฐ์ผ์ธ์.
programmers.co.kr
๐ธ ๋ฌธ์ ๋ถ์ ๐ธ
- ๋น๋ด๋ฆผ์ฐจ์ ์์ด์ ๋ถ๋ถ ์์ด ์ค ํฉ์ด k๊ฐ ๋๋ ๊ฐ์ฅ ์งง์ ๋ถ๋ถ ์์ด์ ์์๊ณผ ๋ ์ธ๋ฑ์ค๋ฅผ ๋ฐํํ๋ค.
- ๊ฐ์ ๊ธธ์ด๊ฐ ์ฌ๋ฌ๊ฐ ๋์ค๋ ๊ฒฝ์ฐ ๋จผ์ ๋์จ ๋ถ๋ถ ์์ด์ ์ฌ์ฉํ๋ค.
๐ธ ๋ฌธ์ ํ์ด ๐ธ
- ์ธ๋ฑ์ค๋ฅผ ์ด๋ํ๋ฉฐ ๋ถ๋ถ ์์ด์ ํฉ์ ๊ณ์ฐํ๋ ๋ฌธ์ ์ด๋ฏ๋ก, ํฌํฌ์ธํฐ๋ก ํ์ดํ๋ค.
- ๋ ์ธ๋ฑ์ค left์ right๋ฅผ ์ง์ ํ๊ณ , k๋ณด๋ค ์์ผ๋ฉด right + 1, k๋ณด๋ค ํฌ๋ค๋ฉด left + 1๋ก ์ด๋ํ๋ค.
- ์ธ๋ฑ์ค๊ฐ ๋ณํ ๋ ๋ถ๋ถ ์์ด์ ํฉ๋ ๋ณ๊ฒฝํ๋ฉฐ ๊ณ์ฐํ๋ค.
- ๋ถ๋ถ ์์ด์ ํฉ์ด k์ ๊ฐ์์ง๋ค๋ฉด, ๊ธธ์ด๊ฐ ์ต์์ผ ๊ฒฝ์ฐ ์ธ๋ฑ์ค๋ฅผ ์ ์ฅํ๋ค.
๐ธ ์ฝ๋ ๐ธ
class Solution {
public int[] solution(int[] sequence, int k) {
int[] answer = new int[2];
int min = Integer.MAX_VALUE;
int left = 0;
int right = 0;
int window = sequence[0];
while (left <= right && right < sequence.length) {
if (window == k) {
if (min > right-left) {
min = right-left;
answer[0] = left;
answer[1] = right;
}
window -= sequence[left++];
if (++right < sequence.length)
window += sequence[right];
} else if (window > k) {
window -= sequence[left++];
} else {
if (++right < sequence.length)
window += sequence[right];
}
}
return answer;
}
}
๐ธ ์ฝ๋ ํด์ ๐ธ
- ๋ถ๋ถ ์์ด์ ์ข์ฐ ์ธ๋ฑ์ค๋ฅผ left, right์ ์ ์ฅํ๊ณ ํฉ์ window์ ์ ์ฅํ๋ค.
- int ๋ณ์ min์ ๋ถ๋ถ ์์ด์ ํฉ์ด k์ผ๋์ ๊ธธ์ด๋ฅผ ์ ์ฅํ๊ณ , ์ต์๊ฐ์ ์ฐพ์๊ฐ๋ค.
- left๊ฐ right๋ณด๋ค ์ปค์ง๊ฑฐ๋, right๊ฐ ์์ด์ ๊ธธ์ด๋ฅผ ๋ฒ์ด๋๋ฉด ๋์ด์ ํด๋นํ๋ ๋ถ๋ถ ์์ด์ด ์๋ ๊ฒ์ด๋ฏ๋ก ๊ณ์ฐ์ ์ข
๋ฃํ๋ค.
- ๋ถ๋ถ ์์ด์ ํฉ์ด k๊ฐ ๋๋ค๋ฉด, min๋ณด๋ค ์งง์ ๊ฒฝ์ฐ ์ ๋ต ์ธ๋ฑ์ค๋ฅผ ๊ฐฑ์ ํ๊ณ , left์ right๋ฅผ +1 ํ๋ค.
- ๋ถ๋ถ ์์ด์ ํฉ์ด k๋ณด๋ค ํฌ๋ค๋ฉด, window์์ ๊ธฐ์กด left ์ธ๋ฑ์ค ๊ฐ์ ๋นผ๊ณ , left๋ฅผ +1 ํ๋ค.
- ๋ถ๋ถ ์์ด์ ํฉ์ด k๋ณด๋ค ์๋ค๋ฉด, right๋ฅผ +1ํ๊ณ , widnow์ right ์ธ๋ฑ์ค ๊ฐ์ ๋ํ๋ค.
- ์ ์ฅํ ์ธ๋ฑ์ค ๋ฐฐ์ด answer๋ฅผ ๋ฐํํ๋ค.
๐ธ end ๐ธ
- ๋ถ๋ถ ์์ด์ ํฉ์ ํ์ธํ๋ฉฐ ์ธ๋ฑ์ค๋ฅผ ์งํํ๋ ๋ฐฉ์์ด ์ ํ์ ์ธ ํฌํฌ์ธํฐ ๋ฐฉ์์ด๋ผ ๊ฐ๋จํ ํ์ดํ ์ ์์๋ค.
728x90
'CodingTest > Java' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
BOJ_2638 : ์น์ฆ (0) | 2024.01.25 |
---|---|
BOJ_5639 : ์ด์ง ๊ฒ์ ํธ๋ฆฌ (0) | 2023.12.15 |
Lv.2 : ์๊ฒฉ ์์คํ (0) | 2023.11.29 |
Lv.2 : ์ซ์ ๋ณํํ๊ธฐ (0) | 2023.11.27 |
Lv.2 : [PCCP ๊ธฐ์ถ๋ฌธ์ ] 2๋ฒ (0) | 2023.11.24 |