๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
โŒจ๏ธ Language/swift

[Swift] ๋ฐฑ์ค€ 1966๋ฒˆ - ํ”„๋ฆฐํ„ฐ ํ

by hyebin (Helia) 2023. 3. 24.
๋ฐ˜์‘ํ˜•
๋ฐฑ์ค€ ๋ฌธ์ œ ๋ชจ์Œ

๋ฌธ์ œ ๋งํฌ

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

 

1966๋ฒˆ: ํ”„๋ฆฐํ„ฐ ํ

์—ฌ๋Ÿฌ๋ถ„๋„ ์•Œ๋‹ค์‹œํ”ผ ์—ฌ๋Ÿฌ๋ถ„์˜ ํ”„๋ฆฐํ„ฐ ๊ธฐ๊ธฐ๋Š” ์—ฌ๋Ÿฌ๋ถ„์ด ์ธ์‡„ํ•˜๊ณ ์ž ํ•˜๋Š” ๋ฌธ์„œ๋ฅผ ์ธ์‡„ ๋ช…๋ น์„ ๋ฐ›์€ ‘์ˆœ์„œ๋Œ€๋กœ’, ์ฆ‰ ๋จผ์ € ์š”์ฒญ๋œ ๊ฒƒ์„ ๋จผ์ € ์ธ์‡„ํ•œ๋‹ค. ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๋ฌธ์„œ๊ฐ€ ์Œ“์ธ๋‹ค๋ฉด Queue ์ž๋ฃŒ๊ตฌ์กฐ์—

www.acmicpc.net

 

๋ฌธ์ œ

์—ฌ๋Ÿฌ๋ถ„๋„ ์•Œ๋‹ค์‹œํ”ผ ์—ฌ๋Ÿฌ๋ถ„์˜ ํ”„๋ฆฐํ„ฐ ๊ธฐ๊ธฐ๋Š” ์—ฌ๋Ÿฌ๋ถ„์ด ์ธ์‡„ํ•˜๊ณ ์ž ํ•˜๋Š” ๋ฌธ์„œ๋ฅผ ์ธ์‡„ ๋ช…๋ น์„ ๋ฐ›์€ ‘์ˆœ์„œ๋Œ€๋กœ’, ์ฆ‰ ๋จผ์ € ์š”์ฒญ๋œ ๊ฒƒ์„ ๋จผ์ € ์ธ์‡„ํ•œ๋‹ค. ์—ฌ๋Ÿฌ ๊ฐœ์˜ ๋ฌธ์„œ๊ฐ€ ์Œ“์ธ๋‹ค๋ฉด Queue ์ž๋ฃŒ๊ตฌ์กฐ์— ์Œ“์—ฌ์„œ FIFO - First In First Out - ์— ๋”ฐ๋ผ ์ธ์‡„๊ฐ€ ๋˜๊ฒŒ ๋œ๋‹ค. ํ•˜์ง€๋งŒ ์ƒ๊ทผ์ด๋Š” ์ƒˆ๋กœ์šด ํ”„๋ฆฐํ„ฐ๊ธฐ ๋‚ด๋ถ€ ์†Œํ”„ํŠธ์›จ์–ด๋ฅผ ๊ฐœ๋ฐœํ•˜์˜€๋Š”๋ฐ, ์ด ํ”„๋ฆฐํ„ฐ๊ธฐ๋Š” ๋‹ค์Œ๊ณผ ๊ฐ™์€ ์กฐ๊ฑด์— ๋”ฐ๋ผ ์ธ์‡„๋ฅผ ํ•˜๊ฒŒ ๋œ๋‹ค.

  1. ํ˜„์žฌ Queue์˜ ๊ฐ€์žฅ ์•ž์— ์žˆ๋Š” ๋ฌธ์„œ์˜ ‘์ค‘์š”๋„’๋ฅผ ํ™•์ธํ•œ๋‹ค.
  2. ๋‚˜๋จธ์ง€ ๋ฌธ์„œ๋“ค ์ค‘ ํ˜„์žฌ ๋ฌธ์„œ๋ณด๋‹ค ์ค‘์š”๋„๊ฐ€ ๋†’์€ ๋ฌธ์„œ๊ฐ€ ํ•˜๋‚˜๋ผ๋„ ์žˆ๋‹ค๋ฉด, ์ด ๋ฌธ์„œ๋ฅผ ์ธ์‡„ํ•˜์ง€ ์•Š๊ณ  Queue์˜ ๊ฐ€์žฅ ๋’ค์— ์žฌ๋ฐฐ์น˜ํ•œ๋‹ค. ๊ทธ๋ ‡์ง€ ์•Š๋‹ค๋ฉด ๋ฐ”๋กœ ์ธ์‡„๋ฅผ ํ•œ๋‹ค.

