CareTim

You are given an n x n integer matrix board where the cells are labeled from 1 to n2 in a Boustrophedon style starting from the bottom left of the board (i.e. board[n - 1][0]) and alternating direction each row.

#풀이

그래프 탐색을 통해서 최단거리를 구하는 문제이다. 다익스트라랑 bfs로 각각 한번씩 풀어봤다.

1. visit을 통해서 방문한 곳을 체크한다, (bfs 방문확인, dijkstra 이동횟수 체크)

2. 주사위로 1,2,3,4,5,6을 굴려서 이동한다 (bfs 방문했다면 pass , dijkstra 방문했어도, 이동횟수가 기록보다 적다면 이동)

3. 현재 위치가 마지막 위치 (n*n) 위치인지 확인한다.  -> 마지막 위치라면 return 

dijkstra는 heapq을 사용해 우선순위(이동횟수)를 두고 탐색하게 했다. 하지만 이 문제에서는 각각의 이동거리가 비슷하고 ,각각 선형으로 이동하는거리가 대부분 동일하게 1로 움직이기에 생각보다 탐색속도가 빠르지 않았다.

반대로 bfs는 넓이탐색을 통해서  이미 방문했던 곳이라면, 본인보다 이동횟수가 적은게 확실하기에 모든 이동경로를 1번 이상 방문하지 않기에 다익스트라보다 비교적 빠르게 탐색이 가능했다. 

Dijkstra

import heapq
import sys
INF = sys.maxsize
class Solution(object):
    def snakesAndLadders(self, board):
        n= len(board)
        line = [-1]
        flag = 1
        for y in range(n-1,-1,-1):
            if flag%2 ==1:
                for x in range(n):
                    line.append(board[y][x])
            else:
                for x in range(n-1,-1,-1):
                    line.append(board[y][x])
            flag+=1
        visit = [INF] *((n**2)+1)
        visit[1]=0
        q= []
        heapq.heappush(q,(0,1))
        while q:
            move,cur = heapq.heappop(q)
            for i in (1,2,3,4,5,6):
                next = cur+i
                if line[next]!= -1:
                    next = line[next]
                if next <(n**2) and visit[next]>move+1:
                    visit[next]=move+1
                    heapq.heappush(q,(move+1,next))
                    # print(move,next)
                if next == (n**2):
                    return move+1
        return -1

BFS

from collections import deque

class Solution(object):
    def snakesAndLadders(board):
        n= len(board)
        line = [-1]
        flag = 1
        for y in range(n-1,-1,-1):
            if flag%2 ==1:
                for x in range(n):
                    line.append(board[y][x])
            else:
                for x in range(n-1,-1,-1):
                    line.append(board[y][x])
            flag+=1
        print(line)
        visit =[0]*((n**2)+1)
        visit[1]=1
        q= deque()
        q.append((0,1))
        while q:
            move,cur = q.popleft()
            for i in (1,2,3,4,5,6):
                next = cur+i
                if line[next]!=-1:
                    next = line[next]
                if visit[next] ==0:
                    visit[next] = move+1
                    q.append((move+1,next))
                    print(next)
                if n**2 == next:
                    return move+1

        return -1


    
board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]

print(Solution.snakesAndLadders(board))

bfs는 방문 리스트를 통해 방문처리하게 되면 방문하지않는다,  반면 다익스트라는 방문을하고나서, 다음에 들어오는 방문인자가 횟수가 적다면 다시 방문처리를 한 후 이동을 하게된다,  dp의 배낭알고리즘과 다익스트라를 합쳐서 사용하면 속도 향상을 할 수 있지 않을까라는 생각을 해봤다.  

Given a reference of a node in a connected undirected graph.

Return a deep copy (clone) of the graph.

Each node in the graph contains a value (int) and a list (List[Node]) of its neighbors.

풀이

주어지는 그래프를 깊은 복사* (참조가 아니라 메모리에 새로 저장)하여  복사한 그래프를 리턴하면 되는 문제이다.

