[Mock] Random 6

뜻밖의 유튜브 감상으로 인해... 제시간에 안풂 ㅎ..

---

788. Rotated Digits

X is a good number if after rotating each digit individually by 180 degrees, we get a valid number that is different from X. Each digit must be rotated - we cannot choose to leave it alone.

A number is valid if each digit remains a digit after rotation. 0, 1, and 8 rotate to themselves; 2 and 5 rotate to each other (on this case they are rotated in a different direction, in other words 2 or 5 gets mirrored); 6 and 9 rotate to each other, and the rest of the numbers do not rotate to any other number and become invalid.

Now given a positive number N, how many numbers X from 1 to N are good?

My Answer 1: Accepted (Runtime: 80 ms - 68.73% / Memory Usage: 14.2 MB - 53.10%)

class Solution:
    def rotatedDigits(self, N: int) -> int:
        cnt = 0
        
        for i in range(N+1):
            tmp = list(str(i))
            if "3" in tmp or "4" in tmp or "7" in tmp:
                continue
            if "2" in tmp or "5" in tmp or "6" in tmp or "9" in tmp:
                cnt += 1
        
        return cnt

이거 어려운 문제가 아닌데 문제를 잘못 읽어서 삽질하다 시간 다갔다...ㅎ

회전 가능한 숫자들만 회전시켜서 원래 숫자와 값이 다른지를 비교함.. 왜그랬지;

모든 숫자가 회전 가능해야 한다.

• string은 immutable type
  replace 나 list 이용해야 함

---

849. Maximize Distance to Closest Person

You are given an array representing a row of seats where seats[i] = 1 represents a person sitting in the ith seat, and seats[i] = 0 represents that the ith seat is empty (0-indexed).

There is at least one empty seat, and at least one person sitting.

Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized.

Return that maximum distance to the closest person.

My Answer 1: Accepted (Runtime: 3452 ms - 5.02% / Memory Usage: 14.5 MB - 93.21%)

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        dis = [0]*len(seats)
        
        left = 0
        
        for i in range(len(seats)):
            right = float('inf')
            if seats[i] == 0:
                if 1 in seats[i:]:
                    right = seats[i:].index(1)
                if left:
                    dis[i] = min(left, right)
                    left += 1
                elif right != float('inf'):
                    dis[i] = right
            else:
                left = 1
        
        return max(dis)

좀 느리긴 하지만..

left 와 right 에 존재하는 1 과의 거리를 구해서 최솟값을 dis 리스트에 넣어줌

최종적으로 dis 의 최댓값이 답이 된다.

Solution 1: Accepted (Runtime: 152 ms - 24.61% / Memory Usage: 14.9 MB - 32.79%)

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        N = len(seats)
        left, right = [N] * N, [N] * N

        for i in range(N):
            if seats[i] == 1: left[i] = 0
            elif i > 0: left[i] = left[i-1] + 1

        for i in range(N-1, -1, -1):
            if seats[i] == 1: right[i] = 0
            elif i < N-1: right[i] = right[i+1] + 1

        return max(min(left[i], right[i])
                   for i, seat in enumerate(seats) if not seat)

left, right 를 쓰는 건 비슷한데 이건 왼->오를 보면서 left 를 구해주고 오->왼을 보면서 right 를 구함

그러고 두 리스트의 값 중 최솟값만 리스트로 둔다고 생각하고 그 중에서 최댓값을 구하면 된다

2 pointer 도 비슷하다. => 1 들의 index 만 구해서 첫 값은 left, 그 다음 값은 right로 두고 하면 됨

Solution 2: Accepted (Runtime: 120 ms - 97.84% / Memory Usage: 14.6 MB - 93.21%)

class Solution:
    def maxDistToClosest(self, seats: List[int]) -> int:
        ans = seats.index(1)
        seats.reverse()
        ans = max(ans,seats.index(1))
        for seat, group in itertools.groupby(seats):
            if not seat:
                K = len(list(group))
                ans = max(ans, (K+1)//2)

        return ans

요건 좀 수학적으로 접근한 줄 알았는데... 뭔소린지

맨 처음 1 의 index 랑 맨 마지막 1 의 index 중 최댓값을 이용

itertools.groupby 가 자동으로 그룹화 해주는데... 어떻게 그렇게 되지...?