๋ฌด์ธ๋์ ๊ฐํ ์ฌ๋๋ค์ ๊ตฌ๋ช ๋ณดํธ๋ฅผ ์ด์ฉํ์ฌ ๊ตฌ์ถํ๋ ค๊ณ ํฉ๋๋ค. ๊ตฌ๋ช ๋ณดํธ๋ ์์์ ํ ๋ฒ์ ์ต๋ 2๋ช ์ฉ ๋ฐ์ ํ ์ ์๊ณ , ๋ฌด๊ฒ ์ ํ๋ ์์ต๋๋ค.
์๋ฅผ ๋ค์ด, ์ฌ๋๋ค์ ๋ชธ๋ฌด๊ฒ๊ฐ [70kg, 50kg, 80kg, 50kg]์ด๊ณ ๊ตฌ๋ช ๋ณดํธ์ ๋ฌด๊ฒ ์ ํ์ด 100kg์ด๋ผ๋ฉด 2๋ฒ์งธ ์ฌ๋๊ณผ 4๋ฒ์งธ ์ฌ๋์ ๊ฐ์ด ํ ์ ์์ง๋ง 1๋ฒ์งธ ์ฌ๋๊ณผ 3๋ฒ์งธ ์ฌ๋์ ๋ฌด๊ฒ์ ํฉ์ 150kg์ด๋ฏ๋ก ๊ตฌ๋ช ๋ณดํธ์ ๋ฌด๊ฒ ์ ํ์ ์ด๊ณผํ์ฌ ๊ฐ์ด ํ ์ ์์ต๋๋ค.
๊ตฌ๋ช ๋ณดํธ๋ฅผ ์ต๋ํ ์ ๊ฒ ์ฌ์ฉํ์ฌ ๋ชจ๋ ์ฌ๋์ ๊ตฌ์ถํ๋ ค๊ณ ํฉ๋๋ค.
์ฌ๋๋ค์ ๋ชธ๋ฌด๊ฒ๋ฅผ ๋ด์ ๋ฐฐ์ด people๊ณผ ๊ตฌ๋ช ๋ณดํธ์ ๋ฌด๊ฒ ์ ํ limit๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ๋ชจ๋ ์ฌ๋์ ๊ตฌ์ถํ๊ธฐ ์ํด ํ์ํ ๊ตฌ๋ช ๋ณดํธ ๊ฐ์์ ์ต์๊ฐ์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
people | limit | return |
---|---|---|
[70, 50, 80, 50] | 100 | 3 |
[70, 80, 50] | 100 | 3 |
๋๋ ์ต์์ ๊ฐ์๋ก ๋ณดํธ์ ์ฌ๋์ ๋ ๋ช
ํ์์ผ ํ๊ธฐ ๋๋ฌธ์,
๋ฌด๊ฒ๊ฐ ๊ฐ์ฅ ์ ๊ฒ ๋๊ฐ๋ ์ฌ๋๊ณผ ๊ฐ์ฅ ๋ง์ด ๋๊ฐ๋ ์ฌ๋ ๋ ๋ช
์ ์ฐพ์ ํ์ฐ๋ ๊ฒ์ด ๊ฐ์ฅ ํจ์จ์ ์ผ ๊ฒ์ด๋ผ๋ ์๊ฐ์ด ๋ค์๋ค.
์ด๋ฅผ ๊ตฌํํ๊ธฐ ์ํด ์ฐ์ people
๋ฐฐ์ด์ ์ค๋ฆ์ฐจ์์ผ๋ก ์ ๋ ฌํ ํ,
๋ฐฐ์ด์ ์์์ ์ถ๋ฐํ๋ ์ฆ, ๋ฌด๊ฒ๊ฐ ๊ฐ์ฅ ๊ฐ๋ฒผ์ด ์ฌ๋๋ถํฐ ํ์ธํ๋ startIdx
์
๋ฐฐ์ด์ ๋์์ ์ถ๋ฐํ๋ ์ฆ, ๋ฌด๊ฒ๊ฐ ๊ฐ์ฅ ๋ฌด๊ฑฐ์ด ์ฌ๋๋ถํฐ ํ์ธํ๋ endIdx
๋ฅผ ํ์ฉํ๊ธฐ๋ก ํ๋ค.
import java.util.Arrays;
class Solution {
public int solution(int[] people, int limit) {
int count = 0; // ์ต์ข
๋ณดํธ ๊ฐ์
int startIdx = 0; // ๋ฌด๊ฒ๊ฐ ๊ฐ์ฅ ์์ ์ฌ๋๋ถํฐ ํ์ํ ์ธ๋ฑ์ค
int endIdx = people.length - 1; // ๋ฌด๊ฒ๊ฐ ๊ฐ์ฅ ๋ฌด๊ฑฐ์ด ์ฌ๋๋ถํฐ ํ์ํ ์ธ๋ฑ์ค
Arrays.sort(people); // ์ค๋ฆ์ฐจ์ ์ ๋ ฌ
// startIdx๊ฐ endIdx๋ณด๋ค ์ปค์ผ ๋ชจ๋ ์ฌ๋ ํ์ ์๋ฃ
while (startIdx <= endIdx) {
// ๋ ์ฌ๋ ๋ฌด๊ฒ์ ํฉ์ด limit ์ดํ๋ฉด ํจ๊ป ํ์น ๊ฐ๋ฅ
// ๋ ์ฌ๋์ด ํ์นํ์ผ๋ฏ๋ก, startIdx, endIdx ๋ชจ๋ ์ฆ๊ฐ/๋ณดํธ ์ ์ฆ๊ฐ
if (people[startIdx] + people[endIdx] <= limit) {
startIdx++;
endIdx--;
count++;
}
// ๋ ์ฌ๋ ๋ฌด๊ฒ์ ํฉ์ด limit ์ด์์ด๋ฉด
// endIdx์ ์๋ ์ฌ๋์ ๋ฌด์กฐ๊ฑด ํผ์ ํ์น ํด์ผํ๋ฏ๋ก, endIdx๊ฐ์/๋ณดํธ ์ ์ฆ๊ฐ
else {
endIdx--;
count++;
}
}
return count;
}
}
๋ฐฐ์ด์ ์ ๋์์ ์ถ๋ฐํ๋ startIdx
์ endIdx
๊ฐ ๋ง๋๋ฉด, ๋ชจ๋ ์ฌ๋์ ๋ค ํ์ํ ๊ฒ์ด๊ธฐ ๋๋ฌธ์, ํด๋น ์กฐ๊ฑด์ ํฌํจํ๋ while๋ฌธ์ ์์ฑํ๊ณ , ๊ทธ ์์ ๋ ๊ฐ์ ์กฐ๊ฑด์ ๋ค์ ๋ถ๊ธฐํ์๋ค.
์ฒซ ๋ฒ์งธ ์กฐ๊ฑด์ผ๋ก๋ ๋ ์ฌ๋์ด ํ์นํ ์ ์๋ ๊ฒฝ์ฐ์ธ๋ฐ,
๋ ์ฌ๋์ ๋ฌด๊ฒ์ ํฉ์ด limit
์ดํ๋ฉด, ๋ ์ฌ๋์ด ํ์นํ ์ ์์ผ๋ฏ๋ก, ๋ ์ฌ๋์ ๊ฐ๋ฆฌํค๊ณ ์๋ ๋ ์ธ๋ฑ์ค๋ฅผ ๊ฐ๊ฐ ์ฆ๊ฐํด ์ฃผ์๊ณ , ๋ณดํธ์ ์ด ๊ฐ์์๋ 1์ ๋ํด ์ฃผ์๋ค.
๋ ๋ฒ์งธ ์กฐ๊ฑด์ผ๋ก๋ ๋ ์ฌ๋์ด ํ์นํ ์ ์๋ ๊ฒฝ์ฐ์ด๋ค.
์ด ๊ฒฝ์ฐ๋ ๋ ์ฌ๋์ ๋ฌด๊ฒ์ ํฉ์ด limit
๋ณด๋ค ํฐ ๊ฒฝ์ฐ์ด๊ณ , ํ์ฌ ๊ฐ์ฅ ๋ฌด๊ฑฐ์ด ์ฌ๋ ์ฆ, endIdx
๊ฐ ๊ฐ๋ฆฌํค๊ณ ์๋ ์ฌ๋์ ๋ค๋ฅธ ๋๊ตฌ์๋ ํ ์ ์๋ค๋ ์๋ฏธ์ด๊ธฐ ๋๋ฌธ์,
endIdx
๋ฅผ ๊ฐ์์ํค๊ณ count
๋ฅผ ์ฆ๊ฐ์์ผ์ค์ผ๋ก์จ endIdx
๊ฐ ๊ฐ๋ฆฌํค๊ณ ์๋ ์ฌ๋์ ํผ์ ๋ณดํธ์ ํ์ฐ๋๋ก ํ์๋ค.
์ด ํ์ด๋ฒ์ ๊ฐ ๋จ๊ณ์์ ์ต์ ์ด๋ผ๊ณ ์๊ฐ๋๋ ๊ฒ์ ์ ํํด ๋๊ฐ๋ ๋ฐฉ์์ธ ๊ทธ๋ฆฌ๋ ๋ฐฉ์์ ์ฌ์ฉํ ๊ฒ์ผ๋ก, ํญ์ ์ ์ฒด ๋ฌธ์ ์ ๋ํด ์ต์ ์ ํด๋ฅผ ๋ณด์ฅํ์ง๋ ์๋๋ค.
์ฆ, ๊ทธ๋ฆฌ๋๋ ์ต์ ์ ํด๋ฅผ ๋ณด์ฅํ์ง ์์ง๋ง, ๋๋ถ๋ถ์ ๊ฒฝ์ฐ์๋ ์ด๋ ๊ฒ ์ข์ ๊ทผ์ฌ ํด๋ฅผ ์ฐพ์ ์ ์๋ค๋ ๊ฒ์ด๋ค.
์ด ๋ฌธ์ ์์ ์ด๋ ๊ฒ ๊ทธ๋ฆฌ๋๋ฅผ ์ฌ์ฉํด ์ข์ ๊ฒฐ๊ณผ๋ฅผ ์ป์ ์ ์์ง๋ง, ํญ์ ์ต์ ์ ํด๋ฅผ ๋ณด์ฅํ์ง๋ ์๋๋ค๋ ๊ฒ์ ์ผ๋์ ๋์ด์ผ ํ๋ค!
์ค์น ์ฌ๋ฐ์ด์์น