코딩 테스트 준비

10/5/ 2022 시작

1일차

704 Binary search

근데 바이너리 서치를 하나도 활용 안함

 

for 루프를 돌리면 최대 O(n) 인데 "sorted list" 라는 특성을 활용하면 O(log n) 까지 줄일 수 있음. 기본 아이디어는 마치 술게임 업다운처럼 ㅎㅎ 반씩 쪼개서 탐색하자는 것. 

import math
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        lo = 0
        hi = len(nums) - 1
        if (target < nums[0]) or (target > nums[-1]):
            return -1
        else:
            while lo <= hi:
                mid = int(lo + math.floor((hi-lo)/2))
                if target < nums[mid]:
                    hi = mid-1
                elif target > nums[mid]:
                    lo = mid+1
                else: #target == nums[mid]
                    return mid
            return -1

생각보다 구간 정하고 equality 결정하는게 까다로웠다. 특히 array에 element 가 두개만 남은 상황을 다루는게 중요하다. 

 

 think of the situation when there are only 2 elements left. Did the boundary shrink correctly?

 

278 First Bad Version

한번 잘 이해하고나니 쉬웠음

class Solution(object):
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        lo = 1
        hi = n
        
        while lo <= hi:
            mid = int(lo + math.floor((hi-lo)/2))
            if isBadVersion(mid) == True:
                bad = mid
                hi = mid-1
            elif isBadVersion(mid) == False:
                lo = mid+1
        return bad

 

35. Search Insert Position

