[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ํฐ ์ˆ˜ ๋งŒ๋“ค๊ธฐ/ ํŒŒ์ด์ฌ/ Python / Stack
Algorithm/Programmers

[ํ”„๋กœ๊ทธ๋ž˜๋จธ์Šค] ํฐ ์ˆ˜ ๋งŒ๋“ค๊ธฐ/ ํŒŒ์ด์ฌ/ Python / Stack

728x90
๋ฐ˜์‘ํ˜•

 

๐Ÿ’กsolutions )

๐Ÿ’ฌ ์ด๋ฏธ k๊ฐœ ๋งŒํผ์˜ ์ˆซ์ž ์‚ญ์ œ๋ฅผ ์™„๋ฃŒํ•œ ๊ฒฝ์šฐ์—๋Š” s ์Šคํƒ์— ๋ชจ๋‘ ๋„ฃ๊ธฐ

๐Ÿ’ฌ ์ฒซ๋ฒˆ์งธ ์ˆซ์ž๋Š” ๋จผ์ € ๋„ฃ๊ณ  ์‹œ์ž‘ํ•˜๋ฉฐ, while๋ฌธ ์•ˆ์—์„œ s ์Šคํƒ์— ๋„ฃ์–ด์•ผ ํ•˜๋Š” ์ˆซ์ž(i)์™€ ๊ธฐ์กด s ์Šคํƒ์— ๋‹ด๊ฒจ์žˆ๋Š” ์ˆซ์ž๋“ค์˜ ํฌ๊ธฐ๋ฅผ ๋น„๊ตํ•˜๊ธฐ -> i๊ฐ€ ๊ธฐ์กด ์ˆซ์ž๋ณด๋‹ค ํฌ๋ฉด ๊ธฐ์กด ์ˆซ์ž ์ œ๊ฑฐ(popํ•˜๊ณ  cnt +1)

๐Ÿ’ฌ ์ด๋ฏธ k๊ฐœ๋ฅผ ๋ชจ๋‘ ์‚ญ์ œํ•˜๊ฑฐ๋‚˜ i๊ฐ€ ๊ธฐ์กด ์ˆซ์ž๋ณด๋‹ค ์ž‘๊ฑฐ๋‚˜ ๊ฐ™์€ ๊ฒฝ์šฐ์—๋Š” break๋ฅผ ๊ฑธ์–ด while๋ฌธ ์ค‘๋‹จ

๐Ÿ’ฌ ์ˆซ์ž๋ฅผ ๋‹ค ๋„ฃ์—ˆ๋Š”๋ฐ ์•„์ง ์ œ๊ฑฐํ•ด์•ผ ํ•  k๊ฐ€ ๋‚จ์•„ ์žˆ๋Š” ๊ฒฝ์šฐ, ๋งจ ๋’ค์—์„œ๋ถ€ํ„ฐ pop์œผ๋กœ ๋‚จ์€ k๊ฐœ์ˆ˜ ๋งŒํผ ์ˆซ์ž ์‚ญ์ œ

๐Ÿ’ฌ ์ฐธ๊ณ ๋กœ ๋‚˜์˜ ๊ฒฝ์šฐ ์ฒซ ์‹œ๋„์—์„  ๋งˆ์ง€๋ง‰ 12๋ฒˆ ์ผ€์ด์Šค ํ†ต๊ณผํ•˜์ง€ ๋ชป ํ–ˆ๊ณ , ์•„๋ž˜ ๋‘ ๊ฐ€์ง€ ํ…Œ์ŠคํŠธ์ผ€์ด์Šค๋ฅผ ๋„ฃ์–ด ์ฝ”๋“œ๋ฅผ ์ˆ˜์ •ํ•œ ํ›„ ํ†ต๊ณผํ•  ์ˆ˜ ์žˆ์—ˆ๋‹ค.

# 12๋ฒˆ ๋Œ€๋น„ ํ…Œ์ŠคํŠธ์ผ€์ด์Šค
# 999, 2 => 9
# 111119, 3 => 119

 

๐ŸŽซcode )

def solution(number, k):
    s = []
    cnt = 0
    for i in number:
        if cnt == k:
            s.append(i)
        else:
            if not s:
                s.append(i)
                print(s)
            else:
                while s:
                    if cnt == k or i <= s[-1]:
                        break
                    if i > s[-1]:
                        s.pop()
                        cnt += 1
                s.append(i)

    while cnt !=k:
        s.pop()
        cnt += 1
    return ''.join(s)

 

 

๐Ÿ“Œ description )

๋ฌธ์ œ์ถœ์ฒ˜ : programmers.co.kr/learn/courses/30/lessons/42883?language=python3

 

์ฝ”๋”ฉํ…Œ์ŠคํŠธ ์—ฐ์Šต - ํฐ ์ˆ˜ ๋งŒ๋“ค๊ธฐ

 

programmers.co.kr

๋ฌธ์ œ ์„ค๋ช…

์–ด๋–ค ์ˆซ์ž์—์„œ k๊ฐœ์˜ ์ˆ˜๋ฅผ ์ œ๊ฑฐํ–ˆ์„ ๋•Œ ์–ป์„ ์ˆ˜ ์žˆ๋Š” ๊ฐ€์žฅ ํฐ ์ˆซ์ž๋ฅผ ๊ตฌํ•˜๋ ค ํ•ฉ๋‹ˆ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด, ์ˆซ์ž 1924์—์„œ ์ˆ˜ ๋‘ ๊ฐœ๋ฅผ ์ œ๊ฑฐํ•˜๋ฉด [19, 12, 14, 92, 94, 24] ๋ฅผ ๋งŒ๋“ค ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค. ์ด ์ค‘ ๊ฐ€์žฅ ํฐ ์ˆซ์ž๋Š” 94 ์ž…๋‹ˆ๋‹ค.

๋ฌธ์ž์—ด ํ˜•์‹์œผ๋กœ ์ˆซ์ž number์™€ ์ œ๊ฑฐํ•  ์ˆ˜์˜ ๊ฐœ์ˆ˜ k๊ฐ€ solution ํ•จ์ˆ˜์˜ ๋งค๊ฐœ๋ณ€์ˆ˜๋กœ ์ฃผ์–ด์ง‘๋‹ˆ๋‹ค. number์—์„œ k ๊ฐœ์˜ ์ˆ˜๋ฅผ ์ œ๊ฑฐํ–ˆ์„ ๋•Œ ๋งŒ๋“ค ์ˆ˜ ์žˆ๋Š” ์ˆ˜ ์ค‘ ๊ฐ€์žฅ ํฐ ์ˆซ์ž๋ฅผ ๋ฌธ์ž์—ด ํ˜•ํƒœ๋กœ return ํ•˜๋„๋ก solution ํ•จ์ˆ˜๋ฅผ ์™„์„ฑํ•˜์„ธ์š”.

์ œํ•œ ์กฐ๊ฑด

  • number๋Š” 1์ž๋ฆฌ ์ด์ƒ, 1,000,000์ž๋ฆฌ ์ดํ•˜์ธ ์ˆซ์ž์ž…๋‹ˆ๋‹ค.
  • k๋Š” 1 ์ด์ƒ number์˜ ์ž๋ฆฟ์ˆ˜ ๋ฏธ๋งŒ์ธ ์ž์—ฐ์ˆ˜์ž…๋‹ˆ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ

 

 

๋ฐ˜์‘ํ˜•