사실 문제를보고 간단하게  deepcopy 함수를 사용하면 바로 풀릴거라 생각했지만 ㅋㅋ 그래프를 탐색해서 풀라는 문제이니  deuqe을  사용해서 딕셔너리로 방문한 리스트 기록하며  bfs탐색을 했다.

1. 주어지는 첫 노드를 deque에 넣는다..

2.deque가 완전히 비워질 때 까지 while을 순회하며 bfs 탐색을한다.

3. cur을 통해 큐에 들어온 원소들을 뽑아서 인접한 노드를 탐색한다.

4.만약 딕셔너리에 현재 돌고있는 이웃 노드를  방문을 안했다면 딕셔너리 노드에 현재 인덱스 dict[cur]에 노드 생성,

-> neighbors에 인접한 노드의 딕셔너리 인덱스를 넣어준다, (딕셔너리를 통해 각 노드인덱스를 모두 방문할 때 까지 갱신)

5.최초 방문이라면 큐에 다시 넣어준다.

5. 방문을 했다면 딕셔너리의 해당 인접노드의 딕셔너리 인덱스의 값을 현재 노드의 딕셔너리의 이웃으로 재갱신 해준다.

from collections import deque
class Solution(object):
    def cloneGraph(self, node):
        if node == None:
            return 
        q = deque()
        visit = dict()
        visit[node.val]= Node(val=node.val)
        q.append(node)
        while q:
            cur=q.popleft()
            for i in cur.neighbors:
                if i.val not in visit:
                    visit[i.val]=Node(i.val)
                    q.append(i)
                visit[cur.val].neighbors.append(visit[i.val])

        return visit[node.val]

처음에 문제를 제대로 이해 못하고, 기존 node클래스에 neighbors속성이 리스트로 구성되어 있는줄 알고 리스트로 계속 넣으려고 하다가 실패했다. 

            for i in cur.neighbors:
                if i.val not in visit:
                    visit[i.val]=Node(i.neighbors)
                visit[node.val].neighbors.append(visit[i.val].neighbors)
        return visit[node.val]

백준으로 문제를 풀 때는 각 리스트를 변수에 저장해서 사용하기에 쉽게 느껴졌는데, 클래스를 통해 문제를 풀려고하니 좀 헤멨던 것 같다.  

다른사람의 코드 

class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node: return
        d = {node: Node(node.val)}
        stack = [node]
        while stack:
            curNode = stack.pop()
            for nei in curNode.neighbors:
                if nei not in d:
                    d[nei] = Node(nei.val)
                    stack.append(nei)
                d[nei].neighbors.append(d[curNode])
        return d[node]

dfs로 깊이탐색을 진행하며, 방법은 동일한다, 순서가 상관없기에 bfs든 dfs던 그래프를 모두 탐색하여 값을 찾아오면 된다.  

Given an m x n board of characters and a list of strings words, return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

풀이

알파벳으로  이루어진 2차원 리스트가 주어지고  단어의 배열이 주어진다,

배열안에 존재하는 단어를 리스트에 담아서 제출하면 된다.

방법

트라이트리(trietree) 자료구조를 활용해서 단어를 넣은 트라이트리를 만들고 매트리스마다 y,x축으로 나누어 dfs로 2차원리스트를 탐색해 어떤 단어들이 존재하는지 찾는다. 

class Node:
    def __init__(self):
        self.children={}
        self.endof =0

class Trie(object):
    def __init__(self):
        self.root = Node()
    def insert(self, word): # 노드 삽입, 딕셔너리로 존재하지않는다면 생성, 존재한다면 추가 
        node = self.root
        for i in word:
            if i not in node.children:
                node.children[i] = Node()
            node= node.children[i] 
        node.endof =1   # 완성문자열



