Greedy

stack

2 pointer approach

balloon question (sorting by end index)

Practice question

큰 수 만들기

https://school.programmers.co.kr/learn/courses/30/lessons/42883

My first approach was not greedy but to generate all possibilities of combinations and sort and get the highest value. But time complexity was really bad here

def solution(number, k):
  length = len(number)-k
  perms = [''.join(map(str,perm)) for perm in combinations(number,length)]
  print(perms)
  print(sorted(perms,reverse=True)[0])
  return sorted(perms,reverse=True)[0]

Then, I sought help from sensei GPT. We can use greedy algorithm with stack to iteratively build the resulting number by selecting the maximum digit at each step.

I tried that but strangely, this didnt work for “4177252841”, 4.

def solution(nums, k):
  count =0
  stack = deque()
  for num in nums:
    if not stack:
      stack.append(num)
      continue
    while stack:
      if stack[-1] <num and count<k:
        stack.pop()
        stack.append(num)
        count+=1
      else:
        stack.append(num)
      break
  # stack.reverse()  # Reverse the stack in-place
  result = ''.join(stack)
  print(result)
  return result

I think there is something wrong with the if condition inside my while loop.

Correct solution

from itertools import permutations,combinations
from collections import deque,defaultdict
def solution(nums, k):
    count = 0
    stack = deque()
    for num in nums:
        if not stack:
            stack.append(num)
            continue
        
        while stack and stack[-1] < num and count < k:
            stack.pop()
            count += 1
        stack.append(num)
    # official solution to handle edge case
    # while count < k:
    #     stack.pop()
    #     count += 1
    
    # my way
    while len(stack)>len(nums)-k:
      stack.pop()
    
    result = ''.join(stack)
    # print(result)
    return result

Notice that we have to handle edge case of solution(“4321”, 1) where our count is still not >=k. Then, our stack is too long so we need to pop the last element accordingly and increment count until stack is of appropriate length.

구명보트

https://school.programmers.co.kr/learn/courses/30/lessons/42885

Right away I thought of 2 pointer approach but was not sure how to increment boat count. But we do it like

my correct code:

def solution(people, limit):
  people.sort()
  count =0
  left = 0
  right = len(people)-1
  while(left<=right):
    if(people[left]+people[right]<=limit):
      count+=1
      left+=1
      right-=1
    else:
      right-=1
      count+=1
  print(count)
  return count

official solution excluded the else statement like this. This is better

def solution(people, limit):
    people.sort()  # Sort the people in ascending order of weight
    left = 0  # Pointer for the lightest person
    right = len(people) - 1  # Pointer for the heaviest person
    boats = 0  # Count of lifeboats used
    
    while left <= right:
        if people[left] + people[right] <= limit:
            left += 1  # Move the left pointer to the next person
        right -= 1  # Move the right pointer to the next person
        boats += 1  # Increment the count of lifeboats used
    
    return boats

체육복

https://school.programmers.co.kr/learn/courses/30/lessons/42862

initial code that I tried but gotten wrong

def solution(n, lost, reserve):
  students=[i for i in range(n+1)]
  while reserve or lost:
    for r in reserve:
      if r-1 in lost or r+1 in lost:
        lost.pop(0)
        reserve.pop(0)
  print(n-len(lost))
  return n-len(lost)


solution(5, [2, 4], [1, 3, 5])

The loop condition while reserve or lost will continue the loop and also this pop when debugging skips the next element and iter goes to the next next element so wtf?

correct but slow

def solution(n, lost, reserve):
  students = [i for i in range(n+1)]
  while reserve and lost:
    for r in reserve:
      if r-1 in lost:
        lost.remove(r-1)
        reserve.remove(r)
        break
      elif r+1 in lost:
        lost.remove(r+1)
        reserve.remove(r)
        break
  print(n - len(lost))
  return n - len(lost)

Why do you need break? The break statement is used to exit the inner for loop once a match is found and a uniform is allocated from the reserve list. It helps to prevent unnecessary iterations and ensures that only one uniform is allocated per student from the reserve list.

Without the break statement, the loop would continue iterating even after finding a match, potentially leading to incorrect results or redundant operations. By breaking out of the loop, we can proceed to the next iteration of the outer while loop and continue checking for other potential matches.

We can make it more efficient though like

def solution(n, lost, reserve):
    students = [1] * (n+2)  # Initialize a list with all students having 1 uniform initially
    for l in lost:
        students[l] -= 1  # Mark students who lost uniforms with 0
    for r in reserve:
        students[r] += 1  # Mark students who have extra uniforms with 2

    for i in range(1, n+1):
        if students[i] == 0:
            if students[i-1] == 2:
                students[i] = 1
                students[i-1] = 1
            elif students[i+1] == 2:
                students[i] = 1
                students[i+1] = 1

    answer = sum(1 for s in students[1:-1] if s >= 1)
    print(answer)
    return answer

solution(5, [2, 4], [1, 3, 5])

What is this sum doing? 1 for s in students[1:-1] if s >= 1 is a generator expression that generates a value of 1 for each student who satisfies the condition s >= 1.

sum(1 for s in students[1:-1] if s >= 1) calculates the sum of all the generated 1 values, effectively counting the number of students who have at least 1 uniform.

model solution:

def solution(n, lost, reserve):
    reserve_uniq = set(reserve) - set(lost)
    lost_uniq = set(lost) - set(reserve)

    for i in reserve_uniq :
        if i-1 in lost_uniq :
            lost_del.remove(i-1)
        elif i+1 in lost_del :
            lost_del.remove(i+1)
        
    return n - len(lost_del)

btw if set’s elements don’t match like (1,3,5) - (2,4) is still (1,3,5).

단속카메라

https://school.programmers.co.kr/learn/courses/30/lessons/42884

my correct solution

def solution(routes):
  routes.sort(key=lambda x:x[1])
  print(routes)
  count=1
  block=routes[0][1]
  print(block)
  for start,end in routes:
    if block<=end and start<=block:
      continue
    else:
      count+=1
      block = end
  print(count)
  return count

This is similar to shooting ballons with minimum arrows on Leetcode but I was confused as to which index to sort. Should I sort first or second index?

Let’s say first index and examine this case


              | <-arrow
##############
   ########
                    ###############

see our arrow can’t penetrate the second case.

So we have to sort via the end index like

           | <-arrow
    #######
################
                     ###################

Now our arrow penetrates the second case.