Algorithm
[Algorithm] ๋ฌธ์์ด ์์ถ
_๋ณด๋ฆ
2021. 4. 16. 15:19
๐ฅ ๋ฌธ์
์์ถํ ๋ฌธ์์ด s๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋, ์์ ์ค๋ช ํ ๋ฐฉ๋ฒ์ผ๋ก 1๊ฐ ์ด์ ๋จ์๋ก ๋ฌธ์์ด์ ์๋ผ ์์ถํ์ฌ ํํํ ๋ฌธ์์ด ์ค ๊ฐ์ฅ ์งง์ ๊ฒ์ ๊ธธ์ด๋ฅผ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด์ฃผ์ธ์.
๐ค ํ์ด ๋ฐฉ๋ฒ
- ๋ณ์
s
: [String] : ์์ถํ ๋ฌธ์์ดcompressedS: [String]
: ์์ถ๋ ๋ฌธ์์ด ์ค ๊ฐ์ฅ ์งง์ ๋ฌธ์์ดstart: Int
: ๋น๊ต์ ๊ธฐ์ค์ด ๋๋ ๋ฌธ์์ด์ ์์ ์ธ๋ฑ์คcurrent: Int
: ๋น๊ต์ค์ธ ์ธ๋ฑ์คnum: Int
: ์์ถ์ด ๊ฐ๋ฅํ ๊ฐ์tmp: [string]
: ์์ถ๋ ๋ฌธ์์ด
for i in 1...s.count/2 + 1 {}
- 1๊ฐ ~ s.count/2๊ฐ์ ๋ฌธ์์ด ๋จ์๋ก ์์ถํ๊ธฐ ์ํ์ฌ ๋ฐ๋ณตํ๋ค.
while current+i-1 < s.count && s[start...start+i-1] == s[current...current+i-1] {}
- ๋น๊ต์ ๊ธฐ์ค์ด ๋๋ ๋ฌธ์์ด๊ณผ ๋๋จธ์ง ๋ฌธ์์ด์ ๋น๊ตํ๋ค.
- ๋ฌธ์์ด์ด ์ฐ์๋๋ฉด ์ฐ์๋๋ ํ์๋งํผ num์ +1 ํด์ค๋ค.
- 2๋ฒ ์ด์ ๋ฐ๋ณต๋ ๊ฒฝ์ฐ, ์ฆ num์ด 2 ์ด์์ผ ๊ฒฝ์ฐ
tmp.append(String(num))
tmp.append(contentsOf: s[start...start+i-1])
- num๊ณผ ๊ธฐ์ค ๋ฌธ์์ด์ ๋ฃ์ด ์์ถํ๋ค.
tmp.append(contentsOf: s[start...start+i-1])
- ์์ถ์ด ๋์ง ์์ ๊ฒฝ์ฐ ๊ธฐ์ค ๋ฌธ์์ด๋ง ๋ฃ๋๋ค.
- ๋ชจ๋ ๋น๊ต๊ฐ ๋๋๊ณ ๋จ์ ๋ฌธ์์ด์ ๋ฃ๋๋ค.
compressedS = tmp == [] || compressedS.count < tmp.count ? compressedS : tmp
- compressedS์ tmp๋ฅผ ๋น๊ตํ์ฌ ๊ฐ์ฅ ์งง์ ๋ฌธ์์ด์ compressedS์ ๋ฃ๋๋ค.
return compressedS.map{$0}.reduce("", +).count
- ๋ชจ๋ ๊ณผ์ ์ด ๋๋๋ฉด compressedS์ ๋ฌธ์์ด ๊ธธ์ด๋ฅผ ๋ฆฌํดํ๋ค.
๐ฉ๐ปโ๐ป Swift Code
import Foundation
func solution(_ s:String) -> Int {
let s = s.map{String($0)}
var compressedS = s
// 1 ~ s.count/2 ๊ฐ์ ๋ฌธ์์ด ๋จ์
for i in 1...s.count/2 + 1 {
var start = 0
var current = i
var num = 1
var tmp: [String] = []
while current < s.count {
// i๊ฐ์ ๋ฌธ์์ด ๋จ์๋ก ๋น๊ต
while current+i-1 < s.count && s[start...start+i-1] == s[current...current+i-1] {
current += i
num += 1
}
// ์์ถ, 2์ด์ ๋ฐ๋ณต๋๋ฉด ๋ฐ๋ณต๋ ํ์ ์ถ๊ฐ
if num > 1 {
tmp.append(String(num))
tmp.append(contentsOf: s[start...start+i-1])
} else {
tmp.append(contentsOf: s[start...start+i-1])
}
// ์์ถ๋์ง ์์ ๋ฌธ์์ด์ ์ถ๊ฐ
if current >= s.count - i && current < s.count {
while current < s.count {
tmp.append(s[current])
current += 1
}
}
start = current
current += i
num = 1
}
compressedS = tmp == [] || compressedS.count < tmp.count ? compressedS : tmp
}
return compressedS.map{$0}.reduce("", +).count
}
์ฝ๋ฉํ ์คํธ ์ฐ์ต - ๋ฌธ์์ด ์์ถ
๋ฐ์ดํฐ ์ฒ๋ฆฌ ์ ๋ฌธ๊ฐ๊ฐ ๋๊ณ ์ถ์ "์ดํผ์น"๋ ๋ฌธ์์ด์ ์์ถํ๋ ๋ฐฉ๋ฒ์ ๋ํด ๊ณต๋ถ๋ฅผ ํ๊ณ ์์ต๋๋ค. ์ต๊ทผ์ ๋๋์ ๋ฐ์ดํฐ ์ฒ๋ฆฌ๋ฅผ ์ํ ๊ฐ๋จํ ๋น์์ค ์์ถ ๋ฐฉ๋ฒ์ ๋ํด ๊ณต๋ถ๋ฅผ ํ๊ณ ์๋๋ฐ, ๋ฌธ
programmers.co.kr