๋ฐฑ์ค ๋ฌธ์ ๋ชจ์
๋ฌธ์ ๋งํฌ
https://www.acmicpc.net/problem/1966
1966๋ฒ: ํ๋ฆฐํฐ ํ
์ฌ๋ฌ๋ถ๋ ์๋ค์ํผ ์ฌ๋ฌ๋ถ์ ํ๋ฆฐํฐ ๊ธฐ๊ธฐ๋ ์ฌ๋ฌ๋ถ์ด ์ธ์ํ๊ณ ์ ํ๋ ๋ฌธ์๋ฅผ ์ธ์ ๋ช ๋ น์ ๋ฐ์ ‘์์๋๋ก’, ์ฆ ๋จผ์ ์์ฒญ๋ ๊ฒ์ ๋จผ์ ์ธ์ํ๋ค. ์ฌ๋ฌ ๊ฐ์ ๋ฌธ์๊ฐ ์์ธ๋ค๋ฉด Queue ์๋ฃ๊ตฌ์กฐ์
www.acmicpc.net
๋ฌธ์
์ฌ๋ฌ๋ถ๋ ์๋ค์ํผ ์ฌ๋ฌ๋ถ์ ํ๋ฆฐํฐ ๊ธฐ๊ธฐ๋ ์ฌ๋ฌ๋ถ์ด ์ธ์ํ๊ณ ์ ํ๋ ๋ฌธ์๋ฅผ ์ธ์ ๋ช
๋ น์ ๋ฐ์ ‘์์๋๋ก’, ์ฆ ๋จผ์ ์์ฒญ๋ ๊ฒ์ ๋จผ์ ์ธ์ํ๋ค. ์ฌ๋ฌ ๊ฐ์ ๋ฌธ์๊ฐ ์์ธ๋ค๋ฉด Queue ์๋ฃ๊ตฌ์กฐ์ ์์ฌ์ FIFO - First In First Out - ์ ๋ฐ๋ผ ์ธ์๊ฐ ๋๊ฒ ๋๋ค. ํ์ง๋ง ์๊ทผ์ด๋ ์๋ก์ด ํ๋ฆฐํฐ๊ธฐ ๋ด๋ถ ์ํํธ์จ์ด๋ฅผ ๊ฐ๋ฐํ์๋๋ฐ, ์ด ํ๋ฆฐํฐ๊ธฐ๋ ๋ค์๊ณผ ๊ฐ์ ์กฐ๊ฑด์ ๋ฐ๋ผ ์ธ์๋ฅผ ํ๊ฒ ๋๋ค.
- ํ์ฌ Queue์ ๊ฐ์ฅ ์์ ์๋ ๋ฌธ์์ ‘์ค์๋’๋ฅผ ํ์ธํ๋ค.
- ๋๋จธ์ง ๋ฌธ์๋ค ์ค ํ์ฌ ๋ฌธ์๋ณด๋ค ์ค์๋๊ฐ ๋์ ๋ฌธ์๊ฐ ํ๋๋ผ๋ ์๋ค๋ฉด, ์ด ๋ฌธ์๋ฅผ ์ธ์ํ์ง ์๊ณ 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์ ๋ง์ง๋ง์ ์ถ๊ฐํ๋ค.
- queue์ ์ฒซ ๋ฒ์งธ ์์์ ์ค์๋๊ฐ input์ ๋ง์ง๋ง ์์์ ๊ฐ ์ฆ, ๊ฐ์ฅ ๋์ ์ค์๋์ ๊ฐ๋ค๋ฉด, result ๋ณ์๋ฅผ 1 ์ฆ๊ฐ์ํจ๋ค.
์์ค์ฝ๋
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
'โจ๏ธ Language > swift' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[Swift] ๋ฐฑ์ค 2577๋ฒ - ์ซ์์ ๊ฐ์ (0) | 2023.03.25 |
---|---|
[Swift] ๋ฐฑ์ค 10808๋ฒ - ์ํ๋ฒณ ๊ฐ์ (0) | 2023.03.25 |
[Swift] ๋ฐฑ์ค 1935๋ฒ - ํ์ ํ๊ธฐ์2 (0) | 2023.03.23 |
[Swift] ๋ฐฑ์ค 10866๋ฒ - ๋ฑ (0) | 2023.03.21 |
[Swift] ๋ฐฑ์ค 2164๋ฒ - ์นด๋2 (0) | 2023.03.21 |