[์ค์ํํธ ์๊ณ ๋ฆฌ์ฆ] ํ๋ก๊ทธ๋๋จธ์ค: ์์ ๊ฒ์
๋ฌธ์
https://programmers.co.kr/learn/courses/30/lessons/72412
์ฝ๋ฉํ ์คํธ ์ฐ์ต - ์์ ๊ฒ์
["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"] ["java and backend and junior and pizza 100","pyt
programmers.co.kr
๋ฌธ์ ์ค๋ช
[๋ณธ ๋ฌธ์ ๋ ์ ํ์ฑ๊ณผ ํจ์จ์ฑ ํ ์คํธ ๊ฐ๊ฐ ์ ์๊ฐ ์๋ ๋ฌธ์ ์ ๋๋ค.]
์นด์นด์ค๋ ํ๋ฐ๊ธฐ ๊ฒฝ๋ ฅ ๊ฐ๋ฐ์ ๊ณต๊ฐ์ฑ์ฉ์ ์งํ ์ค์ ์์ผ๋ฉฐ ํ์ฌ ์ง์์ ์ ์์ ์ฝ๋ฉํ ์คํธ๊ฐ ์ข ๋ฃ๋์์ต๋๋ค. ์ด๋ฒ ์ฑ์ฉ์์ ์ง์์๋ ์ง์์ ์์ฑ ์ ์๋์ ๊ฐ์ด 4๊ฐ์ง ํญ๋ชฉ์ ๋ฐ๋์ ์ ํํ๋๋ก ํ์์ต๋๋ค.
- ์ฝ๋ฉํ ์คํธ ์ฐธ์ฌ ๊ฐ๋ฐ์ธ์ด ํญ๋ชฉ์ cpp, java, python ์ค ํ๋๋ฅผ ์ ํํด์ผ ํฉ๋๋ค.
- ์ง์ ์ง๊ตฐ ํญ๋ชฉ์ backend์ frontend ์ค ํ๋๋ฅผ ์ ํํด์ผ ํฉ๋๋ค.
- ์ง์ ๊ฒฝ๋ ฅ๊ตฌ๋ถ ํญ๋ชฉ์ junior์ senior ์ค ํ๋๋ฅผ ์ ํํด์ผ ํฉ๋๋ค.
- ์ ํธํ๋ ์์ธํธ๋๋ก chicken๊ณผ pizza ์ค ํ๋๋ฅผ ์ ํํด์ผ ํฉ๋๋ค.
์ธ์ฌ์์
ํ์ ๊ทผ๋ฌดํ๊ณ ์๋ ๋๋์ฆ๋ ์ฝ๋ฉํ
์คํธ ๊ฒฐ๊ณผ๋ฅผ ๋ถ์ํ์ฌ ์ฑ์ฉ์ ์ฐธ์ฌํ ๊ฐ๋ฐํ๋ค์ ์ ๊ณตํ๊ธฐ ์ํด ์ง์์๋ค์ ์ง์ ์กฐ๊ฑด์ ์ ํํ๋ฉด ํด๋น ์กฐ๊ฑด์ ๋ง๋ ์ง์์๊ฐ ๋ช ๋ช
์ธ ์ง ์ฝ๊ฒ ์ ์ ์๋ ๋๊ตฌ๋ฅผ ๋ง๋ค๊ณ ์์ต๋๋ค.
์๋ฅผ ๋ค์ด, ๊ฐ๋ฐํ์์ ๊ถ๊ธํดํ๋ ๋ฌธ์์ฌํญ์ ๋ค์๊ณผ ๊ฐ์ ํํ๊ฐ ๋ ์ ์์ต๋๋ค.
์ฝ๋ฉํ
์คํธ์ java๋ก ์ฐธ์ฌํ์ผ๋ฉฐ, backend ์ง๊ตฐ์ ์ ํํ๊ณ , junior ๊ฒฝ๋ ฅ์ด๋ฉด์, ์์ธํธ๋๋ก pizza๋ฅผ ์ ํํ ์ฌ๋ ์ค ์ฝ๋ฉํ
์คํธ ์ ์๋ฅผ 50์ ์ด์ ๋ฐ์ ์ง์์๋ ๋ช ๋ช
์ธ๊ฐ?
๋ฌผ๋ก ์ด ์ธ์๋ ๊ฐ ๊ฐ๋ฐํ์ ์ํฉ์ ๋ฐ๋ผ ์๋์ ๊ฐ์ด ๋ค์ํ ํํ์ ๋ฌธ์๊ฐ ์์ ์ ์์ต๋๋ค.
- ์ฝ๋ฉํ ์คํธ์ python์ผ๋ก ์ฐธ์ฌํ์ผ๋ฉฐ, frontend ์ง๊ตฐ์ ์ ํํ๊ณ , senior ๊ฒฝ๋ ฅ์ด๋ฉด์, ์์ธํธ๋๋ก chicken์ ์ ํํ ์ฌ๋ ์ค ์ฝ๋ฉํ ์คํธ ์ ์๋ฅผ 100์ ์ด์ ๋ฐ์ ์ฌ๋์ ๋ชจ๋ ๋ช ๋ช ์ธ๊ฐ?
- ์ฝ๋ฉํ ์คํธ์ cpp๋ก ์ฐธ์ฌํ์ผ๋ฉฐ, senior ๊ฒฝ๋ ฅ์ด๋ฉด์, ์์ธํธ๋๋ก pizza๋ฅผ ์ ํํ ์ฌ๋ ์ค ์ฝ๋ฉํ ์คํธ ์ ์๋ฅผ 100์ ์ด์ ๋ฐ์ ์ฌ๋์ ๋ชจ๋ ๋ช ๋ช ์ธ๊ฐ?
- backend ์ง๊ตฐ์ ์ ํํ๊ณ , senior ๊ฒฝ๋ ฅ์ด๋ฉด์ ์ฝ๋ฉํ ์คํธ ์ ์๋ฅผ 200์ ์ด์ ๋ฐ์ ์ฌ๋์ ๋ชจ๋ ๋ช ๋ช ์ธ๊ฐ?
- ์์ธํธ๋๋ก chicken์ ์ ํํ ์ฌ๋ ์ค ์ฝ๋ฉํ ์คํธ ์ ์๋ฅผ 250์ ์ด์ ๋ฐ์ ์ฌ๋์ ๋ชจ๋ ๋ช ๋ช ์ธ๊ฐ?
- ์ฝ๋ฉํ ์คํธ ์ ์๋ฅผ 150์ ์ด์ ๋ฐ์ ์ฌ๋์ ๋ชจ๋ ๋ช ๋ช ์ธ๊ฐ?
์ฆ, ๊ฐ๋ฐํ์์ ๊ถ๊ธํดํ๋ ๋ด์ฉ์ ๋ค์๊ณผ ๊ฐ์ ํํ๋ฅผ ๊ฐ์ต๋๋ค.
* [์กฐ๊ฑด]์ ๋ง์กฑํ๋ ์ฌ๋ ์ค ์ฝ๋ฉํ ์คํธ ์ ์๋ฅผ X์ ์ด์ ๋ฐ์ ์ฌ๋์ ๋ชจ๋ ๋ช ๋ช ์ธ๊ฐ?
[๋ฌธ์ ]
์ง์์๊ฐ ์ง์์์ ์
๋ ฅํ 4๊ฐ์ง์ ์ ๋ณด์ ํ๋ํ ์ฝ๋ฉํ
์คํธ ์ ์๋ฅผ ํ๋์ ๋ฌธ์์ด๋ก ๊ตฌ์ฑํ ๊ฐ์ ๋ฐฐ์ด info, ๊ฐ๋ฐํ์ด ๊ถ๊ธํดํ๋ ๋ฌธ์์กฐ๊ฑด์ด ๋ฌธ์์ด ํํ๋ก ๋ด๊ธด ๋ฐฐ์ด query๊ฐ ๋งค๊ฐ๋ณ์๋ก ์ฃผ์ด์ง ๋,
๊ฐ ๋ฌธ์์กฐ๊ฑด์ ํด๋นํ๋ ์ฌ๋๋ค์ ์ซ์๋ฅผ ์์๋๋ก ๋ฐฐ์ด์ ๋ด์ return ํ๋๋ก solution ํจ์๋ฅผ ์์ฑํด ์ฃผ์ธ์.
ํ์ด
Set์ ๋ง๋ค์ด intersection์ ํ๋ ๋ฐฉ๋ฒ, ๋จ์ํ ๋ธ๋ฃจํธํฌ์ค๋ก ํธ๋ ๋ฐฉ๋ฒ์ ๋ชจ๋ ์๋ํด๋ณด์๋๋ฐ ์ ํ๋๋ ํต๊ณผํ์ง๋ง ํจ์จ์ฑ๊ฒ์ฌ๋ฅผ ํต๊ณผํ ์ ์์์ต๋๋ค. ์๊ฐ๋ณต์ก๋๋ฅผ ์ค์ด๋ ค๋ฉด ๋ ๊ฐ์ง ๋ถ๋ถ์ ์ ๊ฒฝ์จ์ผ ํฉ๋๋ค. ์ฒซ ๋ฒ์งธ๋ ์ฟผ๋ฆฌ์ "-"๊ฐ ์์ ๋์ ํ์์๊ฐ์ ์ค์ด๋ ๊ฒ์ด๊ณ , ๋๋ฒ์งธ๋ ์ฃผ์ด์ง ์ ์ ์ด์์ ์ ์๋ฅผ ๊ฐ์ง ๋ ์ฝ๋๋ค์ ์ฐพ๋ ์๊ฐ์ ์ค์ด๋ ๊ฒ์ ๋๋ค.
ํ์์๊ฐ์ ์ค์ด๊ธฐ ์ํด์๋ ์ฃผ์ด์ง ์ ๋ ฅ ์ค ์ ์๋ฅผ ์ ์ธํ ์กฐ๊ฑด๋ค๊ณผ "-" ์ผ๋ก ๋ง๋ค ์ ์๋ ์กฐํฉ์ ๋ฏธ๋ฆฌ ๋ง๋ค์ด ๋์ ๋๋ฆฌ๋ก ๋ง๋๋ ๊ฒ์ด ๊ฐ์ฅ ํจ๊ณผ์ ์ ๋๋ค. ์๋ฅผ ๋ค์ด, "python and frontend and senior and chicken 200" ๊ฐ ์ฃผ์ด์ก๋ค๋ฉด ๋ค์๊ณผ ๊ฐ์ ๋์ ๋๋ฆฌ ์์๋ฅผ ๋ง๋ค ์ ์์ต๋๋ค.
"pythonfrontendseniorchicken" : 200
"-frontendseniorchicken" : 200
"--seniorchicken" : 200
"---chicken" : 200
"----" : 200
.
.
.
"pythonfrontendsenior-" : 200
๊ฐ ์์น์ ์ฃผ์ด์ง ์ ๋ณด ํน์ "-" ๋ฅผ ์ฌ์ฉํ ์ ์๊ธฐ ๋๋ฌธ์ 2^4 ๋ก ์ด 16๊ฐ์ ๋์ ๋๋ฆฌ๋ฅผ ์ฑ์ํ ์ ์์ต๋๋ค. ๊ฐ์ ๋ฐฉ์์ผ๋ก ๋ชจ๋ info์ ๋ํด ํค๋ฅผ ๋ง๋ค๊ณ , ์ด๋ฏธ ์กด์ฌํ๋ ํค๋ผ๋ฉด ์ ์๋ฅผ ๋ฐฐ์ด๋ก ์ถ๊ฐํด์ฃผ๋ฉด๋ฉ๋๋ค. ์ด์ ์ ์ฒด ๋์ ๋๋ฆฌ ํ์ํ ํ์์์ด query๋ก key๋ฅผ ๋ง๋ค์ด ๊ณง๋ฐ๋ก ์ ์๋ฅผ ์ป์ ์ ์์ต๋๋ค.
ํค๋ฅผ ์ ๋ ฅํด ์ป์ ์ ์๋ค์์ ์ฟผ๋ฆฌ๋ก ์ฃผ์ด์ง ์ ์ ์ด์์ ์ ์๋ค์ ๊ณจ๋ผ๋ด๊ธฐ ์ํด์๋ ์์ ํ์์ผ๋ก๋ ํจ์จ์ฑ์ ํต๊ณผํ ์ ์์ต๋๋ค. ๋ฐ๋ผ์ ์ ์๋ค์ ๋ด๋ฆผ์ฐจ์์ผ๋ก ์ ๋ ฌํ๊ณ , ์ด๋ถ ํ์์ผ๋ก ๋ฐ์ด๋๋ฅผ ์ฐพ์ ์ธ๋ฑ์ค๋ฅผ ๊ฐ์๋ก ๋ณํํด์ ์ฌ์ฉํ๋ฉด O(NLogN)์ ์๊ฐ๋ณต์ก๋๋ก ์ ์๋ค์ ๊ฐ์๋ฅผ ์์๋ผ ์ ์์ต๋๋ค.
์ฝ๋
import Foundation | |
func makeCombination(comb:[Bool], combGroup: inout [[Bool]]) { | |
if comb.count == 4 { | |
combGroup.append(comb) | |
return | |
} | |
makeCombination(comb: comb + [true], combGroup: &combGroup) | |
makeCombination(comb: comb + [false], combGroup: &combGroup) | |
} | |
func binarySearch(scores:[Int], target: Int) -> Int { | |
var left = 0 | |
var right = scores.count - 1 | |
var mid = 0 | |
while left <= right { | |
mid = (left + right) / 2 | |
if scores[mid] >= target { | |
left = mid + 1 | |
} else { | |
right = mid - 1 | |
} | |
} | |
return left | |
} | |
func solution(_ info:[String], _ query:[String]) -> [Int] { | |
var combinations: [[Bool]] = [] | |
makeCombination(comb: [], combGroup: &combinations) | |
var answer: [Int] = [] | |
var dict: [String:[Int]] = [:] | |
for row in info { | |
var rowValues = row.components(separatedBy: " ") | |
let score = Int(rowValues.removeLast())! | |
for combination in combinations { | |
var rowKey = rowValues | |
for i in 0..<combination.count { | |
if combination[i] { | |
rowKey[i] = "-" | |
} | |
} | |
let key = rowKey.joined() | |
if dict[key] == nil { | |
dict[key] = [score] | |
} else { | |
dict[key]?.append(score) | |
} | |
} | |
} | |
for key in dict.keys { | |
dict[key] = dict[key]?.sorted(by: >) | |
} | |
for request in query { | |
answer.append(0) | |
var req = request.replacingOccurrences(of: " and ", with: " ").components(separatedBy: " ") | |
let score = Int(req.removeLast()) ?? 0 | |
let requestKey = req.joined() | |
if let result = dict[requestKey] { | |
answer[answer.count - 1] = (binarySearch(scores: result, target: score)) | |
} | |
} | |
return answer | |
} | |
assert(solution(["java backend junior pizza 150","python frontend senior chicken 210","python frontend senior chicken 150","cpp backend senior pizza 260","java backend junior chicken 80","python backend senior chicken 50"], ["java and backend and junior and pizza 100","python and frontend and senior and chicken 200","cpp and - and senior and pizza 250","- and backend and senior and - 150","- and - and - and chicken 100","- and - and - and - 150"]) == [1,1,1,1,2,4], "wrong") | |
print("correct") |
'๐๐ปโโ๏ธ ํผ-์์ค > ๐ฃ ํ๋ก๊ทธ๋๋จธ์ค' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
๋๊ธ
์ด ๊ธ ๊ณต์ ํ๊ธฐ
-
๊ตฌ๋
ํ๊ธฐ
๊ตฌ๋ ํ๊ธฐ
-
์นด์นด์คํก
์นด์นด์คํก
-
๋ผ์ธ
๋ผ์ธ
-
ํธ์ํฐ
ํธ์ํฐ
-
Facebook
Facebook
-
์นด์นด์ค์คํ ๋ฆฌ
์นด์นด์ค์คํ ๋ฆฌ
-
๋ฐด๋
๋ฐด๋
-
๋ค์ด๋ฒ ๋ธ๋ก๊ทธ
๋ค์ด๋ฒ ๋ธ๋ก๊ทธ
-
Pocket
Pocket
-
Evernote
Evernote
๋๊ธ์ ์ฌ์ฉํ ์ ์์ต๋๋ค.