[Python] LeetCode Daily 연습

 

매일 문제 풀기~

 

Push Dominoes

class Solution:
    def pushDominoes(self, dominoes: str) -> str:

        if len(dominoes)==1:
            return dominoes

        a = ""
        ans = dominoes
        while a!=ans:
            a = ans
            ans = ""
            if a[1] == 'L' and a[0] == '.':
                ans = 'L'
            else:
                ans = a[0]
            
            for i in range(1, len(a)-1):
                if a[i] == '.':
                    if a[i-1] == 'R' and a[i+1] != 'L':
                        ans+='R'
                    elif a[i-1] != 'R' and a[i+1] == 'L':
                        ans+='L'
                    else:
                        ans+=a[i]
                else:
                    ans+=a[i]
            
            if a[-2] == 'R' and a[-1] == '.':
                ans += 'R'
            else:
                ans += a[-1]

        return ans

• 도미노가 한 칸씩 넘어가게 해서 더이상 변화가 없을 때까지 반복한다.
• O(N^2)으로 꽤 시간복잡도가 높게 나왔다.

 

# 솔루션
class Solution:
    def pushDominoes(self, d):
        d = 'L' + d + 'R'
        res = ""
        i = 0
        for j in range(1, len(d)):
            if d[j] == '.':
                continue
            middle = j - i - 1
            if i:
                res += d[i]
            if d[i] == d[j]:
                res += d[i] * middle
            elif d[i] == 'L' and d[j] == 'R':
                res += '.' * middle
            else:
                res += 'R' * (middle // 2) + '.' * (middle % 2) + 'L' * (middle // 2)
            i = j
        return res

• 투 포인터를 이용하여 O(N)으로 풀어낸 방식
• 먼저 계산을 편하게 하기 위해 양쪽에 L과 R을 붙인다.
• j는 오른쪽부터 도미노를 계산하기 위한 포인터, i는 왼쪽 도미노 계산 포인터 이다. 따라서 middle은 L혹은 R 도미노 사이에 낀 . 의 갯수가 된다.
• i, 즉 L/R 도미노 사이에 낀 . 도미노가 존재하는 경우, res(중간 결과물)에 왼쪽에 존재하는 도미노를 일단 추가한다.
• 이후 양쪽 도미노를 비교 후 바뀐 도미노들을 추가한다.
  • 만약 왼쪽과 오른쪽이 같은 방향의 도미노인 경우, middle갯수만큼 같은 방향의 도미노를 추가한다.
  • 만약 왼쪽은 L, 오른쪽은 R인 경우 중간에 있는 도미노는 영향이 없으므로 . 을 추가한다.
  • 만약 왼쪽이 R, 오른쪽이 L 인경우 R과 L이 각각 같은 갯수로 채운다. 홀수인 경우 가운데 . 은 그대로 .이 된다.
• 이제 다음 구간을 계산하기 위해 i에 j를 대입하고 반복한다.

 

 

Number of Equivalent Domino Pairs

class Solution:
    def numEquivDominoPairs(self, dominoes: List[List[int]]) -> int:
        ans = 0
        for i in range(len(dominoes)-1):
            for j in range(i+1, len(dominoes)):
                if (dominoes[i][0] == dominoes[j][0] and dominoes[i][1] == dominoes[j][1]) or (dominoes[i][1] == dominoes[j][0] and dominoes[i][0] == dominoes[j][1]):
                    # print(dominoes[i], dominoes[j], i, j)
                    ans += 1

        return ans

• 시간초과로 틀렸다

 

# 솔루션
def numEquivDominoPairs(self, A):
        return sum(v * (v - 1) // 2 for v in collections.Counter(tuple(sorted(x)) for x in A).values())

• tuple(sorted(x)) for x in A -> 각 도미노를 정렬한다. 즉, [1,2]와 [2,1] 을 동일하게 [1,2] 로 만들어준다.
• Counter 함수를 이용해 동일한 튜플의 갯수를 센다.
• 중복된 도미노 v개가 있을 때, 가능한 조합의 갯수는 vC2 = v*(v-1)//2 가 된다.

 

 

Domino and Tromino Tiling

# 솔루션
class Solution:
    def numTilings(self, n: int) -> int:
        if n<3:
            return n

        dp = [0] * (n + 1)
        dp[0], dp[1], dp[2] = 1, 1, 2

        for i in range(3, n + 1):
            dp[i] = (2 * dp[i - 1] + dp[i - 3]) % int(1e9+7)
        return dp[n]

• DP 문제...너무 어렵다..
• dp[n-1] (세로로 타일 1개 추가) + dp[n-1] (트로미노를 양쪽에 추가) + dp[n-3] (트로미노를 활용해 한번엥 3칸을 추가) = 2*dp[n-1] + dp[n-3] 점화식이 도출된다.
• 어렵다...

이렇게 놓는 패턴을 생각해보자:

위:   ◻️ ◻️ ◻️ ◻️
아래: ◼️ ◻️ ◻️ ◼️

← dp[3] →    ←   새로 추가한 영역   →

여기서 좌우 끝의 ◼️은 트로미노의 일부분이고,
각각 "ㄴ", "ㄱ 뒤집은 것" 형태로 대칭됨.

 

 

Build Array from Permutation

class Solution:
    def buildArray(self, nums: List[int]) -> List[int]:
        ans = []
        for i in nums:
            ans.append(nums[i])
        return ans

• 단순한 O(N) 풀이

 

Find Minimum Time to Reach Last Room I

• shortest path 알고리즘 중 어떤 걸 사용해야 하는지...헷갈렸다.
• [0][0] 에서 [n-1][m-1] 까지의 모든 거리 중 최선의 거리를 선택해야 하므로 다익스트라 사용

# 솔루션
class Solution(object):
    def minTimeToReach(self, moveTime):
        n = len(moveTime)
        m = len(moveTime[0])
        dp = [[float('inf')] * m for _ in range(n)]
        minh = []
        heapq.heappush(minh, (0, 0, 0))
        moveTime[0][0] = 0
        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        while minh:
            currTime, currRow, currCol = heapq.heappop(minh)
            if currTime >= dp[currRow][currCol]:
                continue
            if currRow == n - 1 and currCol == m - 1:
                return currTime
            dp[currRow][currCol] = currTime
            for dr, dc in directions:
                nextRow = currRow + dr
                nextCol = currCol + dc
                if 0 <= nextRow < n and 0 <= nextCol < m and dp[nextRow][nextCol] == float('inf'):
                    nextTime = max(moveTime[nextRow][nextCol], currTime) + 1
                    heapq.heappush(minh, (nextTime, nextRow, nextCol))
        return -1

• 먼저 도착했는지 확인하는 dp 배열과 [row, col, time] 을 저장하는 minh 배열 변수를 초기화 한다.
• heapq를 이용하여 가장 빠르게 도착할 수 있 노드를 처리한다.
• if currTime >= dp[currRow][currCol] 더 빠른 시간에 도달한 적이 있으면 건너뛴다.
• dp에 현재 도착한 시간을 저장하고, 4방향으로 아직 도달한 적이 없는 방이 있다면 해당 방에 도달하는 시간을 계산한 후 큐에 넣는다.
• nxmxlog(nxm)(우선순위 큐 연산 시간) 이 걸린다.

 

 

Find Minimum Time to Reach Last Room II

• time 변수를 만들어 1과 2를 번걸하 가며 nextTime에 더해주면 될 줄 알았는데..그렇게 단순하지는 않음
• 이동횟수에 따라 time을 다르게 더해야 한다. for문 마다가 아닌, minh에 이동횟수를 추가해 이에 따라 변수를 추가해준다.

class Solution(object):
    def minTimeToReach(self, moveTime):
        n = len(moveTime)
        m = len(moveTime[0])
        dp = [[float('inf')] * m for _ in range(n)]
        minh = []
        heapq.heappush(minh, (0, 0, 0, 0))
        moveTime[0][0] = 0
        directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        while minh:
            currTime, currRow, currCol, currMove = heapq.heappop(minh)
            if currTime >= dp[currRow][currCol]:
                continue
            if currRow == n - 1 and currCol == m - 1:
                return currTime
            dp[currRow][currCol] = currTime
            for dr, dc in directions:
                nextRow = currRow + dr
                nextCol = currCol + dc
                nextMove = currMove + 1
                if 0 <= nextRow < n and 0 <= nextCol < m and dp[nextRow][nextCol] == float('inf'):
                    time = 1 if currMove%2==0 else 2
                    nextTime = max(moveTime[nextRow][nextCol], currTime) + time
                    heapq.heappush(minh, (nextTime, nextRow, nextCol, nextMove))
        return -1

• 어제 푼 풀이에 Move 관련 변수와 변수에 따른 time 변수를 추가해 계산해준다.

 

Count Number of Balanced Permutations

from itertools import permutations

class Solution:
    def countBalancedPermutations(self, num: str) -> int:
        ans = 0
        result = list(permutations(num, len(num)))
        int_result = set([''.join(per) for per in result])
        # print(int_result)
        for s in int_result:
            a = str(s)
            if sum(int(a[i]) for i in range(0, len(a), 2)) == sum(int(a[i]) for i in range(1, len(a), 2)):
                ans = (ans+1)%(10**9+7)
        return ans

• permutations 로 만들 수 있는 문자열 구하고 하나씩 검사하기
• 당연하지만 엄청난 시간복잡도가 든다...

 

# 솔루션
class Solution:
    def countBalancedPermutations(self, num: str) -> int:
        cnt = Counter(int(ch) for ch in num)
        total = sum(int(ch) for ch in num)

        @cache
        def dfs(i, odd, even, balance):
            if odd == 0 and even == 0 and balance == 0:
                return 1
            if i < 0 or odd < 0 or even < 0 or balance < 0:
                return 0
            res = 0
            for j in range(0, cnt[i] + 1):
                res += comb(odd, j) * comb(even, cnt[i] - j) * dfs(i - 1, odd - j, even - cnt[i] + j, balance - i * j)
            return res % 1000000007

        return 0 if total % 2 else dfs(9, len(num) - len(num) // 2, len(num) // 2, total // 2)

 

• DFS + DP로 풀기
• 먼저 각 숫자의 갯수와 숫자의 합을 구한다. 숫자의 합 total이 홀수인 경우 답이 될 수 없으므로 return에서 거른다.
• 파라미터는 숫자 0~i 중 odd는 남은 홀수 자리 개수, even은 남은 짝수 자리 개수, balance는 짝수자리 합==홀수자리 합 이 되기 위해 남은 balance의 차이
• 만약 파라미터들이 0이 되면 유효한 순열이고, 아니면 유효하기 않다.
• cnt[i] 개의 숫자 i를 각 자리에 둔다. 이때 comb(odd, j)*comb(even, cnt[i]-j) 는 홀수 자리에 j개* 짝수 자리에 나머지 개수를 놓는 경우의 수를 의미한다.
• 이후 자리 수와 balance를 가지고 DFS 재귀. balance는 i숫자 j개가 들어갔으므로, 짝수==홀수를 위해 balance - i*j가 된다.
• 최종적으로 total의 절반을 목표로 균형을 맞춘다.
• 즉 순열을 직접 구하지 않고, 균형 조건을 만족하는 배치를 계산한다.

 

 

---

# 회고

 

어렵다.

마지막 문제는 hard 였는데 확실히 DFS+DP 문제가 나온다..