λ°±μ€€ - 크게 λ§Œλ“€κΈ°(Swift)

2022. 11. 3. 11:47ㆍAlgorithm

λ°±μ€€ - ν¬κ²Œ λ§Œλ“€κΈ°(Swift)

 

 

 λ¬Έμ œ μ„€λͺ…

 

https://www.acmicpc.net/problem/2812

 

2812번: 크게 λ§Œλ“€κΈ°

N자리 μˆ«μžκ°€ μ£Όμ–΄μ‘Œμ„ λ•Œ, μ—¬κΈ°μ„œ 숫자 K개λ₯Ό μ§€μ›Œμ„œ 얻을 수 μžˆλŠ” κ°€μž₯ 큰 수λ₯Ό κ΅¬ν•˜λŠ” ν”„λ‘œκ·Έλž¨μ„ μž‘μ„±ν•˜μ‹œμ˜€.

www.acmicpc.net

 

 λ‚˜μ˜ 풀이

 

μ²˜μŒμ—λŠ” 큰 μˆ«μžκ°€ μ•žμ— μžˆμ–΄μ•Όν•œλ‹€λŠ” 것을 μ•Œμ•˜κΈ°μ— 투 ν¬μΈν„°λ‘œ μ΄μš©ν•΄μ„œ 문제λ₯Ό ν’€μ—ˆλ‹€. ν•˜μ§€λ§Œ 500,000인 μƒνƒœμ—μ„œ 투 포인터λ₯Ό 계속 μ•žμœΌλ‘œ λ¦¬μ…‹ν•˜λ©΄μ„œ λŒλ¦¬λŠ” 것은 λ§λ„μ•ˆλ˜λŠ” μ‹œκ°„λ³΅μž‘λ„λ₯Ό 결과둜 λ‚΄λ†“λŠ”λ‹€.

 

이 λ•Œλ¬Έμ— λ‹€λ₯Έ 풀이λ₯Ό μ°Έκ³ ν•˜λ‹€κ°€ μŠ€νƒμ„ μ‚¬μš©ν•˜λŠ” 것을 μ•Œκ²Œλ˜μ—ˆλ‹€.

μŠ€νƒμ΄λΌλŠ” 좔가적인 자료ꡬ쑰λ₯Ό μ‚¬μš©ν•¨μœΌλ‘œμ¨ μƒˆλ‘œ λ“€μ–΄μ˜€λŠ” 값에 λŒ€ν•΄μ„œλŠ” λ§ˆμ§€λ§‰κ°’κ³Ό λΉ„κ΅ν•˜λŠ” λ‘œμ§μ„ 담을 수 있게 λ˜μ—ˆλ‹€. 

(기쑴의 투 ν¬μΈν„°λŠ” ν•œλ²ˆ 숫자λ₯Ό λΉΌλ©΄ μ²˜μŒλΆ€ν„° λ‹€μ‹œ μ‹œμž‘ν–ˆκΈ°μ— μ‹œκ°„μ΄ˆκ³Όκ°€ λ‚˜μ™”λ‹€.)

 

λ§ˆμ§€λ§‰μ— 0..<k에 λŒ€ν•΄μ„œ 또 μ œκ±°ν•˜λŠ” μ΄μœ λŠ” λ‹€μŒκ°’μ΄ 더 큰 값은 μ—†μœΌλ©΄μ„œ 제거λ₯Ό ν•΄μ•Όν•  λ•Œμ΄κΈ° λ•Œλ¬Έμ— 맨 λ§ˆμ§€λ§‰μ΄ 제일 μž‘μ€ μˆ«μžμ΄λ―€λ‘œ μ§€μš°λŠ” 것이닀.

 

 

 

import Foundation

let input = readLine()!.components(separatedBy:" ").map{Int($0)!}

let n = input[0]
var k = input[1]

var arr = readLine()!.map{Int(String($0))!}

var stack: [Int] = []

for x in arr {
    while k > 0 && !stack.isEmpty && stack.last! < x {
        stack.removeLast()
        k -= 1
    }
    stack.append(x)
}

(0..<k).forEach { _ in
    stack.removeLast()
}

print(stack.map{String($0)}.joined())

 

 

 

 

 ν”Όλ“œλ°±

 

μŠ€νƒ 자료ꡬ쑰λ₯Ό μ™œ μƒκ°ν•˜μ§€ λͺ»ν–ˆλ‚˜ μ‹Άλ‹€.. μ’€ 더 μœ μ—°ν•˜κ²Œ μƒκ°ν•˜λŠ” λŠ₯λ ₯을 κΈΈλŸ¬μ•Όκ² λ‹€.

 

 

'Algorithm' μΉ΄ν…Œκ³ λ¦¬μ˜ λ‹€λ₯Έ κΈ€

λ°±μ€€ - μ„Όμ„œ(Swift)  (0) 2022.11.04
λ°±μ€€ - 곡항(Swift)  (0) 2022.11.03
λ°±μ€€ - 빡집(Swift)  (0) 2022.11.01
κ²Œμž„μ„ λ§Œλ“  동쀀이  (0) 2022.10.31
λ°±μ€€ - 병든 λ‚˜μ΄νŠΈ(Swift)  (0) 2022.10.31