Welcome to My IT World

코딩테스트 연습 - 할인 행사

문제요약

일정금액 지불 → 10일간 회원

회원 대상 매일 1가지 제품 할인

할인 제품은 하루에 하나씩만

정현이는 자신이 원하는 제품과 수량이 할인하는 날짜와 10일 연속으로 일치한 경우 회원가입 하려고 함

정현이가 가입 가능한 날짜의 총 일수 return

없으면 return 0

입력

1 ≤ want(원하는 제품 문자열 배열), number(원하는 수량 배열) ≤ 10

10 ≤ discount 배열 길이 ≤ 10^5

1 ≤ number의 원소 ≤ 10

number의 원소 합 = 10

출력

return int

불가능하면, return 0

어떻게 풀까?

discount 범위를 생각할 때, O(NlogN) 정도까지 가능

회원가입 일수가 10일 → 슬라이딩 윈도우?

⇒ 회원가입 일수가 10일일 뿐, 1일 안에도 정현이의 want가 모두 채워질 수 있음

⇒ 투포인터로 적용해서 discount for문 한 바퀴(10^5) 돌리면서 조정해주고 그 안에서 want 길이(10)만큼 돌면서 모두 충족되었는지 검사해도 시간복잡도 충분할듯

내 코드

def check_satisfied(want_num):
    for want in want_num.keys():
        if want_num[want] > 0:
            return False
    return True

def solution(want, number, discount):
    # 데이터 전처리(want, number-> dict)
    want_num = dict()
    for i in range(len(want)):
        want_num[want[i]] = number[i]
    # answer 초기화
    answer = 0
    # discount 돌면서 투포인터 적용
    start = 0
    end = 0
    # 초기화 처리
    if discount[start] in want and want_num[discount[start]] > 0:
        want_num[discount[start]] -= 1
    while end < len(discount):
        days = end - start + 1
        # 10일 초과 -> start += 1
        if days > 10:
            if discount[start] in want:
                want_num[discount[start]] += 1
            start += 1
        # 10일 전까지 -> 검사
        elif check_satisfied(want_num):
            answer += 1
            if discount[start] in want:
                want_num[discount[start]] += 1
            start += 1
        # 그 외의 경우
        else:
            end += 1
            if end == len(discount): break
            if discount[end] in want:
                want_num[discount[end]] -= 1
    return answer

코딩테스트 연습 - 두 큐 합 같게 만들기

문제요약

길이가 동일한 큐 2개가 주어짐

하나의 큐에서 추출해서 다른 큐에 삽입함 : FIFO 방식으로 진행

추출+삽입 = 1회

두 큐의 합이 같아질 수 있는 최소 횟수 return

만일, 불가능하면 -1 return

입력

1≤ 각 q의 길이 ≤ 3*10^5

1≤ q의 원소 ≤ 10^9

출력

return int

불가능하면, return -1

어떻게 풀까?

1. 일단, 입력 값의 범위를 봤을 때, O(n^2)는 불가능하고 O(nlogn) 정도까지는 가능
2. 제일 먼저 예외처리를 할 수 있는 건, 두 큐의 합이 짝수가 아닐 때! 큐의 합을 모두 더해서 짝수가 아니면 바로 return -1을 해주자!
3. 가장 간단하게 푸는 방법?
   while 문 돌리면서 각 큐의 합을 비교하고 큰 큐에서 값을 빼서 작은 큐에 넣어주는 것 반복 어차피 FIFO 방식이기 때문에, 결국 돌고 돌면서 크고 작음이 조율될 것!
   이때 문제는, 이게 얼마나 돌아야 return -1 판별이 가능한지임 사실 두 q 길이의 합 만큼 돌리면 원상복귀이기 때문에 더 이상 돌 필요가 없음! => 두 q 길이의 합은 2*3*10^5 로 충분히 가능!
4. 이 때, 주의할 점은 deque로 만들어주고 해야한다는 점! 배열에서 바로 pop(0)을 해주면, O(N)이 걸리기 때문(배열에서 앞에걸 빼면 뒤에 원소들도 다 자리이동을 시키기 때문에)에 시간초과가 남 ⇒ deque popleft() 이용 : O(1)

내 코드

다르게 푸는 방법?

투포인터 활용하기!

def solution(queue1, queue2):
    target = (sum(queue1) + sum(queue2)) // 2
    cur = sum(queue1)
    queue3 = queue1 + queue2 + queue1

    s = 0
    e = len(queue1) - 1
    answer = 0
    while True:
        if cur == target:
            return answer
        if cur < target:
            e += 1
            if e >= len(queue3):
                return -1
            cur += queue3[e]
        else:
            cur -= queue3[s]
            s += 1
        answer += 1

" 위 풀이코드 출처 : algorithm-ps/두 큐 합 같게 만들기.md at main · dali0202/algorithm-ps "  

위 코드에서 유심히 볼 점!

단순히 q1+q2로 합치지 않고 q1+q2+q1를 해준 점

아래와 같은 경우가 있을 수 있음