deo2kim
๋งž์™œํ‹€
deo2kim
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ
    • CS
      • Algorithm
      • Data Structure
      • Network
      • DB
      • OS
    • Algorithm Problem
      • Python
      • JavaScript
    • Programming language
      • Python
      • JavaScript
    • Tool
      • Jquery
      • React
    • ๊ฐœ๋ฐœ
    • Infra

๋ธ”๋กœ๊ทธ ๋ฉ”๋‰ด

  • ํ™ˆ
  • ํƒœ๊ทธ
  • ๋ฐฉ๋ช…๋ก

๊ณต์ง€์‚ฌํ•ญ

์ธ๊ธฐ ๊ธ€

์ตœ๊ทผ ๋Œ“๊ธ€

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

๋ฐ˜์‘ํ˜•
hELLO ยท Designed By ์ •์ƒ์šฐ.
deo2kim

๋งž์™œํ‹€

[python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์ฟ ํ‚ค ๊ตฌ์ž…
Algorithm Problem/Python

[python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์ฟ ํ‚ค ๊ตฌ์ž…

2020. 9. 10. 20:28
๋ฐ˜์‘ํ˜•

๐Ÿค”๋ฌธ์ œ ํ•ด๊ฒฐ

Lv4

 

๊ธฐ์ค€์ ์„ ํ•˜๋‚˜ ์ •ํ•œ๋‹ค. 0๋ถ€ํ„ฐ ์ฟ ํ‚ค์˜ ๊ธธ์ด-1 ๊นŒ์ง€

๊ทธ ๊ธฐ์ค€์€ ์ฒซ์งธ ์•„๋“ค ๊ณผ์ž, ๊ธฐ์ค€ + 1์€ ๋‘˜์งธ ์•„๋“ค ๊ณผ์ž๋กœ ์‹œ์ž‘ํ•œ๋‹ค.

1. ์ฒซ์งธ์˜ ๊ณผ์ž๊ฐ€ ์ ์œผ๋ฏ€๋กœ ์ฒซ์งธ์—๊ฒŒ ๊ณผ์ž๋ฅผ ํ•˜๋‚˜ ๋” ์ค€๋‹ค.

2. ๋‘˜์งธ์˜ ๊ณผ์ž๊ฐ€ ๋” ์ ์œผ๋ฏ€๋กœ ๋‘˜์งธ์—๊ฒŒ ๊ณผ์ž๋ฅผ ํ•˜๋‚˜ ๋” ์ค€๋‹ค.

3. ์ฒซ์งธ์˜ ๊ณผ์ž๊ฐ€ ์ ์œผ๋ฏ€๋กœ ์ฒซ์งธ์—๊ฒŒ ๊ณผ์ž๋ฅผ ํ•˜๋‚˜ ๋” ์ค€๋‹ค.

4. ๋‘˜์งธ์˜ ๊ณผ์ž๊ฐ€ ๋” ์ ์œผ๋ฏ€๋กœ ๋‘˜์งธ์—๊ฒŒ ๊ณผ์ž๋ฅผ ํ•˜๋‚˜ ๋” ์ค€๋‹ค.

5. ๋‘˜์˜ ๊ณผ์ž๊ฐ€ ๊ฐ™์œผ๋ฏ€๋กœ ๊ฐ’์„ ์ €์žฅํ•˜๊ณ  ์ฒซ์งธ๋ถ€ํ„ฐ ๊ณผ์ž๋ฅผ ๋” ์ค˜๋ณธ๋‹ค. (๋‘˜์งธ ๋จผ์ € ์ค˜๋„ ๋œ๋‹ค.)

6. ๋‘˜์งธ์˜ ๊ณผ์ž๊ฐ€ ๋” ์ ์œผ๋ฏ€๋กœ ๋‘˜์งธ์—๊ฒŒ ๊ณผ์ž๋ฅผ ํ•˜๋‚˜ ๋” ์ค€๋‹ค.

7. ์ฒซ์งธ์˜ ๊ณผ์ž๊ฐ€ ๋” ์ ์–ด์„œ ์ฒซ์งธ์—๊ฒŒ ๊ณผ์ž๋ฅผ ๋” ์ฃผ๊ณ  ์‹ถ์ง€๋งŒ ๋” ์ด์ƒ ์ค„ ๊ณผ์ž๊ฐ€ ์—†๋‹ค.

8. ๋‹ค์Œ ๊ธฐ์ค€์„ ์žก๊ณ  ์œ„์˜ ๊ณผ์ •์„ ๋ฐ˜๋ณตํ•œ๋‹ค.

๋‹ค์Œ ๊ธฐ์ค€

๐Ÿ’จ 

 

๐Ÿ’ป์†Œ์Šค ์ฝ”๋“œ

def solution(cookie):
    answer = 0
    n = len(cookie)

    for i in range(n - 1):
        left_sum, left_idx = cookie[i], i
        right_sum, right_idx = cookie[i + 1], i + 1

        while True:
            if left_sum == right_sum:
                answer = max(answer, left_sum)
                # answer = max(answer, right_sum)
                
            if left_idx > 0 and left_sum <= right_sum:
                left_idx -= 1
                left_sum += cookie[left_idx]
            elif right_idx < n - 1 and right_sum <= left_sum:
                right_idx += 1
                right_sum += cookie[right_idx]
            else:
                break

    return answer

 

๐Ÿ“•๋ฌธ์ œ ํ™•์ธ

์ถœ์ฒ˜: ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค

๋งํฌ: https://programmers.co.kr/learn/courses/30/lessons/49995

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ์ฟ ํ‚ค ๊ตฌ์ž…

๊ณผ์ž๋ฅผ ๋ฐ”๊ตฌ๋‹ˆ ๋‹จ์œ„๋กœ ํŒŒ๋Š” ๊ฐ€๊ฒŒ๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ๊ฐ€๊ฒŒ๋Š” 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€ ์ฐจ๋ก€๋กœ ๋ฒˆํ˜ธ๊ฐ€ ๋ถ™์€ ๋ฐ”๊ตฌ๋‹ˆ N๊ฐœ๊ฐ€ ์ผ๋ ฌ๋กœ ๋‚˜์—ดํ•ด ๋†จ์Šต๋‹ˆ๋‹ค. ์ฒ ์ˆ˜๋Š” ๋‘ ์•„๋“ค์—๊ฒŒ ์ค„ ๊ณผ์ž๋ฅผ ์‚ฌ๋ คํ•ฉ๋‹ˆ๋‹ค. ์ฒซ์งธ ์•„๋“ค์—๊ฒŒ๋Š”

programmers.co.kr


๋ฌธ์ œ ์„ค๋ช…

๊ณผ์ž๋ฅผ ๋ฐ”๊ตฌ๋‹ˆ ๋‹จ์œ„๋กœ ํŒŒ๋Š” ๊ฐ€๊ฒŒ๊ฐ€ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ๊ฐ€๊ฒŒ๋Š” 1๋ฒˆ๋ถ€ํ„ฐ N๋ฒˆ๊นŒ์ง€ ์ฐจ๋ก€๋กœ ๋ฒˆํ˜ธ๊ฐ€ ๋ถ™์€ ๋ฐ”๊ตฌ๋‹ˆ N๊ฐœ๊ฐ€ ์ผ๋ ฌ๋กœ ๋‚˜์—ดํ•ด ๋†จ์Šต๋‹ˆ๋‹ค.

์ฒ ์ˆ˜๋Š” ๋‘ ์•„๋“ค์—๊ฒŒ ์ค„ ๊ณผ์ž๋ฅผ ์‚ฌ๋ คํ•ฉ๋‹ˆ๋‹ค. ์ฒซ์งธ ์•„๋“ค์—๊ฒŒ๋Š” l๋ฒˆ ๋ฐ”๊ตฌ๋‹ˆ๋ถ€ํ„ฐ m๋ฒˆ ๋ฐ”๊ตฌ๋‹ˆ๊นŒ์ง€, ๋‘˜์งธ ์•„๋“ค์—๊ฒŒ๋Š” m+1๋ฒˆ ๋ฐ”๊ตฌ๋‹ˆ๋ถ€ํ„ฐ r๋ฒˆ ๋ฐ”๊ตฌ๋‹ˆ๊นŒ์ง€๋ฅผ ์ฃผ๋ คํ•ฉ๋‹ˆ๋‹ค. ๋‹จ, ๋‘ ์•„๋“ค์ด ๋ฐ›์„ ๊ณผ์ž ์ˆ˜๋Š” ๊ฐ™์•„์•ผ ํ•ฉ๋‹ˆ๋‹ค(1 <= l <= m, m+1 <= r <= N). ์ฆ‰, A[i] ๋ฅผ i๋ฒˆ ๋ฐ”๊ตฌ๋‹ˆ์— ๋“ค์–ด์žˆ๋Š” ๊ณผ์ž ์ˆ˜๋ผ๊ณ  ํ–ˆ์„ ๋•Œ, A[l]+..+A[m] = A[m+1]+..+A[r] ๋ฅผ ๋งŒ์กฑํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

๊ฐ ๋ฐ”๊ตฌ๋‹ˆ ์•ˆ์— ๋“ค์€ ๊ณผ์ž ์ˆ˜๊ฐ€ ์ฐจ๋ก€๋กœ ๋“ค์€ ๋ฐฐ์—ด cookie๊ฐ€ ์ฃผ์–ด์งˆ ๋•Œ, ์กฐ๊ฑด์— ๋งž๊ฒŒ ๊ณผ์ž๋ฅผ ์‚ด ๊ฒฝ์šฐ ํ•œ ๋ช…์˜ ์•„๋“ค์—๊ฒŒ ์ค„ ์ˆ˜ ์žˆ๋Š” ๊ฐ€์žฅ ๋งŽ์€ ๊ณผ์ž ์ˆ˜๋ฅผ return ํ•˜๋Š” solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•ด์ฃผ์„ธ์š”. (๋‹จ, ์กฐ๊ฑด์— ๋งž๊ฒŒ ๊ณผ์ž๋ฅผ ๊ตฌ๋งคํ•  ์ˆ˜ ์—†๋‹ค๋ฉด 0์„ return ํ•ฉ๋‹ˆ๋‹ค)

์ œํ•œ์‚ฌํ•ญ

  • cookie์˜ ๊ธธ์ด๋Š” 1 ์ด์ƒ 2,000 ์ดํ•˜์ž…๋‹ˆ๋‹ค.
  • cookie์˜ ๊ฐ๊ฐ์˜ ์›์†Œ๋Š” 1 ์ด์ƒ 500 ์ดํ•˜์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

cookieresult

cookie result
[1,1,2,3] 3
[1,2,4,5] 0

์ž…์ถœ๋ ฅ ์˜ˆ ์„ค๋ช…

์ž…์ถœ๋ ฅ ์˜ˆ #1

์ฒซ์งธ ์•„๋“ค์—๊ฒŒ 2, 3๋ฒˆ ๋ฐ”๊ตฌ๋‹ˆ๋ฅผ, ๋‘˜์งธ ์•„๋“ค์—๊ฒŒ 4๋ฒˆ ๋ฐ”๊ตฌ๋‹ˆ๋ฅผ ์‚ฌ์ฃผ๋ฉด ๋‘ ์•„๋“ค์€ ๊ฐ๊ฐ ๊ณผ์ž 3๊ฐœ๋ฅผ ๋ฐ›์Šต๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ #2

์ฃผ์–ด์ง„ ์กฐ๊ฑด์— ๋งž๊ฒŒ ๊ณผ์ž๋ฅผ ์‚ด ๋ฐฉ๋ฒ•์ด ์—†์Šต๋‹ˆ๋‹ค.

๋ฐ˜์‘ํ˜•
์ €์ž‘์žํ‘œ์‹œ ๋น„์˜๋ฆฌ ๋ณ€๊ฒฝ๊ธˆ์ง€

'Algorithm Problem > Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€

[python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ๋ธ”๋ก ๊ฒŒ์ž„(2019 KAKAO BLIND RECRUITMENT)  (3) 2020.09.11
[python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์•ผ๊ทผ ์ง€์ˆ˜  (0) 2020.09.11
[python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ๋””์Šคํฌ ์ปจํŠธ๋กค๋Ÿฌ  (0) 2020.09.10
[python] ๋ฐฑ์ค€ - 2343. ๊ธฐํƒ€ ๋ ˆ์Šจ  (5) 2020.09.09
[python] ๋ฐฑ์ค€ - 1926. ๊ทธ๋ฆผ  (0) 2020.09.08
    'Algorithm Problem/Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
    • [python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ๋ธ”๋ก ๊ฒŒ์ž„(2019 KAKAO BLIND RECRUITMENT)
    • [python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ์•ผ๊ทผ ์ง€์ˆ˜
    • [python] ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค - ๋””์Šคํฌ ์ปจํŠธ๋กค๋Ÿฌ
    • [python] ๋ฐฑ์ค€ - 2343. ๊ธฐํƒ€ ๋ ˆ์Šจ
    deo2kim
    deo2kim
    ์ฝ”๋”ฉ ๊ธฐ๋กํ•˜๊ธฐ

    ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”