[JS|해시] 프로그래머스 131127번. 할인 행사

 

프로그래머스

 

---

1. 입력과 출력

• 입력
  • 정현이가 원하는 제품을 나타내는 문자열 배열 want
  • 정현이가 원하는 제품의 수량을 나타내는 정수 배열 number
  • XYZ 마트에서 할인하는 제품을 나타내는 문자열 배열 discount
• 출력
  • 회원등록시 정현이가 원하는 제품을 모두 할인 받을 수 있는 회원등록 날짜의 총 일수 return

 

2. 시행착오

• 출력값 이해를 잘 못함 : 회원 등록 날짜의 총 일수가 아니라 회원 등록 최소 일자를 찾았었다..! (+ 10분)

 

3. 문제 풀이 로직

문제 풀이 로직 설명

• 회원 등록을 할 수 있는 날짜의 갯수를 세면 된다!

 

---

• 제품 목록 want 배열과 가격 number 배열로 해시테이블 만들어놓기

  let hashTable = new Object()

  // 1. 제품 목록 want배열과 가격 number 배열로 해시테이블 만들어놓기
  want.map((item, idx) => (hashTable[item] = number[idx]))

 

• 1일차 ~ 10일차 제품들을 미리 해시테이블에서 빼기 (구매할 것들 목록)

  // 2. 1일 차 ~ 10일 차 제품들을 미리 해시테이블에서 빼기 (구매할 것들)
  discount.slice(0, 10).map((item) => {
    if (want.includes(item)) hashTable[item]--
  })

 

 

• 10개의 제품이 포함되는 일자까지만 반복문 돌기
  • 일자가 지난 제품은 구매하지 않음 : hashTable[이전 일자]++
  • 일자가 다가온 제품은 구매함 : hashTable[다음 일자]--

  // 3. 10개 제품의 목록이 포함되는 일자까지만 반복문 돌기
  let answer = checkDiscount(hashTable) ? 1 : 0
  for (let i = 1; i <= discount.length - 10; i++) {
    hashTable[discount[i - 1]]++ // 이전 제품은 구매 안함
    hashTable[discount[i + 9]]-- // 다음 제품은 구매 함

    // 만약 모든 제품을 구매에 성공하였다면, 해당 일차는 회원등록가능날짜이므로 +1
    if (checkDiscount(hashTable)) answer++
  }
  console.log(answer)
  return answer

 

• 모든 제품을 구매했는지 확인할 수 있는 헬퍼함수 checkDiscount
  • hashTable 내 제품 중 구매를 하지 못한 ( > 0 ) 제품이 있다면 return false
  • 모든 것을 다 구매하였다면 return true

function checkDiscount(hashTable) {
  for (const Item in hashTable) {
    if (hashTable[Item] > 0) return false
  }
  return true
}

 

 

풀이 시간 및 시간 복잡도 설명

• 총 60분 풀이
• 시간복잡도 : O(N)
  • 제품 목록(N)을 돌며 hashTable에 저장함 -> O(N)
  • 할인 제품 목록을 10개 자름 -> O(10)
  • 10개 제품의 목록이 포함되는 일자까지만 반복문 실행 -> O(N-10)

 

 

4. 전체 코드

// 2. 할인 행사
function solution(want, number, discount) {
  let hashTable = new Object()

  // 1. 제품 목록 want배열과 가격 number 배열로 해시테이블 만들어놓기
  want.map((item, idx) => (hashTable[item] = number[idx]))

  // 2. 1일 차 ~ 10일 차 제품들을 미리 해시테이블에서 빼기 (구매할 것들)
  discount.slice(0, 10).map((item) => {
    if (want.includes(item)) hashTable[item]--
  })

  // 3. 10개 제품의 목록이 포함되는 일자까지만 반복문 돌기
  let answer = checkDiscount(hashTable) ? 1 : 0
  for (let i = 1; i <= discount.length - 10; i++) {
    hashTable[discount[i - 1]]++ // 이전 제품은 구매 안함
    hashTable[discount[i + 9]]-- // 다음 제품은 구매 함

    // 만약 모든 제품을 구매에 성공하였다면, 해당 일차는 회원등록가능날짜이므로 +1
    if (checkDiscount(hashTable)) answer++
  }
  console.log(answer)
  return answer
}

function checkDiscount(hashTable) {
  for (const Item in hashTable) {
    if (hashTable[Item] > 0) return false
  }
  return true
}