sladuf
200
sladuf
์ „์ฒด ๋ฐฉ๋ฌธ์ž
์˜ค๋Š˜
์–ด์ œ
  • ๋ถ„๋ฅ˜ ์ „์ฒด๋ณด๊ธฐ (83)
    • ๐Ÿ“š Programming (32)
      • Swift (13)
      • JAVA (2)
      • Python (6)
      • SQL (6)
      • Web (5)
    • ๐Ÿ“ฑ iOS (25)
      • Base (7)
      • SwiftUI (9)
      • UIKit (7)
      • ์ธ๊ฐ• & ์ฑ… (2)
    • ๐Ÿ”— Algorithm (20)
      • Python (12)
      • Swift (3)
      • Tip (5)
    • ๐Ÿ—‚ ETC (6)

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

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

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

์ธ๊ธฐ ๊ธ€

ํƒœ๊ทธ

  • Swift
  • ์Šค์œ„ํ”„ํŠธ

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

์ตœ๊ทผ ๊ธ€

ํ‹ฐ์Šคํ† ๋ฆฌ

๊ธ€์“ฐ๊ธฐ ์„ค์ •
hELLO ยท Designed By ์ •์ƒ์šฐ.
sladuf

200

[Python] ๋ฐฑ์ค€ 6549
๐Ÿ”— Algorithm/Python

[Python] ๋ฐฑ์ค€ 6549

2021. 2. 20. 23:40

๊ตํ›ˆ : ํ”Œ๋ž˜๋ผ๊ณ  ๊ฒ๋จน์ง€ ๋ง์ž

 

 

 

 

 

stack์„ ์ด์šฉํ•ด์„œ ํ’€์—ˆ๋‹ค

stack ์‚ฝ์ž… : index์™€ ๋†’์ด(h)

์›๋ฆฌ : ํ˜„์žฌ index๋ณด๋‹ค stack์— ์žˆ๋Š” index(๋‚˜๋ณด๋‹ค ์™ผ์ชฝ)์˜ h๊ฐ€ ๋” ํฌ๋ฉด ํ˜„์žฌ index์˜ h๊ฐ’์œผ๋กœ ์™ผ์ชฝ๋„ ํฌํ•จํ•  ์ˆ˜ ์žˆ๋‹ค.

 

๋”๋ณด๊ธฐ
   
   
   

์—ฌ๊ธฐ์„œ ์˜ค๋ฅธ์ชฝ์˜ ๋†’์ด(2) ๋กœ ์™ผ์ชฝ์„ ํฌํ•จํ•˜์—ฌ ๋„“์ด๊ฐ€ 4๊ฐ€ ๋  ์ˆ˜ ์žˆ๋‹ค. 

 

 

์ด ์›๋ฆฌ๋ฅผ ์ด์šฉํ•ด stack์œผ๋กœ ํ’€ ์ˆ˜ ์žˆ์—ˆ๋‹ค!

 

import sys

while True:
	#๋งˆ์ง€๋ง‰์— stack์— ์žˆ๋Š” ๊ฐ’์„๋“ค ๋‹ค ๊บผ๋‚ด๊ธฐ ์œ„ํ•ด ๋งˆ์ง€๋ง‰ h๊ฐ’์€ 0
    h = list(map(int, sys.stdin.readline().split())) + [0]
    if h[0] == 0:
        break
    n = h[0]
    stack = [(1,h[1])]
    res = 0
    for i in range(2,n+2):
        w = i
        #๋‚˜๋ณด๋‹ค stack์— ์žˆ๋Š” h๊ฐ€ ๋” ๋†’์œผ๋ฉด ๊บผ๋‚ด์„œ (๋‚˜์˜ ๋†’์ด * ๋„ˆ๋น„)
        while stack and stack[-1][1] > h[i]:
            w, hi = stack.pop()
            res = max(res, (i-w)*hi)
        stack.append((w, h[i]))
    print(res)

 

์˜ˆ์ œ๋กœ ์‹คํ–‰ํ–ˆ์„ ๋•Œ res์— ๋“ค์–ด๊ฐ€๋Š” ์ง์‚ฌ๊ฐํ˜•์˜ ๋„“์ด

 

 

 

์ €์ž‘์žํ‘œ์‹œ (์ƒˆ์ฐฝ์—ด๋ฆผ)

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

[Python] ๋ฐฑ์ค€ 2089  (0) 2021.03.04
[Python] ๋ฐฑ์ค€ 1442  (0) 2021.02.25
[Python] ๋ฐฑ์ค€ 2606  (0) 2020.09.01
[Python] ๋ฐฑ์ค€ 1260  (0) 2020.08.27
[Python] ๋ฐฑ์ค€ 2231  (0) 2020.05.03
    '๐Ÿ”— Algorithm/Python' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
    • [Python] ๋ฐฑ์ค€ 2089
    • [Python] ๋ฐฑ์ค€ 1442
    • [Python] ๋ฐฑ์ค€ 2606
    • [Python] ๋ฐฑ์ค€ 1260
    sladuf
    sladuf

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