class Solution(object):
    def findWords(self, board, words):
        self.result = []
        trie = Trie() # trieTree 생성
        node = trie.root
        for i in words: # 트라이트리에 단어 삽입
            trie.insert(i)
        for y in range(len(board)):
            for x in range(len(board[0])):
                self.search(node,board,y,x,"")
    def search(self,node,board,y,x,temp):
        dy,dx = [0,0,1,-1],[1,-1,0,0]
        if node.endof: # 현재 완성된 단어라면 tmep result에 추가 
            self.result.append(temp)
            node.endof = 0 #방문체크 
            if not node: 
                return
        if 0>y>=len(board) or 0>x>=len(board[0]): #범위체크
            return
        char = board[y][x] # 현재 위치의 문자열 확인
        if char not in node.children: # 현재 노드의 해시맵에 없다면 리턴
            return
        node = node.children[char] #node 현재 char의 인덱스로 변경
        for i in range(4): # ny,nx재지정 상하좌우
            ny,nx = y+dy[i],x+dx[i]
            self.search(node,board,ny,nx,temp+char) # 재귀적으로 탐색

오류나서 생긴 문제

1.board의 방문리스트를 사용하지 않아서 최초에 오류가 났었는데 ( 왔던 경로 재방문) , 이걸 위해 board를 '*'문자열로 바꿨다가 findword의 2차원탐색에서 다른 위치에서 시작할 때 오류 발생,  변경된 문자열로 새로 찾을 수 없음

   -> search의 for문으로 ny,nx 변경시에만 값 변경

2.시간초과

모든 경로를 2차원리스트에서 dfs로 모두 찾으려하니 시간이 초과됨 

You are given two integer arrays nums1 and nums2 sorted in non-decreasing order and an integer k.

Define a pair (u, v) which consists of one element from the first array and one element from the second array.

Return the k pairs (u1, v1), (u2, v2), ..., (uk, vk) with the smallest sums.

풀이

2개의 배열이 주어지고 각각 오름차순 되어있는 배열에서 인자를 뽑아 2개의 조합만들어 질 때  가장 작은 합을 갖는 k개의 쌍을 찾는 문제이다.

생각한 방법

1. 모든 2개의 조합을 만들어  heap을 사용해 (nums1+nums2,nums1,nums2) 형식으로 삽입하여, 합이 가장 작은 k개를 뽑는다.

2. 문제에서 원하는 쌍은 k개이니 두 개의 배열을 오름차순 정렬되어있는걸 활용하여  범위를 k까지 지정하여 조합을 만든다.

import heapq
class Solution(object):
    def kSmallestPairs(self, nums1, nums2, k):
        if not nums1 or not nums2:
            return
        heap = []
        for i in range(min(k, len(nums1))):
            for j in range(min(k, len(nums2))):
                heapq.heappush(heap,(nums1[i]+ nums2[j],[nums1[i],nums2[j]]))
        result =[]
        for __ in range(min(k, len(heap))):
            result.append(heapq.heappop(heap))
        
        return [i[1] for i in result]

실패 ) 메모리초과 

메모리값을 줄 일 수 있는 방법이 생각이 안나서 같은 조의 팀원의 코드를 가져와봤다.

result가 추가되는것을 제한한다. heap에 k개 까지만 저장한 뒤 k개가 넘는다면 최대힙을 통해서 가장 큰 값을 뺀다.

다른 사람의 코드 

import heapq
class Solution(object):
    def kSmallestPairs(self, nums1, nums2, k):
        if not nums1 or not nums2:
            return
        heap = []
        for i in range(min(k, len(nums1))):
            for j in range(min(k, len(nums2))):
                if len(heap)<k:
                    heapq.heappush(heap,(-(nums1[i]+ nums2[j]),[nums1[i],nums2[j]]))
                else:
                    if heap[0][0] < -(nums1[i] + nums2[j]):
                        heapq.heappop(heap)
                        heapq.heappush(heap,(-(nums1[i]+ nums2[j]),[nums1[i],nums2[j]]))
                    else:
                        break
        return [i[1] for i in heap]

메모리 공간을 위해서 heap에는 k개의 원소만 유지하며, k개의 이상의 인자가 더해진다면 기존에 있던 값 (최소 힙트리의 root값)과 비교하여 작은지 확인 한 후 기존 값보다 작다면 pop을 진행하고 다시 새로운 인자를 넣고,

