biweekly-contest-42

leetcode.com/contest/biweekly-contest-42.  

 

 

 

 

leetcode.com/problems/number-of-students-unable-to-eat-lunch/  

 

문제에 기술된 그대로의 코드

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:    
        n = len(students)
        ans = n
        start = 0
        for sandwich in sandwiches:
            found = False
            print(start, start+n)
            for i in range(start, start+n):
                idx = i % n
                start = (idx+1)%n
                if students[idx] == sandwich:
                    ans -= 1
                    students[idx] = -1
                    found = True
                    break
            if found == False:
                return ans
        
        print(students)
        print(sandwiches)
        return ans

 

비슷한 솔루션

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int:
        eaten = 0
        n = len(students)
        sandwiches = sandwiches[::-1]
        visited = [False] * n
        
        while True:
            exit = True
            
            for i in range(n):
                if visited[i]:
                    continue
                if students[i] == sandwiches[-1]:
                    eaten += 1
                    visited[i] = True
                    exit = False
                    sandwiches.pop()
            
            if exit:
                break
        
        
        return len(students) - eaten

 

 

원리를 이해했다면 파이썬의 카운터를 이용하여 이렇게 풀수있다.

class Solution:
    def countStudents(self, students: List[int], sandwiches: List[int]) -> int: 
        prefer_count = collections.Counter(students)
        n, sw_idx = len(sandwiches), 0
        for sandwich in sandwiches:
            if prefer_count[sandwich]:
                prefer_count[sandwich] -= 1
                n -= 1
            else:
                break
        return n

 

 

 

 

 

leetcode.com/problems/average-waiting-time/

 

class Solution:
    def averageWaitingTime(self, customers: List[List[int]]) -> float:
        served = 0
        total = 0
        for arrival, preparing in customers:
            served = preparing + max(served, arrival)
            total += served - arrival
        return total / len(customers)

 

 

 

 

leetcode.com/problems/maximum-binary-string-after-change/

이문제는 앞부분을 최대한 1로 채우는 것이다.

00을 10으로 바꿀수있고, 10을 01로 바꿀수 있다.

앞에서부터 탐색하며 00이 있으면 10으로 바꾸고,

그때 뒤에 또 0이와서 100이되면 또 01로 바꾸면되지만,

그 뒤에 1이 온다면 101이 되고 그 후에 나오는 0을 찾아서 01로 만들어주면서 앞으로 오다보면 여기서 문제되는 부분인 101을 100으로 바꿀수있고, 따라서 110으로 변경이 가능하다.

 

따라서 스트링에 0이 하나만 남을때까지 하면 되는데, 그게 어디인지를 찾는것이 이 문제이다.

 

정답은

0이 나오기 전까지 원래 있던 1의 수 + 0의 개수만큼의 1 + 새로만들어진0(00->10 혹은 10->01)+나머지글자수만큼의1이다.

 

 

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        first_zero_idx = binary.find('0')
        print(first_zero_idx)
        if first_zero_idx < 0:
            return binary
        
        n = len(binary)
        zeros = binary.count('0')
        left_ones = first_zero_idx-1 + zeros
        right_ones = n - left_ones - 1
        return '1'* left_ones + '0' + '1' * right_ones

 

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        n=len(binary)
        idx=binary.find('0')
        if idx==-1:
            return binary
        cnt=binary.count('0')
        return "1"*(idx+cnt-1)+"0"+"1"*(n-idx-cnt)

 

 

 

 

leetcode.com/problems/minimum-adjacent-swaps-for-k-consecutive-ones/  

오늘도 HARD는 skip