๐Ÿ”ฅ[99ํด๋Ÿฝ ์ฝ”ํ…Œ ์Šคํ„ฐ๋””] 19์ผ์ฐจ TIL - ๊ตฌ๋ช…๋ณดํŠธ

HOONSSACยท2024๋…„ 8์›” 9์ผ
1

99Club Coding Test Study

๋ชฉ๋ก ๋ณด๊ธฐ
19/41
post-thumbnail

โณ๋ฌธ์ œ

๋ฌด์ธ๋„์— ๊ฐ‡ํžŒ ์‚ฌ๋žŒ๋“ค์„ ๊ตฌ๋ช…๋ณดํŠธ๋ฅผ ์ด์šฉํ•˜์—ฌ ๊ตฌ์ถœํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค. ๊ตฌ๋ช…๋ณดํŠธ๋Š” ์ž‘์•„์„œ ํ•œ ๋ฒˆ์— ์ตœ๋Œ€ 2๋ช…์”ฉ ๋ฐ–์— ํƒˆ ์ˆ˜ ์—†๊ณ , ๋ฌด๊ฒŒ ์ œํ•œ๋„ ์žˆ์Šต๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ์‚ฌ๋žŒ๋“ค์˜ ๋ชธ๋ฌด๊ฒŒ๊ฐ€ [70kg, 50kg, 80kg, 50kg]์ด๊ณ  ๊ตฌ๋ช…๋ณดํŠธ์˜ ๋ฌด๊ฒŒ ์ œํ•œ์ด 100kg์ด๋ผ๋ฉด 2๋ฒˆ์งธ ์‚ฌ๋žŒ๊ณผ 4๋ฒˆ์งธ ์‚ฌ๋žŒ์€ ๊ฐ™์ด ํƒˆ ์ˆ˜ ์žˆ์ง€๋งŒ 1๋ฒˆ์งธ ์‚ฌ๋žŒ๊ณผ 3๋ฒˆ์งธ ์‚ฌ๋žŒ์˜ ๋ฌด๊ฒŒ์˜ ํ•ฉ์€ 150kg์ด๋ฏ€๋กœ ๊ตฌ๋ช…๋ณดํŠธ์˜ ๋ฌด๊ฒŒ ์ œํ•œ์„ ์ดˆ๊ณผํ•˜์—ฌ ๊ฐ™์ด ํƒˆ ์ˆ˜ ์—†์Šต๋‹ˆ๋‹ค.

๊ตฌ๋ช…๋ณดํŠธ๋ฅผ ์ตœ๋Œ€ํ•œ ์ ๊ฒŒ ์‚ฌ์šฉํ•˜์—ฌ ๋ชจ๋“  ์‚ฌ๋žŒ์„ ๊ตฌ์ถœํ•˜๋ ค๊ณ  ํ•ฉ๋‹ˆ๋‹ค.

์‚ฌ๋žŒ๋“ค์˜ ๋ชธ๋ฌด๊ฒŒ๋ฅผ ๋‹ด์€ ๋ฐฐ์—ด people๊ณผ ๊ตฌ๋ช…๋ณดํŠธ์˜ ๋ฌด๊ฒŒ ์ œํ•œ limit๊ฐ€ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์งˆ ๋•Œ, ๋ชจ๋“  ์‚ฌ๋žŒ์„ ๊ตฌ์ถœํ•˜๊ธฐ ์œ„ํ•ด ํ•„์š”ํ•œ ๊ตฌ๋ช…๋ณดํŠธ ๊ฐœ์ˆ˜์˜ ์ตœ์†Ÿ๊ฐ’์„ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์ž‘์„ฑํ•ด์ฃผ์„ธ์š”.

์ œํ•œ ์‚ฌํ•ญ

  • ๋ฌด์ธ๋„์— ๊ฐ‡ํžŒ ์‚ฌ๋žŒ์€ 1๋ช… ์ด์ƒ 50,000๋ช… ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • ๊ฐ ์‚ฌ๋žŒ์˜ ๋ชธ๋ฌด๊ฒŒ๋Š” 40kg ์ด์ƒ 240kg ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • ๊ตฌ๋ช…๋ณดํŠธ์˜ ๋ฌด๊ฒŒ ์ œํ•œ์€ 40kg ์ด์ƒ 240kg ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • ๊ตฌ๋ช…๋ณดํŠธ์˜ ๋ฌด๊ฒŒ ์ œํ•œ์€ ํ•ญ์ƒ ์‚ฌ๋žŒ๋“ค์˜ ๋ชธ๋ฌด๊ฒŒ ์ค‘ ์ตœ๋Œ“๊ฐ’๋ณด๋‹ค ํฌ๊ฒŒ ์ฃผ์–ด์ง€๋ฏ€๋กœ ์‚ฌ๋žŒ๋“ค์„ ๊ตฌ์ถœํ•  ์ˆ˜ ์—†๋Š” ๊ฒฝ์šฐ๋Š” ์—†์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