아닐경우 멈춘다.  

다른사람의 코드

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        flag = (n := len(nums1)) > (m := len(nums2)) # 원소 개수 체크
        if flag:
            n, m, nums1, nums2 = m, n, nums2, nums1	# 원소 크기에 따라 heappush에서 앞에 들어갈지 뒤에 들어가리 정해준다,
            
        heap = []
        for i in range(min(k, n)):
            heappush(heap, (nums1[i] + nums2[0], i, 0)) # 
        
        ans = []
        
        while heap and len(ans) < k:
            s, i, j = heappop(heap)
            ans.append([nums1[i], nums2[j]] if not flag else [nums2[j], nums1[i]]) # 둘중 개수가 큰걸 앞으로 놓는다,
            
            if j + 1 < min(k, m):
                heappush(heap, (nums1[i] + nums2[j + 1], i, j + 1))
                #개수가 적은쪽의 인덱스를 늘려가며 ans에 넣을 인자를 heap에 먼저 넣어줌 
            
        return ans

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

Can you solve it without sorting?

풀이

배열을 정렬하지 않고 k번째 큰 수를 출력하는 문제이다.

최대힙을 사용해서 문제를 풀 생각을 했고,  heapq를 사용해서 각 숫자들을 음수로 바꿔준 뒤 

pop을 k+1번 시행하여 답을 찾았다.

import heapq
def changeMinus(n):
        return -n
class Solution(object):
    def findKthLargest(self, nums, k):
        result = 0
        q= []
        for i in nums:
            heapq.heappush(q,-i)

        for __  in range(k):
            result = heapq.heappop(q)
        return -result
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

• WordDictionary() Initializes the object.
• void addWord(word) Adds word to the data structure, it can be matched later.
• bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

풀이  

단어를 추가하고 이전에 추가된 문자열과 일치하는지 확인할 수 있는 데이터 구조를 설계하는 문제

문자열에서 '.'  마침표는 모든 문자와 일치할 수 있다.

TrieTree를 통해 문자열을 넣어주면 되는데 문자열에서 마침표 일 때 탐색을 어떻게해줘야할지 고민을 했다.

1.while문으로 모든 문자열 하위를 모두 탐색하기,

2.DFS로 다음 문자열이 동일한지 확인해서 탐색하기

DRF로 문자열 하위를 확인해서 재귀로 찾는법을 사용하기로했다.

class Node: # 해시맵으로 문자열이 들어갈 노드 작성
    def __init__(self):
        self.children={}
        self.endof =False	#문자열의 끝 확인 플래그 


class WordDictionary(object):

    def __init__(self):
        self.root = Node()	#root 최초시작 노드 자동생성,

        

    def addWord(self, word):
        node = self.root	# 첫 노드는 root로 시작,
        for i in word:
            if i not in node.children:	#node의 자식중 문자열 i가 없다면, 해당인덱스 노드생성
                node.children[i] = Node() 
            node= node.children[i]	#존재한다면 node는 해시맵[i]
        node.endof =1   # 완성문자열	# for문 종료 후 (문자 삽입 완료) 해당 노드 endof로 완성플래그 
        
    def dictFind(self,node,word):
        if not word: # 마지막 도달 종료 조건 node가 존재하지 않을때 종료된 곳이 endof가 True인지 확인, 
            if node.endof:
                self.result = True  #endof가 True라면 result= True로 변경 
            return 
        if  word[0] == '.': # 마침표가 들어왔을때, 현재 노드의 모든 해시맵 탐색,
            for i in node.children.values():	# for문을 통해서 dictFind함수재귀로 탐색
                self.dictFind(i,word[1:])
        else:
            node = node.children.get(word[0])	#문자열의 첫번째 인덱스가, 현재 노드의 해시맵에 존재하는지 탐색
            if not node:	# 존재 하지 않는다면 종료 
                return
            self.dictFind(node,word[1:])	 #슬라이싱을 통해 2번쨰 인덱스부터 끝 인덱스 word로 재귀탐색



    def search(self, word):
        node = self.root 	# 첫시작 노드 설정
        self.result = False	#result 디폴트 설정 False
        self.dictFind(node,word) # dictFind를 통해 탐색시작 (재귀탐색)
        return self.result	#탐색 종료후 result 리턴 
        

        """
        :type word: str
        :rtype: bool
        """
    


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)

