[카카오 인턴] 보석 쇼핑

문제 링크

#효율성

문제 요약

Input

진열대 번호 순서대로 보석들의 이름이 저장된 배열 gems

output

가장 짧은 구간의 시작 진열대 번호와 끝 진열대 번호를 차례대로 배열에 담아서 return 하도록 하며, 만약 가장 짧은 구간이 여러 개라면 시작 진열대 번호가 가장 작은 구간을 return 합니다.

해결방법

효율성을 제치고 떠오르는 가장 간단한 방법으로 생각해보자

1. 제일 앞에서부터 보석의 수량 + n만큼 골라서 전체 보석의 수량과 일치하는지 확인하는 방법

정확도에는 이상이 없지만 시간초과 발생 2. 투포인터 알고리즘

1. 문제 자체는 전형적인 투포인터 알고리즘이지만... 그렇게 풀면 시간 초과가 발생한다.(내가 잘못한 걸지도?)
2. Map을 이용
   1. 순회를 하면서
   2. Map에 보석을 담고
   3. 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번에서 시간초과 발생...

다시 소스코드를 뜯어보자....

개선

속도 개선이 이뤄질만한 부분은 두 부분이다.

1. results에 모아서 처리하지 말고 조건에 맞는 답을 찾았을 때 비교해서 가지고 있는다.
2. gemsMap에 보석이 모였을 때 entries().sort()하는 부분에서 시간복잡도가 추가된다.
   1. 보석의 종류가 많으면 많을수록 정렬시간이 추가되고 이로 인해 O(n)같아 보이지만 o(n^2)으로 변한다.
   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
}