알고리즘 풀이 - 보석 쇼핑
January 09, 2021
[카카오 인턴] 보석 쇼핑
효율성
문제 요약
Input
진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems
output
가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.
해결방법
효율성을 제치고 떠오르는 가장 간단한 방법으로 생각해보자
- 제일 앞에서부터 보석의 수량 + n만큼 골라서 전체 보석의 수량과 일치하는지 확인하는 방법
정확도에는 이상이 없지만 시간초과 발생 2. 투포인터 알고리즘
- 문제 자체는 전형적인 투포인터 알고리즘이지만… 그렇게 풀면 시간 초과가 발생한다.(내가 잘못한 걸지도?)
-
Map을 이용- 순회를 하면서
Map에 보석을 담고Map의 크기가 보석의 종류와 같아질 때를 저장한다
소스코드
최초
function solution(gems) {
const gemsCount = new Set(gems).size
for (let i = 0; i < gems.length; i++)
for (let j = 0; j <= gems.length - gemsCount - i; j++) {
const start = j
const end = j + gemsCount + i
if (new Set(gems.slice(start, end)).size === gemsCount)
return [start + 1, end]
}
}정확도 중 1개, 효율성 모두 실패했다.
시간복잡도가 너무 높아진 것이 문제.
어떻게 해야할까?
j 튜닝
function solution(gems: string[]): number[] {
const gemsCount = new Set(gems).size
for (let i = 0; i < gems.length; i++)
for (let j = 0; j <= gems.length - gemsCount - i; j) {
const start = j
const end = j + gemsCount + i
const gap = gemsCount - new Set(gems.slice(start, end)).size
if (gap === 0) return [start + 1, end]
j = j + gap
}
}이중 포문 중 안쪽 포문을 +1씩 이 아니라 부족한 보석 수량만큼 건너뛰도록 수정했다.
정확성 테스트 중 하나 더 통과하기는 했는데 나머지는 여전히 실패다.
어떻게 해야 처리가 될까.
이 정도로 실패가 뜬다는 건 다른 알고리즘
바이너리 서치와 비슷하게…
접근하였으나 여전히 실패…
로컬에서 할 때에는 훨씬 빠르게 수행되는데
문제의 요구사항에는 미치지 못하나보다
function solution(gems) {
const target = new Set(gems).size
const getGems = num => {
for (let i = 0; i <= gems.length - num; i) {
const start = i
const end = i + num
const gap = target - new Set(gems.slice(start, end)).size
if (gap === 0) {
return [start + 1, end]
}
i = i + gap
}
return null
}
let willShift = false
let min = []
for (let i = gems.length; i <= gems.length; i) {
const result = getGems(i)
if (willShift) {
if (result) return result
i++
} else {
if (result) {
i = Math.floor(i / 2)
min = result
} else {
i = target
willShift = true
}
}
}
return min
}투포인터 알고리즘
막막함에 검색을 해보니 투포인터 알고리즘을 통해 해결가능할 것 같다.
투 포인터 알고리즘은 배열의 start와 end를 점차로 증가시켜 검색하는 알고리즘으로 O(n)의 시간복잡도를 가진다.
그 전 완전탐색으로 접근했을 때에는 어떻게 효율화를 하더라도 O(n)이 소요된다.
function solution(gems: string[]): number[] {
const target = new Set(gems).size
let start = 0
let end = 1
let result: { length: number; position: number[] } = {
length: Infinity,
position: [],
}
while (end <= gems.length) {
const getGems = new Set(gems.slice(start, end))
if (getGems.size === target) {
if (result.length > end - start) {
result = { length: end - start, position: [start + 1, end] }
}
start++
} else {
end++
}
}
return result.position
}투포인터 시간 초과…
그래도 효율성 테스트를 통과 못한다…
const getGems = new Set(gems.slice(start, end))부분이 문제가 아닌가 싶은데
해당 부분을 slice 쓰지말고 배열에 직접 접근해서 해결해보자
Map을 이용해보자
Map에 Key Value를 담아두고 Map.size가 gemkind와 같아지면 push하는 방법
value가 각 보석들의 idx이다.
function solution(gems: string[]): number[] {
const gemsKind = new Set(gems).size
const gemsMap: Map<string, number> = new Map()
const results: number[][] = []
for (let i = 0; i < gems.length; i++) {
gemsMap.set(gems[i], i)
if (gemsMap.size === gemsKind) {
const gemsArr = [...gemsMap.entries()].sort((a, b) => a[1] - b[1])
results.push([gemsArr[0][1] + 1, gemsArr[gemsKind - 1][1] + 1])
gemsMap.delete(gemsArr[0][0])
}
}
results.sort((a, b) => {
const aLength = a[1] - a[0]
const bLength = b[1] - b[0]
if (aLength === bLength) {
return 0 // a[0] - b[0]
}
return aLength - bLength
})
return results[0]
}
export default solution효율성 1번에서 시간초과 발생…
다시 소스코드를 뜯어보자…
개선
속도 개선이 이뤄질만한 부분은 두 부분이다.
results에 모아서 처리하지 말고 조건에 맞는 답을 찾았을 때 비교해서 가지고 있는다.-
gemsMap에 보석이 모였을 때entries().sort()하는 부분에서 시간복잡도가 추가된다.- 보석의 종류가 많으면 많을수록 정렬시간이 추가되고 이로 인해 O(n)같아 보이지만 o(n^2)으로 변한다.
- 하여 해당 부분은 뜯어봤는데… values만 가져와서 minmax 구하고 사용하는 소스로 변경
function solution(gems) {
const gemsKind = new Set(gems).size
const gemsMap = new Map()
let result = [0, Infinity]
const results = []
for (let i = 0; i < gems.length; i++) {
gemsMap.set(gems[i], i)
if (gemsMap.size === gemsKind) {
const gemsArr = [...gemsMap.values()]
const start = Math.min(...gemsArr)
const end = Math.max(...gemsArr)
if (result[1] - result[0] > end - start) {
result = [start + 1, end + 1]
}
gemsMap.delete(gems[start])
}
}
return result
}겨우겨우 통과. 한 문제에 거의 이틀, 순 시간으로는 5시간? 정도 투자한 것 같다.
고생한만큼 점수는 올랐다(+9)
그만큼 내 실력이 올라갔기를 🙏
모범답안 참조
function solution(gems: string[]): number[] {
const gemVarietyCounts = new Set(gems).size
const gemMap = new Map()
const gemLengths: any[] = []
gems.forEach((gem, i) => {
gemMap.delete(gem)
gemMap.set(gem, i)
if (gemMap.size === gemVarietyCounts) {
gemLengths.push([gemMap.values().next().value + 1, i + 1])
}
})
gemLengths.sort((a, b) => {
if (a[1] - a[0] === b[1] - b[0]) {
return a[1] - b[1]
}
return a[1] - a[0] - (b[1] - b[0])
})
return gemLengths[0]
}
export default solution위 소스가 모범답인인데 나는 시간을 줄이기 위해 답안을 저장한 배열도 지우고 난리를 쳤는데 이 소스는 그 부분을 지우지 않고도 통과를 했더라.
어떤 부분이 차이인가 해서 보니
gems.forEach((gem, i) => {
gemMap.delete(gem)
gemMap.set(gem, i)
if (gemMap.size === gemVarietyCounts) {
gemLengths.push([gemMap.values().next().value + 1, i + 1])
}
})해당 부분에서 나는 start에 해당하는 부분을 구하기 위해 value()를 배열로 바꾸고([...values()]) Math.min, Math.max를 이용했는데
// 내 소스
const gemsArr = [...gemsMap.values()]
const start = Math.min(...gemsArr)
const end = Math.max(...gemsArr)
if (result[1] - result[0] > end - start) {
result = [start + 1, end + 1]
}
// 모범답안 소스
gemLengths.push([gemMap.values().next().value + 1, i + 1])여기서는 getMap.values().next().value를 이용해 최소값을 구했다.
getMap.values().next().value만 가져와서 내 소스코드에 적용해보니 최소값을 가져오지는 않기에 조금 더 찬찬히 뜯어보니
gemMap.delete(gem)
gemMap.set(gem, i)에서 gemMap.delete(gem)를 통해 보석을 삭제하고 다시 등록하여 gemMap의 보석 순서를 인덱스 순서와 동일하게 유지할 수 있었다.
그래서 getMap.values().next()가 제일 먼저 등록된 보석의 종류를 나타내는 것이었다.
그래서 내 소스코드도 바꿔보면…
진짜_최최최종.src
function solution(gems) {
const gemsKind = new Set(gems).size
const gemsMap = new Map()
let result = [0, Infinity]
for (let i = 0; i < gems.length; i++) {
gemsMap.delete(gems[i])
gemsMap.set(gems[i], i)
if (gemsMap.size === gemsKind) {
const start = gemsMap.values().next().value
const end = i
if (result[1] - result[0] > end - start) {
result = [start + 1, end + 1]
}
gemsMap.delete(gems[start])
}
}
return result
}