[LeetCode - Top Interview Questions(Easy, Python3)]Array

리트코드 Top Interview Questions 챕터 1 Array 전체 Python3 풀이

 

 

• Remove Duplicates from Sorted Array 

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i = 0
        while i<len(nums)-1:
            if nums[i] == nums[i+1]:
                nums.remove(nums[i])
            else:
                i+=1
        return len(nums)
                

in-place 로 추가 메모리를 할당하지 않고 풀어야하는 문제라서 'nums[:] = sorted(set(nums))'로 풀지 않았다. 느리다. 

 

 

• Best Time to Buy and Sell Stock II 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        for i in range(len(prices)-1):
            if prices[i]<prices[i+1]:
                profit += prices[i+1]-prices[i]
        return profit

비슷한 문제로는 'Best Time to Buy and Sell Stock I'이 있는다. 그 문제에서는 단 한번 주식을 사고 팔 수 있어서, 한번의 매수와 매도로 얻을 수 있는 최대 이익이 어느 정도인지 계산해야한다.

하지만 이 문제에서는 매수, 매도 횟수에 제한이 없고 미래 가격도 알 수 있고 수수료마저도 없기때문에, 오늘보다 내일 더 높은 가격이면 사서 바로 팔면 된다.

 

•  Rotate Array

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        while k!=0:
            nums.insert(0, nums.pop())
            k -= 1
        

k번만큼 nums 배열 맨 뒤의 원소를 맨 앞으로 이동시키는 문제다.   

 

•  Contains Duplicate

1번 풀이

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        nums.sort()
        i=0
        while i<len(nums)-1:
            if nums[i] == nums[i+1]:
                return True
            i+=1
        return False
                
        
                

2번 풀이

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:
        return not len(set(nums)) == len(nums)
        # 또는
        # return len(set(nums)) != len(nums)
        
                

중복 원소를 포함했는지의 여부를 구하는 문제다. 

1번 풀이는 배열을 한번 정렬한 다음에, 정렬된 배열의 i번째 원소와 i+1번째 원소가 같으면 중복된 원소가 있으므로 True를 리턴하고, 없으면 False를 리턴한다.

2번 풀이는 nums의 set(중복x)의 길이와 nums의 길이를 비교한다. 

 

 

•  Single Number

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return collections.Counter(nums).most_common()[-1][0]

배열 중 단 하나의 원소만 1번 나타나고, 그 외의 원소는 모두 2번씩 나타나는 문제다.

collections의 Counter(iterable)는 list, dict, str 등 iterable에서 각 원소가 몇 번씩 사용되었는지 세준다. 그리고 most_common()은 많이 사용된 순서대로 (key, value) 형태로 리턴해준다.

most_common() 예시

•  Intersection of Two Arrays II

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        answer = []
        for num1 in nums1:
            if num1 in nums2:
                nums2.remove(num1)
                answer.append(num1)
        return answer

 

두 배열의 교집합을 구하는 문제다. 만약 배열에 중복된 원소가 없다면 array를 set으로 변경해서 intersection 메서드를 사용하면 되지만, 이 문제에는 중복된 원소가 있다.

 

 

•  Plus One

class Solution:
    def plusOne(self, digits: List[int]) -> List[int]:
        # answer = ''
        # for digit in digits:
        #     answer += str(digit)
        # return list(str(int(answer)+1))
        
        return list(str(int(''.join(map(str, digits)))+1))

join은 list를 str로 만들 때 사용하는데, 원소들이 str이어야 사용할 수 있다.

그래서 map을 사용해서 digits의 원소들을 str로 만들어 준 뒤, join을 사용해서 하나의 문자열로 만들었다.

그 후 int 형태로 바꿔준 후 1을 더하고, list로 바꿔서 리턴했다.

 

문제 풀 때 사용한 메서드 예시

 

•  Move Zeroes

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        for num in nums:
            if num == 0:
                nums.pop(nums.index(num))
                nums.append(num)

리스트의 원소 중 0이 있으면 리스트의 맨 뒤로 보내주는 문제다.

nums의 원소 num이 0이면 nums에서 num의 인덱스를 찾아서 pop하고, nums의 맨 뒤에 num을 추가했다.

 

•  Two Sum

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for index, num in enumerate(nums):
            if target-num in nums and index != nums.index(target-num):
                return [index, nums.index(target-num)]

nums 에서 더하면 target이 되는 원소 i, j를 찾는 문제다.

 

a+b = c 중 a, c를 알고 있는 것과 마찬가지인 상황이므로 이중 for문을 돌릴 필요없다. b를 구하기위해서는 c-a를 해주면 되는 것 처럼 풀면 된다.

 

target - num in nums 는 nums 리스트 안에 target - num이 있는지(더하면 target이 되는 원소 두개가 존재하는지)를 확인하기 위해,

index != nums.index(target-num) 은 리스트의 모든 원소가 distinct하다는 조건이 없으므로 붙인 조건이다. 

 

•  Valid Sudoku

class Solution:
    def check(self, board):
        for row in board:
            if not all([row.count(elem)==1 for elem in row if elem != '.']):
                return False
        return True
    
    def rotate(self, board):
        return list(map(list, zip(*board)))
    
    def mini_board(self, board):
        result = [[], [], [], [], [], [], [], [], []]
        for idx in range(len(board)):
            if idx in range(0,3):
                result[0].extend(board[idx][0:3])
                result[1].extend(board[idx][3:6])
                result[2].extend(board[idx][6:9])
            elif idx in range(3,6):
                result[3].extend(board[idx][0:3])
                result[4].extend(board[idx][3:6])
                result[5].extend(board[idx][6:9])
            else:
                result[6].extend(board[idx][0:3])
                result[7].extend(board[idx][3:6])
                result[8].extend(board[idx][6:9])
        return result
    
    def isValidSudoku(self, board: List[List[str]]) -> bool:
        if all([self.check(board), self.check(self.rotate(board)), self.check(self.mini_board(board))]):
            return True
        return False

비효율의 끝판왕처럼 푼 것 같다(근데 의외로 86.94%). 정석적으로 스도쿠를 풀 때 처럼 하나하나 확인해줬다.

스도쿠를 풀때 확인하는 가로줄, 세로줄, sub-box 각각에 1~9까지의 숫자가 반복되는지를 확인해줬다. 

 

•  Rotate Image

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        rotated = [list(reversed(row)) for row in list(map(list, zip(*matrix)))]
        matrix[:] = rotated

in-place 안지키고 푼 풀이

class Solution:
    def rotate(self,  matrix: List[List[int]]):
        """
        Do not return anything, modify matrix in-place instead.
        """
        matrix.reverse()
        for i in range(len(matrix)):
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

in-place 지키고 푼 풀이