코딩대장경

중복 되지 않는 가장 긴 문자열을 찾는 문제. 문자열을 n번 순회하고 해당 문자열의 길이를 하나씩 늘려가며 검사하는 로직 통과는 했지만 상당히 낮은 속도를 보여줬다. from collections import Counter as ct class Solution: def lengthOfLongestSubstring(self, s: str) -> int: set_s = list(set(s)) if len(set_s) == 0: return 0 elif len(set_s) == 1: return 1 max_result = len(set_s) result = 2 for i in range(len(s)): if i + result > len(s): break flag = 0 t1 = ct(s[i:i + resul..

내가 푼 코드 제공받은 리스트 중에 가장 작은 값을 비교하여 새로운 노드에 값을 계속 추가해줬다. 근데 런타임이 아주 길게 나오며 아슬아슬하게 통과한 것 같다. class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next from typing import List, Optional class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: for i in range(len(lists)-1,-1,-1): if not lists[i]: del lists[i] if len(lists) == 0: return d..

중복된 문자를 제거하고 사전적 순서가 가장 적은 순으로 나열하라는 문제다. 이 문제는 직접 풀긴 했지만 속도가 100ms 정도로 하위 5%에 속하는 속도를 보여서 문제를 풀긴했지만 아주 찝찝하기 그지 없었다. stack문제인데 대체 어디서 스택을 써야하는지 감도 오지 않는다. class Solution: def removeDuplicateLetters(self, s: str) -> str: temp_s = sorted(list(set(s))) t1 = 0 temp_i = 0 result = [] while temp_s: t2 = temp_s[t1] for i in range(temp_i,len(s)): if s[i] == t2: flag = 0 for j in temp_s: if j not in s[i:..

토요일에 배웠던 Linked List가 어려워서 관련 문제를 하나 풀어보았다. https://leetcode.com/problems/reverse-linked-list-ii/ Reverse Linked List II - 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 위 그림을 예제로 개념을 설명하겠다. 1. 2번부터 4번까지 순서를 바꿔준다. 2. 1 ->4, 2->5로 가리키는 주소를 바꿔준다 어렵지 않게 풀지 알았는데 구현하는데에 1시간 정도 걸려서 문제를 ..

토요일 새벽에 문제를 풀어서 강의를 적용하지 않은 방식과 적용한 방식 2가지를 소개하겠다. 간단하게 요약하자면 괄호가 제대로 닫히는지 확인하는 로직을 짜라는 문제다. 그리고 그것을 VPS라고 부른다. 이 문제를 보고 처음에 든 생각은 '입력 값은 무조건 짝수여야만 하겠구나'였다. 하지만 올바르지 않은 VPS도 짝수개 일 수 있다. 예제를 보며 10분간 멍때리다 보니 답이 생각났다. 왼쪽 괄호(Opener)와 오른쪽 괄호(Closer)의 갯수를 카운트하면 답이 나온다 Closer의 수 가 Opener 의 수보다 많아 질때 VPS가 되지 못 한다. (왼쪽부터 계산했을 때) ( ) ) ( ( ) 이 시점에서 뒤에있는 문자열은 체크할 필요없이 "NO"를 출력하면 된다. 만약에 끝까지 오른쪽 괄호가 왼쪽 괄호보다..

두 정렬 리스트의 병합 https://leetcode.com/problems/merge-two-sorted-lists/ Merge Two Sorted Lists - 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 linked list.. 개념은 익숙하나 처음 들어보는 자료구조다. 노드 관련해서는 많이 취약한 편이라 이번 자료구조는 풀기 어려웠다. 어찌저찌 통과는 했지만 답안을 보니 내가 푼것은 편법이였다. 두 배열의 값을 모두 꺼내 sort시킨 후 다시 노드로 만..

이 문제는 Easy라고 나와 있지만 영어로 되어있어서 나는 문제를 이해하는 곳 부터 막혔다. 간단히 말해서 2n개의 숫자 input이 주어지고 n개의 쌍으로 만들어 각 쌍의 최소값이 가장 크게 만들어 모두 더한 것이 output이다. (간단하지 않다.) 처음에는 어떻게 두개의 값을 쌍으로 만들어서 더할까 고민을 많이 했다. 조합 문제인가 했지만 아니였고 아무리 생각해도 두개의 값을 묶는 방법은 떠오르지 않아 답안을 보게 됐다. 문제는 간단했다. 두개의 쌍을 만들 필요없이 정렬을 한 후 순서대로 2개의 값을 묶으면 최솟값을 가장 크게 만들 수 있다. 앞으로는 문제가 막힐때에 수학적으로 접근해보는것도 나쁘지 않은 방법 같다.

영어를 몰라서 첫문자와 끝문자가 같은 부분을 출력하는 로직을 짰다가 다 지웠다.. 팰린드롬 문자란 뒤집어도 같은 문자를 뜻한다. 예시로 'bsb' 를 꺼꾸로 뒤집어도 'bsb'가 되니 팰린드롬 문자에 해당한다. 총 3가지 로직을 소개하겠다. 처음에는 문자열을 2~n개씩 nlogn번 검사하는 로직이다. 예상되는 시간복잡도는 O(nlogn) 이 로직은 통과 했지만 시간이나 메모리가 다른 로직에 비해 비효율적이였다. class Solution: def longestPalindrome(self, s: str) -> str: if s == s[::-1]: return s tl = [] for i in range(len(s)): for j in range(len(s) - 1, i - 1, -1): if s[i] =..

python의 딕셔너리는 다음 코드에서 Keyerror가 난다. strs = ["eat","tea","tan","ate","nat","bat"] ans = {} for i in strs: ans["".join(sorted(i))].append(i) print(list(ans.values())) ans에 key가 없을 때는 값을 추가할 수 없다는 에러가 난다. 그렇다고 몇의 공간이 필요한지, 어떤 키를 사용 해야 하는지 모르는 상황에서 key를 미리 할당할 수 도 없는 노릇이다. 그래서 사용해야 하는 것이 defaultdict 다. 기본 라이브러리인 from collections import defaultdict 로 사용할 수 있으며 다음과 같이 사용하면 된다. strs = ["eat","tea","tan..