마침표가  나왔을 때 for문을 통해서 현재 노드의 모든 하위 문자열을 for문으로 순회하며  dictFind 로 깊이 탐색을 시행한다.

외에는 재귀를 통해 하위 문자열로 연결,

다른사람의코드

class TrieNode:
    def __init__(self):
        self.is_word = False
        self.children = {}

class WordDictionary:

    def __init__(self):
        self.root = TrieNode()

    def addWord(self, word: str) -> None:
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
        node.is_word = True

    def search(self, word: str) -> bool:
        nodes = [self.root]
        for ch in word:
            next_nodes = []
            for node in nodes:
                if ch in node.children:
                    next_nodes.append(node.children[ch])
                if ch == '.':
                    next_nodes.extend(node.children.values())
            nodes = next_nodes
        
        for node in nodes:
            if node.is_word:
                return True
        
        return False

리스트를 사용해 탐색을 진행한다,  search의 함수에서 nodes에 담긴 node들을 모두 탐색하며 bfs로 각 노드들을 탐색하여 마지막에 도달하지는지 확인한다 . extend함수를 사용하여 '.' 일때 현재 인덱스의 모든 노드들을 next_nodes에 담아서 반복적으로 탐색을 수행하고, 모든 탐색이 끝났을때 맨 마지막 노드에서 완성된 문자열인지 확인한다. 

A trie (pronounced as "try") or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

풀이

TrieTree를 구현하는 직접 구현해서 만드는 문제이다.

보통 for문과 재귀를 사용해서 검색하고 찾는방법을 만드는데 , 저번에 재귀를 많이 사용해봤으니 이번에는 for문을 통해 만들어봐야겠다.

트라이트리는 검색을 구현할 때 많이 사용하는데, 해시맵(딕셔너리)를 사용해서 만들면 비교적 빠르게 트리를 탐색하여 값을 반환 할 수 있다. 

1.노드에 다음 탐색경로를 알려 줄 수 있는 children를 딕셔너리로 지정, endof를 통해서 문자가 완성된 문자인지 확인, 

2.탐색시 각 문자열의 딕셔너리에 들어있는 문제의 인덱스를 확인한다  ex) dict[char] 

3. 존재한다면 현재 노드에서 딕셔너리 안의 노드로 이동, 존재하지 않는다면 딕셔너리에 node생성 후 이동

4. 문자 탐색이 끝났을 때 endof 가 True라면 존재하는 문자

class Node:
    def __init__(self):
        self.children={}
        self.endof =False