peoplelimitreturn
[70, 50, 80, 50]1003
[70, 80, 50]1003

โœ๏ธํ’€์ด

๋‚˜๋Š” ์ตœ์†Œ์˜ ๊ฐœ์ˆ˜๋กœ ๋ณดํŠธ์— ์‚ฌ๋žŒ์„ ๋‘ ๋ช… ํƒœ์›Œ์•ผ ํ•˜๊ธฐ ๋•Œ๋ฌธ์—,
๋ฌด๊ฒŒ๊ฐ€ ๊ฐ€์žฅ ์ ๊ฒŒ ๋‚˜๊ฐ€๋Š” ์‚ฌ๋žŒ๊ณผ ๊ฐ€์žฅ ๋งŽ์ด ๋‚˜๊ฐ€๋Š” ์‚ฌ๋žŒ ๋‘ ๋ช…์„ ์ฐพ์•„ ํƒœ์šฐ๋Š” ๊ฒƒ์ด ๊ฐ€์žฅ ํšจ์œจ์ ์ผ ๊ฒƒ์ด๋ผ๋Š” ์ƒ๊ฐ์ด ๋“ค์—ˆ๋‹ค.

์ด๋ฅผ ๊ตฌํ˜„ํ•˜๊ธฐ ์œ„ํ•ด ์šฐ์„  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๊ฐ€ ๊ฐ€๋ฆฌํ‚ค๊ณ  ์žˆ๋˜ ์‚ฌ๋žŒ์€ ํ˜ผ์ž ๋ณดํŠธ์— ํƒœ์šฐ๋„๋ก ํ•˜์˜€๋‹ค.

๐Ÿšฉ์ฑ„์  ๊ฒฐ๊ณผ

์ด ํ’€์ด๋ฒ•์€ ๊ฐ ๋‹จ๊ณ„์—์„œ ์ตœ์ ์ด๋ผ๊ณ  ์ƒ๊ฐ๋˜๋Š” ๊ฒƒ์„ ์„ ํƒํ•ด ๋‚˜๊ฐ€๋Š” ๋ฐฉ์‹์ธ ๊ทธ๋ฆฌ๋”” ๋ฐฉ์‹์„ ์‚ฌ์šฉํ•œ ๊ฒƒ์œผ๋กœ, ํ•ญ์ƒ ์ „์ฒด ๋ฌธ์ œ์— ๋Œ€ํ•ด ์ตœ์ ์˜ ํ•ด๋ฅผ ๋ณด์žฅํ•˜์ง€๋Š” ์•Š๋Š”๋‹ค.
์ฆ‰, ๊ทธ๋ฆฌ๋””๋Š” ์ตœ์ ์˜ ํ•ด๋ฅผ ๋ณด์žฅํ•˜์ง€ ์•Š์ง€๋งŒ, ๋Œ€๋ถ€๋ถ„์˜ ๊ฒฝ์šฐ์—๋Š” ์ด๋ ‡๊ฒŒ ์ข‹์€ ๊ทผ์‚ฌ ํ•ด๋ฅผ ์ฐพ์„ ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ์ด๋‹ค.

์ด ๋ฌธ์ œ์—์„œ ์ด๋ ‡๊ฒŒ ๊ทธ๋ฆฌ๋””๋ฅผ ์‚ฌ์šฉํ•ด ์ข‹์€ ๊ฒฐ๊ณผ๋ฅผ ์–ป์„ ์ˆ˜ ์žˆ์ง€๋งŒ, ํ•ญ์ƒ ์ตœ์ ์˜ ํ•ด๋ฅผ ๋ณด์žฅํ•˜์ง€๋Š” ์•Š๋Š”๋‹ค๋Š” ๊ฒƒ์„ ์—ผ๋‘์— ๋‘์–ด์•ผ ํ•œ๋‹ค!


๐Ÿ”—๋ฌธ์ œ ๋งํฌ
๐Ÿ’ปRepository

profile
ํ›ˆ์‹น์˜ ๊ฐœ๋ฐœ์—ฌํ–‰

1๊ฐœ์˜ ๋Œ“๊ธ€

comment-user-thumbnail
2024๋…„ 8์›” 9์ผ

์˜ค์˜น ์žฌ๋ฐŒ์–ด์š”์˜น

๋‹ต๊ธ€ ๋‹ฌ๊ธฐ