์˜ˆ๋ฅผ ๋“ค์–ด Queue์— 4๊ฐœ์˜ ๋ฌธ์„œ(A B C D)๊ฐ€ ์žˆ๊ณ , ์ค‘์š”๋„๊ฐ€ 2 1 4 3 ๋ผ๋ฉด C๋ฅผ ์ธ์‡„ํ•˜๊ณ , ๋‹ค์Œ์œผ๋กœ D๋ฅผ ์ธ์‡„ํ•˜๊ณ  A, B๋ฅผ ์ธ์‡„ํ•˜๊ฒŒ ๋œ๋‹ค.

์—ฌ๋Ÿฌ๋ถ„์ด ํ•  ์ผ์€, ํ˜„์žฌ Queue์— ์žˆ๋Š” ๋ฌธ์„œ์˜ ์ˆ˜์™€ ์ค‘์š”๋„๊ฐ€ ์ฃผ์–ด์กŒ์„ ๋•Œ, ์–ด๋–ค ํ•œ ๋ฌธ์„œ๊ฐ€ ๋ช‡ ๋ฒˆ์งธ๋กœ ์ธ์‡„๋˜๋Š”์ง€ ์•Œ์•„๋‚ด๋Š” ๊ฒƒ์ด๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด ์œ„์˜ ์˜ˆ์—์„œ C๋ฌธ์„œ๋Š” 1๋ฒˆ์งธ๋กœ, A๋ฌธ์„œ๋Š” 3๋ฒˆ์งธ๋กœ ์ธ์‡„๋˜๊ฒŒ ๋œ๋‹ค.

์ž…๋ ฅ

์ฒซ ์ค„์— ํ…Œ์ŠคํŠธ์ผ€์ด์Šค์˜ ์ˆ˜๊ฐ€ ์ฃผ์–ด์ง„๋‹ค. ๊ฐ ํ…Œ์ŠคํŠธ์ผ€์ด์Šค๋Š” ๋‘ ์ค„๋กœ ์ด๋ฃจ์–ด์ ธ ์žˆ๋‹ค.

ํ…Œ์ŠคํŠธ์ผ€์ด์Šค์˜ ์ฒซ ๋ฒˆ์งธ ์ค„์—๋Š” ๋ฌธ์„œ์˜ ๊ฐœ์ˆ˜ N(1 ≤ N ≤ 100)๊ณผ, ๋ช‡ ๋ฒˆ์งธ๋กœ ์ธ์‡„๋˜์—ˆ๋Š”์ง€ ๊ถ๊ธˆํ•œ ๋ฌธ์„œ๊ฐ€ ํ˜„์žฌ Queue์—์„œ ๋ช‡ ๋ฒˆ์งธ์— ๋†“์—ฌ ์žˆ๋Š”์ง€๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์ •์ˆ˜ M(0 ≤ M < N)์ด ์ฃผ์–ด์ง„๋‹ค. ์ด๋•Œ ๋งจ ์™ผ์ชฝ์€ 0๋ฒˆ์งธ๋ผ๊ณ  ํ•˜์ž. ๋‘ ๋ฒˆ์งธ ์ค„์—๋Š” N๊ฐœ ๋ฌธ์„œ์˜ ์ค‘์š”๋„๊ฐ€ ์ฐจ๋ก€๋Œ€๋กœ ์ฃผ์–ด์ง„๋‹ค. ์ค‘์š”๋„๋Š” 1 ์ด์ƒ 9 ์ดํ•˜์˜ ์ •์ˆ˜์ด๊ณ , ์ค‘์š”๋„๊ฐ€ ๊ฐ™์€ ๋ฌธ์„œ๊ฐ€ ์—ฌ๋Ÿฌ ๊ฐœ ์žˆ์„ ์ˆ˜๋„ ์žˆ๋‹ค.

์ถœ๋ ฅ

