[스위프트 알고리즘] 프로그래머스: 순위 검색

문제

https://programmers.co.kr/learn/courses/30/lessons/72412

코딩테스트 연습 - 순위 검색

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 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")

view raw 순위-검색.swift hosted with ❤ by GitHub