문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 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 함수를 완성해 주세요.
제한 사항
- info 배열의 크기는 1 이상 50,000 이하입니다.
- info 배열 각 원소의 값은 지원자가 지원서에 입력한 4가지 값과 코딩테스트 점수를 합친 "개발언어 직군 경력 소울푸드 점수" 형식입니다.
- 개발언어는 cpp, java, python 중 하나입니다.
- 직군은 backend, frontend 중 하나입니다.
- 경력은 junior, senior 중 하나입니다.
- 소울푸드는 chicken, pizza 중 하나입니다.
- 점수는 코딩테스트 점수를 의미하며, 1 이상 100,000 이하인 자연수입니다.
- 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
- query 배열의 크기는 1 이상 100,000 이하입니다.
- query의 각 문자열은 "[조건] X" 형식입니다.
- [조건]은 "개발언어 and 직군 and 경력 and 소울푸드" 형식의 문자열입니다.
- 언어는 cpp, java, python, - 중 하나입니다.
- 직군은 backend, frontend, - 중 하나입니다.
- 경력은 junior, senior, - 중 하나입니다.
- 소울푸드는 chicken, pizza, - 중 하나입니다.
- '-' 표시는 해당 조건을 고려하지 않겠다는 의미입니다.
- X는 코딩테스트 점수를 의미하며 조건을 만족하는 사람 중 X점 이상 받은 사람은 모두 몇 명인 지를 의미합니다.
- 각 단어는 공백문자(스페이스 바) 하나로 구분되어 있습니다.
- 예를 들면, "cpp and - and senior and pizza 500"은 "cpp로 코딩테스트를 봤으며, 경력은 senior 이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 500점 이상 받은 사람은 모두 몇 명인가?"를 의미합니다.
입출력 예
| info | query | result |
|---|---|---|
| ["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] |
입출력 예 설명
지원자 정보를 표로 나타내면 다음과 같습니다.
| info | query | result | 소울푸드 | 점수 |
|---|---|---|---|---|
| java | backend | junior | pizza | 150 |
| python | frotend | senior | chicken | 210 |
| python | frotend | 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" : java로 코딩테스트를 봤으며, backend 직군을 선택했고 junior 경력이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 100점 이상 받은 지원자는 1명 입니다.
- "python and frontend and senior and chicken 200" : python으로 코딩테스트를 봤으며, frontend 직군을 선택했고, senior 경력이면서 소울 푸드로 chicken을 선택한 지원자 중 코딩테스트 점수를 200점 이상 받은 지원자는 1명 입니다.
- "cpp and - and senior and pizza 250" : cpp로 코딩테스트를 봤으며, senior 경력이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점수를 250점 이상 받은 지원자는 1명 입니다.
- "- and backend and senior and - 150" : backend 직군을 선택했고, senior 경력인 지원자 중 코딩테스트 점수를 150점 이상 받은 지원자는 1명 입니다.
- "- and - and - and chicken 100" : 소울푸드로 chicken을 선택한 지원자 중 코딩테스트 점수를 100점 이상을 받은 지원자는 2명 입니다.
- "- and - and - and - 150" : 코딩테스트 점수를 150점 이상 받은 지원자는 4명 입니다.
내가 제출한 코드
import Foundation
func solution(_ info:[String], _ query:[String]) -> [Int] {
var result: [Int] = []
var applicantGroup: [String:[Int]] = [:]
// 지원자 정보를 읽음
for infos in info {
let infoJobs = infos.split(separator: " ").map { String($0)}
let tmpGroup: [String] = createGroup(infoJobs) // 지원자 정보를 바탕으로 그룹을 만듬
tmpGroup.forEach { // 만든 그룹에 해당하는 점수를 삽입
if let score = applicantGroup[$0] {
var scoreArray = score
scoreArray.append(Int(infoJobs[4])!)
applicantGroup[$0] = scoreArray
} else {
applicantGroup[$0] = [Int(infoJobs[4])!]
}
}
}
// 이진탐색을 위한 오름차순 정렬
for (k, v) in applicantGroup {
var tmpList = v.sorted()
applicantGroup[k] = tmpList
}
// query할 조건과 점수를 구분
for queries in query {
// query문에서 점수 파싱
let queryScore = queries.filter {
return ($0.isNumber) ? true : false
}
var tmpQuery = queries.filter {
return ($0.isNumber) ? false : true
}
// query문에서 해당하는 조건들을 그룹의 key랑 매칭하기 위한 문자열 처리
tmpQuery = tmpQuery.replacingOccurrences(of: "and", with: "")
tmpQuery = tmpQuery.replacingOccurrences(of: "-", with: "")
tmpQuery = tmpQuery.replacingOccurrences(of: " ", with: "")
// 지원자 자료구조에서 해당 점수 이상인 사람의 수를 반환
result.append(searchApplicant(tmpQuery, Int(queryScore)!, applicantGroup))
}
return result
}
// n점 이상인 사람의 수를 반환
func searchApplicant(_ condition: String, _ queryScore: Int, _ group: [String:[Int]]) -> Int {
var result = 0
// binarysearch 사용
if let applicantScoreList = group[condition] {
var peopleCount = binarySearch(applicantScoreList, queryScore) // 해당 점수가 처음 나타나는 위치 반환
result = applicantScoreList.count - peopleCount
}
return result
}
// 이진 탐색 (lower bound)
func binarySearch(_ data: [Int], _ target: Int) -> Int{
var begin = 0, end = data.count
while begin < end {
var middle = (begin+end)/2
if target <= data[middle] {
end = middle
} else {
begin = middle+1
}
}
return end
}
// 입력된 지원자의 정보를 바탕으로 그룹을 만듬
func createGroup(_ infoJob: [String]) -> [String]{
var group: [String] = []
var lastIndex = infoJob.index(before: infoJob.endIndex)
var data = infoJob[..<lastIndex].map { String($0) }
// query문에서 개발언어, 지원 직군, 경력, 소울푸드가 생략될 수 있으므로 모든 경우의 수에 해당하는 그룹을 만듬(16개)
for i in 0...4 {
group += combination(data, 0, i, "",0)
}
return group
}
// 그룹을 만드는 함수
func combination(_ data: [String], _ k: Int, _ r: Int, _ tmp: String, _ count: Int) -> [String] {
var result: [String] = []
if count == r {
return [tmp]
}
for i in k..<data.count {
result += combination(data, i+1, r, tmp+data[i], count+1)
}
return result
}코드 설명
해당 문제는 정확성과 효율성이 있는 문제이다.
우선 효율성을 고려하지 않는 방법은 단순히 순차 탐색을 하는 경우이다. 이 방법은 info 배열의 크기가 50,000이고 query 배열의 크기가 100,000일시 효율성 측면에서 통과하지 못한다. 그러므로 효율성을 고려하기 위해 info 배열에서 읽은 지원자에 대해 그룹별로 적절히 분류를 해야 한다. 예를 들어 "java backend junior pizza 150" 지원자는 다음과 같이 16개의 그룹에 속한다.
이렇게 16개의 그룹으로 나누는 이유는 query 배열에 언어나 직군, 경력, 소울푸드 등이 생략될 수 있기 때문에 이를 모두 고려하여 분류하였다. 그러므로 query 배열에 해당하는 지원자를 찾는 경우, 모든 info 배열을 탐색하는 것이 아닌 해당 그룹에서 탐색하면 시간을 단축할 수 있다. 탐색을 하는 경우에 순차 탐색을 하는 것이 아닌 이진 탐색을 사용한다.
다음으로 코드를 세부적으로 살펴본다.
지원자 정보를 관리하는 딕셔너리 applicantGroup을 선언하였다. 각 그룹의 이름을 key로 구성하고, value인 Int 배열은 해당 그룹에 속하는 지원자의 코딩 테스트 점수들의 리스트이다.
var applicantGroup: [String:[Int]] = [:]다음은 info 배열에서 지원자의 정보를 읽고 이를 그룹으로 분류하는 코드다.
// 입력된 지원자의 정보를 바탕으로 그룹을 만듬
func createGroup(_ infoJob: [String]) -> [String]{
var group: [String] = []
var lastIndex = infoJob.index(before: infoJob.endIndex)
var data = infoJob[..<lastIndex].map { String($0) }
// query문에서 개발언어, 지원 직군, 경력, 소울푸드가 생략될 수 있으므로 모든 경우의 수에 해당하는 그룹을 만듬(16개)
for i in 0...4 {
group += combination(data, 0, i, "",0)
}
return group
}
// 그룹을 만드는 함수
func combination(_ data: [String], _ k: Int, _ r: Int, _ tmp: String, _ count: Int) -> [String] {
var result: [String] = []
if count == r {
return [tmp]
}
for i in k..<data.count {
result += combination(data, i+1, r, tmp+data[i], count+1)
}
return result
}우선 파라미터 infoJob에 info배열의 각 element가 할당된다. 해당 지원자의 정보를 16개의 그룹으로 만들기 위해선 조합을 사용하였다. 조합으로 얻는 그룹의 예시는 다음과 같다. 각 그룹을 보면 query 배열에서 처럼 몇개의 항목이 생략되어 만들어진 것을 확인할 수 있다. 빈 문자열인 경우는 모든 정보가 생략되고 점수만 query된 경우에 해당하는 것이다.
group: ["", "java", "backend", "junior", "pizza", "javabackend", "javajunior", "javapizza",
"backendjunior", "backendpizza", "juniorpizza", "javabackendjunior", "javabackendpizza",
"javajuniorpizza", "backendjuniorpizza", "javabackendjuniorpizza"]1명의 지원자의 정보에 대해 다음과 같이 16개의 그룹을 리스트에 담아 반환한다. 반환된 리스트를 지원자 정보를 관리하는 딕셔너리 applicantGroup에 할당된다. 즉 만든 각각의 16개의 그룹들을 key로 만들고 key에 해당하는 value에는 읽은 지원자의 점수를 할당한다. 이를 모든 info 배열의 element에 적용하여 지원자의 정보 자료구조를 만든다.
다음 단계는 query 배열을 읽어 각 element에 해당하는 사람들의 수를 계산하는 과정이다.
for queries in query {
// query문에서 점수 파싱
let queryScore = queries.filter {
return ($0.isNumber) ? true : false
}
var tmpQuery = queries.filter {
return ($0.isNumber) ? false : true
}
// query문에서 해당하는 조건들을 그룹의 key랑 매칭하기 위한 문자열 처리
tmpQuery = tmpQuery.replacingOccurrences(of: "and", with: "")
tmpQuery = tmpQuery.replacingOccurrences(of: "-", with: "")
tmpQuery = tmpQuery.replacingOccurrences(of: " ", with: "")
// 지원자 자료구조에서 해당 점수 이상인 사람의 수를 반환
result.append(searchApplicant(tmpQuery, Int(queryScore)!, applicantGroup))
}지원자의 정보를 담은 딕셔너리의 key가 String의 연속 (javabackendjuniorpizza)와 같이 구성되어 있기 때문에, query를 key의 형태처럼 변환해야 한다. 그러므로 filter를 사용하여 query할 조건과 점수를 구분한다. 다음으로 and, -, " "을 제거한다. 이 과정을 거치면 딕셔너리의 key와 동일한 형태의 문자열이 되므로 subscript로 접근하여 해당 그룹의 점수 리스트를 얻을 수 있다.
그룹의 점수 리스트를 얻은 뒤 조건을 만족하는 지원자의 수를 얻어야 한다. 이때 순차 탐색을 사용할 수 있으나 효율성을 고려하여 이진 탐색을 사용한다. 그러나 여기서 유의할 점이 1개 있다.
기존에 이진 탐색은 찾고자 하는 값(target)이 있다면 해당 값의 인덱스를 바로 반환한다. 그러나 이 문제에서는 해당 점수 이상인 사람을 찾아야 하므로 lower bound를 이용한다.
// 이진 탐색 (lower bound)
func binarySearch(_ data: [Int], _ target: Int) -> Int{
var begin = 0, end = data.count
while begin < end {
var middle = (begin+end)/2
if target <= data[middle] {
end = middle
} else {
begin = middle+1
}
}
return end
}몰랐던 사실 or 기억하면 도움이 될 만한 사실
문자열 치환 (replacingOccurrences)
swift의 문자열 치환은 replacingOccurrences(of:with:) 메소드를 사용한다.
func replacingOccurrences(
of target: String,
with replacement: String
) -> String이 메소드는 of 파라미터에 변환하기 전의 문자, with 파라미터에 변환하고자 하는 문자를 할당하면 된다. 예를 들어
tmpQuery = tmpQuery.replacingOccurrences(of: "and", with: "")인 경우 tmpQuert 문자열 내에 "and"가 있다면 이를 빈칸("")으로 변환 즉 제거하는 것이다. 이 메소드는 변환된 문자열을 반환한다.
binary search (이진 탐색)
순차 탐색은 어떤 리스트에 찾고자 하는 값이 있다면 리스트의 처음이나 끝에서 1개씩 찾아 원하는 값을 탐색하는 것이다. 그러므로 시간 복잡도 O(n)을 가진다. 그러나 이보다 더 효율적인 탐색 방법인 있는 데 바로 이진 탐색(binary search)이다.
이진 탐색은 시간 복잡도가 O(logn)으로 훨씬 효율적이다. 그러나 이는 리스트의 데이터가 오름차순으로 정렬되어 있다는 조건을 만족하여야 가능하다.
이진 탐색에 대한 자세한 설명은 다음 동영상을 참고하길 바란다.
https://www.youtube.com/watch?v=ZX2mC6OJrqM&list=PL52K_8WQO5oXIATx2vcTvqwxXxoGxxsIz&index=45