class Trie(object):
    def __init__(self):
        self.root = Node()
        

    def insert(self, word): # 노드 삽입, 딕셔너리로 존재하지않는다면 생성, 존재한다면 추가 
        node = self.root
        for i in word:
            if i not in node.children:
                node.children[i] = Node() # 딕셔너리에 존재하지않는다면, node 추가,
            node= node.children[i] 
        node.endof =1   # 마지막 문자에 완성을 알려줄 수 있도록 endof = Ture 설정 
            
    def search(self, word):
        cur = self.root
        for i in word: 
            if i not in cur.children:
                return False  # 트라이트리하위에 글자가 존재하지 않는다면 False 반환
            cur = cur.children[i 
        if cur.endof ==1: # 마지막 탐색에서 endof가 Ture인지 확인, 
            return True
         retrun False


    def startsWith(self, prefix): #접두사 확인, 
        cur = self.root 
        for i in prefix:
            if i not in cur.children: # 트라이트리하위에 글자가 존재하지 않는다면 False 반환
                return False
            cur = cur.children[i] # 존재한다면 자식의 노드로 이동
 


# Your Trie object will be instantiated and called as such:
# obj = Trie()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.startsWith(prefix)

다른사람의 코드

class TrieNode:
    def __init__(self):
        self.children = {}
        self.end = False
        
class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        def fun(index, root):
            if index == len(word):
                root.end = True
                return
            
            if word[index] not in root.children:
                root.children[word[index]] = TrieNode()
                
            fun(index+1, root.children[word[index]])
                
        fun(0, self.root)
        
    def search(self, word: str) -> bool:
        def fun(index, root):
            if index == len(word):
                if root.end:
                    return True
                else:
                    return False
            
            if word[index] in root.children:
                return fun(index+1, root.children[word[index]])
            
            return False
        
        return fun(0, self.root)
        

    def startsWith(self, prefix: str) -> bool:
        def fun(index, root):
            if index == len(prefix):
                return True
            
            if prefix[index] in root.children:
                return fun(index+1, root.children[prefix[index]])
            
            return False
        
        return fun(0, self.root)

기본적으로 딕셔너리를 생성해서 하위 문자열을 찾고, for문을 사용해서 찾는게 아니라 재귀를 통해서 하위노드로 찾아내려간다, 

풀이

이진트리가 주어지고, 각 깊이 레벨의 해당하는 값들의 평균값을 구하는 문제

각 트리를 재귀로 탐색하고, 각각의 값을 리스트에 레벨에 맞는 인덱스에 값을 모두 더 해준 뒤

레벨의 개수 별로 나눠주면 되는 문제이다.

코드

class Solution(object):
    def averageOfLevels(self, root):
        self.depth = 0	#깊이 체크 포인터
        self.result=[]	# 레벨별로 값이 담길 리스트
        self.count =[]	# 레벨별로 개수가 담길 리스트
        self.find(root,0) # 시작
        for i in range(len(self.result)):	# 구해진 값들을 result(레벨별 총합)/count(레벨별 개수)
            self.result[i]= float(self.result[i])/float(self.count[i])
         
    
        return self.result # 나눠진 값이 담긴 리스트 리턴 
            
    def find(self,node,depth):
        if node== None:	# node가 비었다면 return 
            return
        if len(self.result)==depth: # 깊이와 레벨이 같다면 각 리스트의 길이 추가
            self.result.append(node.val)
            self.count.append(1)
        else:
            self.result[depth]+=node.val # 다르다면 레벨에 맞게 result와 count에 값 추가
            self.count[depth]+=1
        self.find(node.left,depth+1) #재귀적으로 left,right 탐색 
        self.find(node.right,depth+1)

1. 레벨별 총합을 넣을 리스트 (result), 레벨별 개수를 넣을 리스트 count를 만든다.

2. find함수로 각 레벨별로 탐색을하며 깊이가 깊어질때마다 depth값을 +1 해준다.

3. depth값을 기반으로 최초 탐색시 len(self.result)와 depth가 같아지는 순간 리스트 공간 추가 

4. depth와 len길이가 다르다면 , 각 리스트 인덱스 (depth)를 통해서 값 더해주고, 개수 추가해주기,

5. 탐색이 끝난 후 각 인덱스별로 나눠준 뒤 리턴

def averageOfLevels(self, root):
    info = []
    def dfs(node, depth = 0):
        if node:
            if len(info) <= depth:
                info.append([0, 0])
            info[depth][0] += node.val
            info[depth][1] += 1
            dfs(node.left, depth + 1)
            dfs(node.right, depth + 1)
    dfs(root)

    return [s/float(c) for s, c in info]

리스트를 하나를 사용하여 각 인덱스에 값과 개수를 추가해서 사용한다.

방법은 내가 사용한 방법이랑 같지만, 코드가 간결하고 공간복잡도가 줄어든 코드이다.

튜프을 사용해서 (값,개수)로 각 인덱스에 값을 갱신해줬다.