๊ฐ ํ…Œ์ŠคํŠธ ์ผ€์ด์Šค์— ๋Œ€ํ•ด ๋ฌธ์„œ๊ฐ€ ๋ช‡ ๋ฒˆ์งธ๋กœ ์ธ์‡„๋˜๋Š”์ง€ ์ถœ๋ ฅํ•œ๋‹ค.

์ž…์ถœ๋ ฅ ์˜ˆ์‹œ

์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ถ„๋ฅ˜

  • ๊ตฌํ˜„
  • ์ž๋ฃŒ๊ตฌ์กฐ
  • ์‹œ๋ฎฌ๋ ˆ์ด์…˜
  • ํ

๋ฌธ์ œ ํ’€์ด

  • ๋ฌธ์„œ์˜ ๊ฐœ์ˆ˜ N๊ณผ ๊ถ๊ธˆํ•œ ๋ฌธ์„œ์˜ ํ˜„์žฌ ์œ„์น˜ M์„ ์ž…๋ ฅ๋ฐ›๋Š”๋‹ค.
  • input์— ๋ฌธ์„œ์˜ ์ค‘์š”๋„๋ฅผ ์ €์žฅํ•œ๋‹ค.
  • input์— ์ €์žฅ๋œ ์š”์†Œ๋“ค ์—์„œ (์ค‘์š”๋„, ์œ„์น˜)๋ฅผ ๋ฐฐ์—ด์— ๋‹ด์•„ queue์— ์ €์žฅํ•œ๋‹ค.
  • input์„ ์˜ค๋ฆ„์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌํ•œ๋‹ค.
  • M๋ฒˆ์งธ ์š”์†Œ๋ฅผ ์‚ญ์ œํ•  ๋•Œ๊นŒ์ง€ while ๋ฌธ์„ ๋™์ž‘ํ•œ๋‹ค.
    • queue์˜ ์ฒซ ๋ฒˆ์งธ ์š”์†Œ์˜ ์ค‘์š”๋„๊ฐ€ input์˜ ๋งˆ์ง€๋ง‰ ์š”์†Œ์˜ ๊ฐ’ ์ฆ‰, ๊ฐ€์žฅ ๋†’์€ ์ค‘์š”๋„์™€ ๊ฐ™๋‹ค๋ฉด, result ๋ณ€์ˆ˜๋ฅผ 1 ์ฆ๊ฐ€์‹œํ‚จ๋‹ค.
      • queue์˜ ์ฒซ ๋ฒˆ์งธ ์š”์†Œ์˜ ์œ„์น˜๊ฐ€ M๊ณผ ๊ฐ™๋‹ค๋ฉด result๋ฅผ ์ถœ๋ ฅํ•˜๊ณ  while ๋ฌธ์„ ์ข…๋ฃŒํ•œ๋‹ค.
      • ์•„๋‹ˆ๋ผ๋ฉด queue์—์„œ๋Š” ์ฒซ ๋ฒˆ์งธ ์š”์†Œ๋ฅผ input์—์„œ๋Š” ๋งˆ์ง€๋ง‰ ์š”์†Œ๋ฅผ ์‚ญ์ œํ•œ๋‹ค.
    • ์•„๋‹ˆ๋ผ๋ฉด queue์—์„œ ์ฒซ ๋ฒˆ์งธ ์š”์†Œ๋ฅผ ์‚ญ์ œํ•œ ํ›„, queue์˜ ๋งˆ์ง€๋ง‰์— ์ถ”๊ฐ€ํ•œ๋‹ค. 

์†Œ์Šค์ฝ”๋“œ

let n = Int(readLine()!)!
for _ in 0..<n {
    let NM = readLine()!.split(separator: " ").map{Int(String($0))!}
    var input = readLine()!.split(separator: " ").map{Int(String($0))!}
    var queue = [(Int, Int)]()
    var result = 0
    
    for (i, value) in input.enumerated() {
        queue.append((value, i))
    }
    
    input.sort()
    
    while true{
        if queue[0].0 == input.last {
            result += 1
            if queue[0].1 == NM[1] {
                print(result)
                break
            }else {
                queue.removeFirst()
                input.removeLast()
            }
        }else {
            queue.append(queue.removeFirst())
        }
    }
}
  • 12ms
๋ฐ˜์‘ํ˜•