[Mock] Amazon 13

541. Reverse String II

Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.

If there are fewer than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.

My Answer 1: Accepted (Runtime: 56 ms - 8.48% / Memory Usage: 14.5 MB - 17.63%)

class Solution:
    def reverseStr(self, s: str, k: int) -> str:
        ans = ''
        
        i = 0
        cnt = 0
        rev = 1
        tmp = ''
        while i < len(s):
            if cnt < k:
                if rev:
                    tmp = s[i] + tmp[:]
                else:
                    tmp += s[i]
                cnt += 1
            else:
                cnt = 0
                rev = not rev
                ans += tmp
                tmp = ''
                i -= 1
            i += 1
        
        if tmp:
            ans += tmp
        
        return ans

cnt 로 k 개 만큼 세주면서

rev == 1 이면 reverse 로 tmp 에 저장하고
rev == 0 이면 원래대로 tmp 에 저장해서
ans 에 추가

cnt == k 면 rev 는 0->1 or 1->0 로, cnt, tmp 는 모두 초기화

뭔가 모르겠는 그지같음을 느꼈읍니다...

---

1192. Critical Connections in a Network

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [ai, bi] represents a connection between servers ai and bi. Any server can reach other servers directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some servers unable to reach some other server.

Return all critical connections in the network in any order.

My Answer 1: X

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        dic = collections.defaultdict(list)
        
        for i in range(len(connections)):
            dic[connections[i][0]].append(connections[i][1])
            dic[connections[i][1]].append(connections[i][0])
        
        def func(c, nums):
            if len(nums) == n:
                return 1
            
            if c is None:
                return 0
            
            ans = 0
            for i in range(len(c)):
                if c[i] not in nums:
                    ans = func(dic[c[i]], nums+c[i])
            
            return ans
        
        self.ans = []
        for i in range(n):
            for j in range(len(dic[i])):
                if func(dic[i][:j]+dic[i][j+1:], [i]) == 0:
                    self.ans.append([i, dic[i][j]])
        
        return self.ans

그래프니까 dic 에 연결된 숫자들 모두 저장

0 ~ n-1 의 숫자로 정해져 있으니까 n 만큼 반복문 돌려서
해당 숫자와 연결된 리스트에서 하나씩 제거한 값을 재귀에 돌림

재귀함수에서는
nums 에 방문한 숫자들을 넣어주면서 파도타기로 어디까지 타고 가나 확인해줌

모든 숫자를 방문하면 return 1
모두 방문하지 못하고 끝나면 return 0

방문했던 숫자는 보지 않도록 처리

라는 아이디어만...^^

1시간 짜리인데 미듐도 아니고 하드가 뭐죠..?

Solution 1: Accepted (Runtime: 2164 ms - 92.06% / Memory Usage: 65 MB - 97.04%)

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = [[] for _ in range(n)]
		
        currentRank = 0
		
        lowestRank = [i for i in range(n)]
		
        visited = [False for _ in range(n)]
        
        for connection in connections:
            graph[connection[0]].append(connection[1])
            graph[connection[1]].append(connection[0])
        
        res = []
        prevVertex = -1
        
        currentVertex = 0
        self._dfs(res, graph, lowestRank, visited, currentRank, prevVertex, currentVertex)
        return res
    
    def _dfs(self, res, graph, lowestRank, visited, currentRank, prevVertex, currentVertex):
        visited[currentVertex] = True 
        lowestRank[currentVertex] = currentRank

        for nextVertex in graph[currentVertex]:
            if nextVertex == prevVertex:
                continue
                
            if not visited[nextVertex]:
                self._dfs(res, graph, lowestRank, visited, currentRank + 1, currentVertex, nextVertex)
                
            lowestRank[currentVertex] = min(lowestRank[currentVertex], lowestRank[nextVertex]) 
            if lowestRank[nextVertex] >= currentRank + 1:
                res.append([currentVertex, nextVertex])

그래프 만들고 rank 를 잡아주기 => currentRank 와 lowestRank

dfs 돌려서 visited True 로 체크해주고

연결된 숫자들 중에 방문하지 않은 곳으로 currentRank + 1 해서 재귀 돌리기

아니 근데 랭크의 의미를 모르겠음...

낮은 랭크일수록 더 귀하다는...?