[Mock] Random 19

easy 와 hard 라뇨...

---

819. Most Common Word

Given a string paragraph and a string array of the banned words banned, return the most frequent word that is not banned. It is guaranteed there is at least one word that is not banned, and that the answer is unique.

The words in paragraph are case-insensitive and the answer should be returned in lowercase.

My Answer 1: Accepted (Runtime: 36 ms - 64.06% / Memory Usage: 14.1 MB - 97.78%)

import re

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        paragraph = re.sub("[^a-zA-Z0-9]", " ", paragraph)
        paragraph = paragraph.lower()
        words = paragraph.split()
        dic = list(set(words))
        
        for i in range(len(banned)):
            if banned[i] in dic:
                dic.remove(banned[i])
                
        cnt = [0]*len(dic)
        
        for i in range(len(words)):
            if words[i] in dic:
                idx = dic.index(words[i])
                cnt[idx] += 1
        
        m = max(cnt)
        return dic[cnt.index(m)]

문자 외의 값들은 모두 공백으로 바꿔주고 모두 소문자로 변경한 후 단어들만 words 로 쪼갬

dic 에는 중복과 banned 값을 제거한 단어들을 넣어준다.

다시 words 값을 보면서 개수를 세서 cnt 에 저장

cnt max 값에 대응하는 dic 값 return

---

675. Cut Off Trees for Golf Event

You are asked to cut off all the trees in a forest for a golf event. The forest is represented as an m x n matrix. In this matrix:

• 0 means the cell cannot be walked through.
• 1 represents an empty cell that can be walked through.
• A number greater than 1 represents a tree in a cell that can be walked through, and this number is the tree's height.

In one step, you can walk in any of the four directions: north, east, south, and west. If you are standing in a cell with a tree, you can choose whether to cut it off.

You must cut off the trees in order from shortest to tallest. When you cut off a tree, the value at its cell becomes 1 (an empty cell).

Starting from the point (0, 0), return the minimum steps you need to walk to cut off all the trees. If you cannot cut off all the trees, return -1.

You are guaranteed that no two trees have the same height, and there is at least one tree needs to be cut off.

My Answer 1: Wrong Answer (21 / 54 Testcases Passed)

class Solution:
    def cutOffTree(self, forest: List[List[int]]) -> int:
        def func(i, j):
            #print(i, j)
            forest[i][j] = -2
                
            a, b, c, d = float('inf'), float('inf'), float('inf'), float('inf')
            m = float('inf')
            
            #if i < 0 or i > len(forest[i])-1 or j < 0 or j > len(forest)-1:
            #    return
            
            if i < len(forest)-1:
                if forest[i+1][j] > 0:
                    a = forest[i+1][j]
            if i > 0:
                if forest[i-1][j] > 0:
                    b = forest[i-1][j]
            if j < len(forest[i])-1:
                if forest[i][j+1] > 0:
                    c = forest[i][j+1]
            if j > 0:
                if forest[i][j-1] > 0:
                    d = forest[i][j-1]
                
            m = min(m, a, b, c, d)
            
            if m == float('inf'):
                return
            
            if m == a:
                func(i + 1, j)
                self.ans += 1
            elif m == b:
                func(i - 1, j)
                self.ans += 1
            elif m == c:
                func(i, j + 1)
                self.ans += 1
            elif m == d:
                func(i, j - 1)
                self.ans += 1
            else:
                return
        
        self.ans = 0
        func(0,0)
        
        for i in range(len(forest)):
            if max(forest[i]) > 1:
                return -1
        
        return self.ans

이건 상하좌우 중에 최솟값으로 가는 거라 다른 경로도 고려해야하는 듯

minimum step 주의하기

시간이 없어서 수정은 못했다...

Solution 1:

https://leetcode.com/problems/cut-off-trees-for-golf-event/discuss/107396/Python-solution-based-on-wufangjie's-(Hadlock's-algorithm)
참고