🍀 할인 행사

이 문제를 처음 봤을 때 O(n^2)으로 밖에는 생각이 나지 않았다. 하지만, number의 길이가 1이상 10이하이며 number 요소의 값은 최대가 10이므로 number의 합 만큼 for구문을 돈다고 가정하면 O(100)이므로 문제를 통과하는데 이상없다고 판단해서 이중 for구문을 이용한 구현으로 문제를 해결하였다. 이 문제를 블로그로 올리는 이유는 python에서 collection의 counter와 javascript에서 hasOwnProperty의 시간 복잡도 O(1)임을 알아서 정리한다.

1️⃣ Python

아래는 첫 번째 풀이로 1, 2, 3을 마킹한 곳에서 개선점은 아니지만 다르게 코드를 쓸 수 있는 점과 in keyword를 이용하여 key값이 존재하는지 아닌지에 대한 시간 복잡도는 O(1)이라는 점이다. 밑에서 언급하겠지만 javascript에서 항상 Object.keys(객체).includes(targetKey)로 키 값이 존재하는지 check했지만, 이는 O(n)을 갖는다. javascript도 객체에서 key값을 찾는데 O(1)의 시간 복잡도를 가질 수 있다.

# 첫 번째 풀이
def get_want_counter(wants, numbers):
    answer = 0
    result = dict()
    
    for want, number in zip(wants, numbers):
        result[want] = number
        
    return result

def solution(wants, numbers, discounts):
    answer = 0
    num_wants = sum(numbers)
    want_counter = get_want_counter(wants, numbers) # 👉🏻 1️⃣
    
    for idx in range(len(discounts) - num_wants + 1):
        copy_want_counter = want_counter.copy()
        
        for j in range(idx, num_wants + idx):
            if discounts[j] not in want_counter: break # 👉🏻 2️⃣
            
            copy_want_counter[discounts[j]] -= 1
            
        if set(copy_want_counter.values()) == {0}: # 👉🏻 3️⃣
            answer += 1
    
    return answer

• 👉🏻 1️⃣: 이 부분은 원하는 품목과 이에 대한 개수를 dictionary형태로 반환하는 함수 이다. 하지만, list comprehension을 이용하여 간략하게 코드를 줄일 수 있다.

def get_want_counter(wants, numbers):
    answer = 0
    result = dict()
    
    for want, number in zip(wants, numbers):
        result[want] = number
        
    return result
   
want_counter = get_want_counter(wants, numbers) # 👉🏻 1️⃣
=======================================================
# 개선
want_counter = {name: count for name, count in zip(wants, numbers)}

• 👉🏻 2️⃣: python에서 항상 그냥 쓰던 in keyword의 시간 복잡도는 O(1)이다.

if discounts[j] not in want_counter: break # 

💡💡 이유는 딕셔너리의 키 값을 해싱처리한 후 찾을 때 해시값을 통해 접근하는데 접근 후 유무를 판단하므로 시간 복잡도가 O(1)이다.

• 👉🏻 3️⃣: 모든 value의 값이 0이어야지 원하는 품목을 모두 구매함을 검증할 수 있으므로 이를 set을 이용해서 처리했는데 set말고도 이번에 알게된 all method를 이용하여 풀 수도 있다.

if set(copy_want_counter.values()) == {0}: 
	answer += 1

=======================================================

if all(num == 0 for num in want_counter.values()): # 👉🏻 all method 사용
	 answer += 1

💡💡 all method를 이용하여 모든 값이 내가 원하는 값을 갖는지에 대한 것을 찾을 수 있다.

🛠️ 나름 적용해 본 코드

def solution(wants, numbers, discounts):
    answer = 0
    num_wants = sum(numbers)
    
    for idx in range(len(discounts) - num_wants + 1):
        want_counter = {name: count for name, count in zip(wants, numbers)}
        
        for j in range(idx, num_wants + idx):
            if discounts[j] not in want_counter: break
            
            want_counter[discounts[j]] -= 1
            
        if all(num == 0 for num in want_counter.values()):
            answer += 1
    
    return answer

코드를 고친 이유는 새로 배운 내용도 정리할 겸 간결한 코드로 가독성이 좋은 코드로 탄생시킬 수 있을 것 같아서 코드를 바꿔보았다. list comprehension으로 dictionary를 만들 때 너무 길지만 않으면 알아보기가 쉬우며 코드 자체가 무엇을 하고 있는지 직관적으로 알 수 있는 all method를 이용하면 다른 사람이 봤을 때 set을 이용한 풀이보다도 더 직관적으로 코드를 파악할 수 있을 것이다.

2️⃣ Javascript

function solution(wants, numbers, discounts) {
    let answer = 0;
    const numWants = numbers.reduce((a, b) => a + b);
    
    for (let i = 0; i < discounts.length - numWants + 1; i++){
        const wantCounter = wants.reduce((acc, cur, idx) => {
            acc[cur] = (acc[cur] || 0) + numbers[idx];
            return acc;
        }, {})
        
        for (let j = i; j < numWants + i; j++){
            if (!wantCounter.hasOwnProperty(discounts[j])) break; // 👉🏻 1️⃣
            wantCounter[discounts[j]] -= 1;
        }
        
        Object.values(wantCounter).every(num => num === 0) && answer++; // 👉🏻 2️⃣
    }
    
    return answer;
}

여기서 눈 여겨 봐야할 점을 1️⃣부분이다. 위에서 언급했듯이 내가 알고 있던 key의 값이 존재하는지에 대한 유무는 지금까지 O(n)으로 풀었지만 hasOwnProperty를 이용하면 O(1)의 시간 복잡도로 해결할 수 있다. 또한 2️⃣에서 python에서의 any = js의 some && python에서의 all = js의 every와 같다.

• python any method = js some method
• python all method = js every method

⽐ includes VS hasOwnProperty

hasOwnProperty가 내가 기존에 비교하던 것과 얼마나 차이가 나나 실감해보기 위해서 아래와 같은 테스트 코드를 짰다.

const createTestObj = (objLength) => {
  const result = {};

  for (let idx = 0; idx < objLength; idx++){
    result[idx] = true;
  }

  return result;
}

const OBJ_LENGTH = 100_000_000
const testObj = createTestObj(OBJ_LENGTH)
const target = 99_999_999;

const s1 = performance.now()
console.log(Object.keys(testObj).includes(target.toString()));
const s2 = performance.now()
console.log(`includes 사용 시 👉🏻 ${(s2 - s1) / 1000}초 걸림`);

console.log(testObj.hasOwnProperty(target));
const s3 = performance.now()
console.log(`hasOwnProperty 사용 시 👉🏻 ${(s3 - s2) / 1000}초 걸림`);

흠..... 시간 = 돈이라는 생각만 든다....;; O(n)도 엄청 빠른 것 같지만 상수시간에는 비비지 못 한다.......;;🥺

🔥 마치며

이번에는 pyhon과 js에 있는 all, any, every, some 메서드를 사용하여 좀 더 직관적으로 코드를 짤 수 있는 방법과 python에서 in keyword로 딕셔너리 key값을 참조하는데의 시간 복잡도는 O(1)이다. 이와 마찬가지로 javascript에서 hasOwnProperty메서드를 사용하면 동일한 퍼포먼스를 기대할 수 있음을 알았다. 항상 느끼는 거지만 나중에 내가 코드를 봤을 때 코드를 봤을 때 이해하기 쉬우려면 직관적으로 코드를 짜는 습관이 중요한 것 같으며 공부는 끝이 없다. 🥺🥺 but, 재미는 있음🔥🔥🔥