class Solution(object):
    def searchInsert(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        lo = 0
        hi = len(nums)-1
        
        while lo <= hi:
            mid = int(lo + math.floor((hi-lo)/2))
            if target < nums[mid]:
                hi = mid-1
            elif target > nums[mid]:
                lo = mid+1
            else: # if target == nums[mid]
                return mid
        return lo

 

 

근데 다른 문제 결과에 비해 성능이 왜이렇게 안좋은지 모르겠음. 나중에 다시 확인해볼것!

 

10/6

2일차

sometimes what "wins" at the notoriously inaccurate Leetcode time/ space percentiles isn't always the best in practice, or even in an interview.

성능 분석표를 믿으면 안된다는 사실을 깨달음

 

내가 생각할 수 있는 솔루션은 built-in function 을 이용하는 것 뿐이라 아에 해설을 읽음. 대부분의 built in function 은 O(n log n) 인데 sorted list 를 주었다는건 그 특성을 이용해서 O(n) 솔루션을 찾아내라는 것. 

class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        return_array = [0]*len(nums)
        write_pointer = len(nums)-1
        left_pointer = 0
        right_pointer = len(nums)-1
        left_square = nums[left_pointer]**2
        right_square = nums[right_pointer]**2
        
        while write_pointer >= 0:
            if left_square > right_square:
                return_array[write_pointer] = left_square
                left_pointer += 1 
                left_square = nums[left_pointer]**2
            else:
                return_array[write_pointer] = right_square
                right_pointer -= 1
                right_square = nums[right_pointer]**2
            write_pointer -= 1
        return return_array

포인터 항목에 들어있길래 포인터로 풀었음.

189. Rotate Array

코드 자체는 간단하나 꽤나 유의해야할 포인트가 많았음. 처음에는 k 번 도는 for 루프를 구상했는데 그럴필요없이 k 로 인덱싱하면 되는 거였음. extra space 를 아끼려면 shallow copy 해야하는데 이때 nums 가 아니라 nums[:]를 사용해야함. (shallow copy 와 deep copy 의 차이점은 shallow copy 는 요소들의 메모리는 바뀌지 않으나 그 리스트의 메모리가 새로운 값으로 할당되는 것. deep copy 는 요소들의 메모리도 바뀜.)

class Solution(object):
    def rotate(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        k = k % len(nums)
        nums[:] = nums[len(nums)-k:] + nums[:len(nums)-k]

그리고 corner case 탐색. k 가 list 길이보다 작은 경우를 고려했어야함. 이를 고려하기 위해 k를 list 길이로 나눈 나머지를 사용했다. 

 

10/7

3일차

pointer 두개를 써서 풀어야 가장 간단. 이건 근데 풀이를 안봤으면 못풀었을것 같음.. non-zero element 를 계속해서 앞으로 가져오는 발상과 비슷한 발상을 나중 문제에서 해낼 수 있는지 체크할것.

283 Move Zeroes

class Solution(object):
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        i = 0 # i denotes final non-zero element at the end
        for j in range(len(nums)): # j is iterating pointer
            if nums[j] != 0:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1

167 Two Sum II

class Solution(object):
    def twoSum(self, numbers, target):
        """
        :type numbers: List[int]
        :type target: int
        :rtype: List[int]
        """
        lo = 0
        hi = len(numbers) - 1
        while numbers[lo] + numbers[hi] != target:
            if numbers[lo] + numbers[hi] < target:
                lo += 1
            else:
                hi -= 1
        return [lo+1, hi+1]

어떻게 풀까 이렇게 저렇게 고민했지만 결국 shrink array 를 구현하기 위한 pointer 를 쓰는게 포인트였다. 

 

10/8

4일차

일단 LinkedList 가 뭔지 몰라서 솔루션을 봐야 했음.ㅜㅜ  근데 너무 specific 한건 아닌지..? LinkedList 의 장점이 뭐고 왜 써야하는지부터 공부해보기. 

 

10/9, 10, 11

567일차

슬슬 어려워지면서 밀리기 시작해서 몰아서 해야했음 ..^^

 

344. Reverse String

class Solution(object):
    def reverseString(self, s):
        """
        :type s: List[str]
        :rtype: None Do not return anything, modify s in-place instead.
        """
        lo = 0
        hi = len(s)-1
        while lo < hi:
            temp = s[lo]
            s[lo] = s[hi]
            s[hi] = temp
            lo += 1
            hi -= 1

 

string 뒤집는건 일단 이렇게 풀었다. array 를 in-place 하기 위해 temp 를 사용함

 

557. Reverse Words in a String III

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        splited = s.split(" ")
        reversed_words = ""
        for i in range(len(splited)):
            word = str(splited[i])
            hi = len(word)-1
            
            reversed_word = ""
            while hi >= 0:
                reversed_word += word[hi]
                hi -= 1
            
            reversed_words += reversed_word
            
            if i != len(splited)-1:
                reversed_words += " "
                
        return reversed_words

이게 나의 처음 솔루션 약간 더 난이도가 있었다.

다른 풀이들을 찾아보니 더 간단한 방법들이 있었다. 다음은 one-liner 솔루션

list[<start>:<stop>:<step>]

만일 list[::-1] 이렇게 쓰면 맨 뒤에서부터 하나씩 앞으로 가면서 읽어옴. string, list, tuple 모두에 적용 가능 

class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        splited_list = s.split(" ")    
        return " ".join([i[::-1] for i in splited_list])

 

Hash table 은 key 를 바탕으로 value 를 가져올 수 있는 자료 구조형으로 파이썬에서는 dictionary 형태로 구현되어있어서 별도로 구현할 필요는 없다. 

 

3. Longest Substring Without Repeating Characters

처음으로 큰 난관에 봉착했다고 느낀 문제. 어렵게 보이지는 않았는데 솔루션이 계속 돌고 돌아 풀리지가 않았다. 원래 평소 코딩할때도 느끼던 현상이라 이번 기회로 한스텝 한스텝 생각하는법을 배워보기로함.

 

솔루션: substring 을 정의해 순차적으로 한 단어씩 넣는다. 만약 새로 넣으려는 character 가 이전 단어와 겹친다면 지금까지의 substring 이 maximum length substring 의 candidate 일것. 지금까지 찾은 maximum 값보다 크다면 업데이트. 그리고 새로 넣으려는 character를 넣고 기존에 그와 겹쳤던 단어를 찾아 뺼수도 있음.

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        max_length = 0
        
        substring = []
        for i in s:
            if i not in substring:
                substring.append(i)
                if len(substring) > max_length:
                    max_length = len(substring)
                
            else: # find i in the substring and remove it
                substring.append(i)
                for j in range(len(substring)):
                    if substring[j] == i:
                        substring = substring[j+1:]
                        break

        return max_length

여러번 시도 끝에 해냈음. 하지만 지쳐서 더 나은 솔루션을 찾아보려는 노력은 하지못했따 ㅎㅎ

11/2

리사브와하는 코딩스터디 3일차 - 평일에 한시간반에서 두시간정도 하는중

그냥 아무 문제나 골라서 브레인스토밍하고 풀기 시작함. 꽤나 장족의 발전이지만 아직 멀었다. bipartite matching 문제는 한시간 반이나 걸렸다 ..  

DFS 는 stack, BFS는 queue 기억하기!

785. Is Graph Bipartite?

class Solution(object):
    def isBipartite(self, graph):
        """
        :type graph: List[List[int]]
        :rtype: bool
        """
        n = len(graph)
        visited = [-1 for _ in range(n)] # -1: unvisited, A, B
         
        for u in range(n):
            if visited[u] != -1:
                continue
            else:
                stack = [u]
                visited[u] = 'A'
            while stack:
                i = stack.pop(-1)
                for v in graph[i]: #get neighbors
                    if visited[v] != -1: # if the neighbors already visited
                        if visited[v] == visited[i]: # if the neighbor is in the same set
                            return False
                        continue
                    else:
                        if visited[i] == 'A':
                            visited[v] = 'B'
                        else: #visited[i] == 'B':
                            visited[v] = 'A'

                        stack.append(v)

        return True