[Mock] Random 1

오랜만에 알고리즘~

---

35. Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

My Answer 1: Accpeted (Runtime: 48 ms - 69.50% / Memory Usage: 14.7 MB - 99.09%)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        if target in nums:
            return nums.index(target)
        
        nums.append(target)
        nums.sort()
        
        return nums.index(target)

값이 nums 에 존재하면 해당 index return
없으면 넣고 정렬한 후의 index return

양심이 조곰 찔리네요...^^

Solution 1: Accpeted (Runtime: 48 ms - 69.50% / Memory Usage: 15 MB - 79.53%)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l , r = 0, len(nums)-1
        
        while l <= r:
            mid = (l+r) // 2
            
            if nums[mid] == target:
                return mid
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid - 1
                
        return l

맨 첨에 생각했던 Binary Search

l, r 써서 target 이 들어갈만한 위치 찾기

Solution 2: Accepted (Runtime: 48 ms - 69.50% / Memory Usage: 14.9 MB - 79.53%)

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        return len([x for x in nums if x<target])

1 줄로도 끝내기 가능

그냥 target 보다 작은 애들을 세주면 된다

---

547. Number of Provinces

There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.

A province is a group of directly or indirectly connected cities and no other cities outside of the group.

You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.

Return the total number of provinces.

My Answer 1: Wrong Answer (86 / 113 test cases passed.)

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        cnt = len(isConnected)
        
        for i in range(len(isConnected)):
            for j in range(i, len(isConnected[i])):
                if i != j and isConnected[i][j] == 1:
                    if isConnected[j][i] == 1:
                        cnt -= 1
        
        if cnt < 1:
            return 1
        
        return cnt

문제 이해를 잘못해서...
전체 길이에서 누군가와 connect 된 애들을 하나씩 빼줌

전에 아일랜드인가 재귀로 타고타고 들어가서 하나의 연결고리 찾는 걸 생각하긴 했는데...
3중 for 문이로도 안풀리더라구요^^

오랜만에 문제를 풀어서 그런가 머리가 굳어버린듯...☆

Solution 1: Accepted (Runtime: 184 ms - 79.63% / Memory Usage: 14.5 MB - 96.49%)

class Solution:
    def findCircleNum(self, isConnected: List[List[int]]) -> int:
        visited = [0]*len(isConnected);
        count = 0;
        
        def dfs(isConnected, visited, i):
            for j in range(len(isConnected)):
                if isConnected[i][j] == 1 and visited[j] == 0:
                    visited[j] = 1
                    dfs(isConnected, visited, j)
        
        for i in range(len(isConnected)):
            if (visited[i] == 0):
                dfs(isConnected, visited, i)
                count += 1
        
        return count

DFS 재귀!!!!!!

그냥 이렇게 간단히 나올 것을... 왤케 머리가 안돌아갔는지...;;

i 랑 연결된(isConnected[i][j] == 1) 애들(j)은 visited[j] = 1

dfs 를 한번 돌때마다 연결된 애들은 다 visited = 1 이 되므로 0 일때만 count += 1