본문 바로가기
728x90
반응형

전체 글

 (30)
[medium] 207. Course Schedule 문제 https://leetcode.com/problems/course-schedule/description/ 풀이방법 course의 prerequisites를 탐색하다가 순환이 존재하는지를 찾는 문제이다. prerequisites 리스트를 그래프로 만든다. 파이썬에서는 dict 구조 활용 각 course에 해당하는 graph를 탐색하다가 순환이면 탐색을 중단하고 False를 리턴. 그렇지 않으면 graph 탐색을 계속한다 순환인지 여부를 찾기 위해서는 course와 그에 해당하는 prerequisites를 history로 관리해야한다. 그래프 탐색 과정에서 현재 course가 이미 history에 있으면 순환이다 그래프 탐색과정에서 순환이 아닌 course들은 이미 검증이 완료되었음을 저장해두었다가, ..
[medium] 1268. Search Suggestions System 문제 https://leetcode.com/problems/search-suggestions-system/description/ 풀이방법 찾고자 하는 단어(searchWord)랑 일치하는 알파벳 개수별 각각의 product들을 리스트로 출력하는 문제이다 1. 문자열 순서대로 출력해야하기 때문에 products 소팅 2. products로 trie 생성. 이 때 children과 함께 현재 노드에서 가능한 product들을 list로 관리 3. searchWord들의 알파벳을 trie에서 탐색하면서 해당 노드에서 가능한 product들을 최대 3개까지 list에 저장. searchWord의 알파벳을 현재 node부터는 더이상 탐색이 불가능할 경우 flag를 False로 변경하고 빈 list 저장 코드 cl..
[hard] 745. Prefix and Suffix Search 문제 https://leetcode.com/problems/prefix-and-suffix-search/description/ 풀이방법 처음에는 단순하게 리스트에서 문자열 비교 방법을 사용했는데, 역시나 시간초과. 두번째로는 아래의 힌트를 참고해서 단어 이어붙인 다음, 문자열 비교하는 방법을 사용했는데 이것도 역시 시간초과. 더보기 힌트 For a word like "test", consider "#test", "t#test", "st#test", "est#test", "test#test". Then if we have a query like prefix = "te", suffix = "t", we can find it by searching for something we've inserted start..
[medium] 583. Delete Operation for Two Strings 문제 https://leetcode.com/problems/delete-operation-for-two-strings/ 풀이방법 word1 에서 몇번의 알파벳 추가/삭제 작업을 거치면 word2를 만들 수 있는지 찾는 문제이다. word1과 word2에서 연속되는 공통부분을 먼저 찾고 공통부분의 길이를 len_subseq 라고 하면, 답은 len(word1)-len_subseq 과 len(word2)-len_subseq 의 합이 된다. 공통부분을 찾는 방법은 현재까지 일치하는 길이를 dp배열에 저장하는 edit distance 방식을 사용한다. word1의 index(wp1)와 word2의 index(wp2) 지점까지의 가능한 가장 긴 공통부분의 길이를 dp[wp2][wp1]라고 할 때, dp[wp2][..
[hard] 51. N-Queens 문제 https://leetcode.com/problems/n-queens/description/ 풀이방법 퀸이 갈 수 있는 방향은 가로(↔), 세로(↕), 대각선(↗,↘) 인데 이때 갈 수 있는 방향에 다른 퀸은 없어야 한다. 이 규칙을 만족하면서 모든 행에 퀸을 배치할 때, 가능한 모든 퍼즐 결과를 출력하면 된다. 각 행, 열, 대각선에는 하나의 퀸만 배치되어야 한다. 그래서 이미 퀸이 배치되어있는 열, 대각선을 각각의 리스트에 저장해놓아야 한다. 열을 저장하는 건 간단한데 대각선은 어떻게 저장해야 하나 싶었는데 아래 표를 보면 row-col 이 동일하면 같은 아랫방향 대각선, row+col 이 동일하면 같은 윗방향 대각선이라는 걸 알 수 있다. 0,0 0,1 0,2 1,0 1,1 1,2 2,0 2,..
[medium] 120. Triangle 문제 https://leetcode.com/problems/triangle/ Triangle - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 풀이방법 각 row 마다 하나의 값을 찾아서 이 숫자들의 합이 최소가 되도록 하면 된다. triangle의 각 list가 하나의 row에 있는 숫자들을 저장해둔 것 이므로 각 list에서 하나의 값을 선택해야한다. 이 때, i번째 row에서 선택된 값이 list의 j번째 숫자라면(traingle[i][j]) 그 다음 ro..
728x90
반응형

티스토리툴바