2022. 11. 15. 14:42ใAlgorithm
๋ฐฑ์ค - ๋น๋ฌผ(Swift)
๋ฌธ์ ์ค๋ช
https://www.acmicpc.net/problem/14719
๋์ ํ์ด
๋ฌธ์ ๋ฅผ ๋ณด์๋ง์ ์ธ์ ๋น๋ฌผ์ด ์ฐจ๋์ง ๊ท์น์ ์ฐพ์ผ๋ ค๊ณ ํ๋ค.
๊ทธ๋์ ์ฐพ์ ๊ท์น์ ์ฒ์๋ถํฐ ํ์ํ ๋ ๋ค์ด์ค๋ ๋ธ๋ก์ ๊ธฐ์ค์ ์ผ๋ก ๋๊ณ ๊ธฐ์ค์ ๋ณด๋ค ํฌ๊ฑฐ๋ ๊ฐ์ ๋ธ๋ญ์ด ๋์ฌ๋๋ง๋ค ๊ทธ ์ฌ์ด์ ๊ฐ๋ค์ ๊ธฐ์ค์ ์ผ๋ก ๋น๋ฌผ์ ์ฑ์์ค๋ค๋ ๊ท์น์ ์ฐพ์๋ค. ์ฃผ์ํ ์ ์ ์ฒ์ ๊ธฐ์ค์ ์ ์ ํ ๋๋ง flag๋ฅผ ์ค์ผ๋ก์จ ๊ณ์ํด์ ๊ธฐ์ค์ ์ด ๋ฆฌ์ ๋๋ ๊ฒ์ ๋ฐฉ์งํ๋ ๊ฒ์ด๋ค. x๊ฐ 1๋ณด๋ค ํฌ๋ค๋ ์กฐ๊ฑด์ ๋ฃ์๊ธฐ ๋๋ฌธ์ ๋์ด ๋น์ด์๋ ๊ฒฝ์ฐ๋ฅผ ๋ฐฉ์งํ ์ ์๋ค.
์ฌ์ค ๋ณ๋ก ์ข์ง์์ ํ์ด์ธ ๊ฒ ๊ฐ๋ค๊ณ ์๊ฐํด์ ๋ค๋ฅธ ๋ถ๋ค์ ํ์ด๋ฅผ ์ฐพ์๋ณด์๋ค.
import Foundation
let input = readLine()!.components(separatedBy:" ").map{Int($0)!}
let H = input[0], W = input[1]
let arr = readLine()!.components(separatedBy:" ").map{Int($0)!}
var visited = [Bool](repeating: false, count: W) // ๋น๋ฌผ์ ์ฑ์ ๋์ง
var flag = false
var baseLine = H+1
var baseIdx = 0
var result = 0
for (i, x) in arr.enumerated() {
if x >= 1 && !flag {
baseLine = x
baseIdx = i
flag = true
} else if baseLine <= x {
for j in baseIdx+1..<i {
if !visited[j] {
result += baseLine - arr[j]
visited[j] = true
}
}
baseLine = x
baseIdx = i
}
}
flag = false
for i in stride(from: W-1, to: -1, by: -1) {
if arr[i] >= 1 && !flag {
baseLine = arr[i]
baseIdx = i
flag = true
} else if baseLine <= arr[i] {
for j in stride(from: baseIdx-1, to: i, by: -1) {
if !visited[j] {
result += baseLine - arr[j]
visited[j] = true
}
}
baseLine = arr[i]
baseIdx = i
}
}
print(result)
๋ค๋ฅธ ์ฌ๋์ ํ์ด
ํน์ ์์น๋ฅผ ๊ธฐ์ค์ผ๋ก ์ผ์ชฝ์ ์ต๋๊ฐ๊ณผ ์ค๋ฅธ์ชฝ์ ์ต๋๊ฐ์ค์ ๋ ์์ ๊ฐ๋งํผ ๋น๋ฌผ์ ์ฑ์์ฃผ๋ ๋ฐฉ์์ด๋ค.
์ด๋ฅผ ์ํด์ ๊ฐ ์ธ๋ฑ์ค์์์ ์ต๋๊ฐ์ ๊ตฌํด์คฌ๋ค.
import Foundation
let input = readLine()!.components(separatedBy:" ").map{Int($0)!}
let H = input[0], W = input[1]
let arr = readLine()!.components(separatedBy:" ").map{Int($0)!}
var leftMax = [Int](repeating: 0, count: arr.count)
var rightMax = [Int](repeating: 0, count: arr.count)
var result = 0
leftMax[0] = arr[0]
rightMax[arr.count-1] = arr.last!
for i in 1..<arr.count {
leftMax[i] = max(leftMax[i-1], arr[i])
}
for i in (0..<arr.count-1).reversed() {
rightMax[i] = max(rightMax[i+1], arr[i])
}
for i in 1..<arr.count-1 {
result += min(leftMax[i], rightMax[i]) - arr[i]
}
print(result)
'Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๋ฐฑ์ค - 0 ๋ง๋ค๊ธฐ(Swift) (0) | 2022.11.16 |
---|---|
๋ฐฑ์ค - ๋น๋ฐํธ์(Swift) (0) | 2022.11.15 |
๋ฐฑ์ค - ์ปจ๋ฒ ์ด์ด ๋ฒจํธ ์์ ๋ก๋ด(Swift) (0) | 2022.11.14 |
๋ฐฑ์ค - ๋ก๋ด ์ฒญ์๊ธฐ(Swift) (0) | 2022.11.14 |
๋ฐฑ์ค - ํ ์ค๋ก ์๊ธฐ(Swift) (0) | 2022.11.11 |