junhwa100 님의 블로그

[LeetCode] 21. Merge Two Sorted Lists

1. 문제 이해두 개의 오름차순으로 정렬된 Linked List인 list1과 list2가 주어진다.두 개의 Linked List를 merge하여 하나의 정렬된 Linked List의 헤드를 리턴한다. 2. 풀이 과정dummy 노드를 만든다.tail이 dummy를 가리키도록 초기화한다. list1과 list2가 모두 존재하는 동안, 앞에서부터 값을 비교하여 더 작은 값을 가지는 노드를 tail이 가리키도록 한다.while list1 and list2: if list1.val >= list2.val: tail.next = list2 tail = tail.next list2 = list2.next else: tail.next = list1 ..

[LeetCode] 2. Add Two Numbers

1. 문제 이해두 개의 non-empty Linked List가 주어진다.이 Linked List들은 각각 역순의 non-negative 정수를 나타낸다.예를 들어, 2 -> 4 -> 3이라면 342를 나타낸다.두 개의 Linked List의 합을 같은 방식으로 Linked List로 나타내고 그 head를 리턴한다. 2. 풀이 과정- l1과 l2의 헤드부터 비교한다.- 각 노드 값의 합이 10이 넘어가는지 확인한다.(올림수 확인)- 결과를 in-place로 l1에 갱신하여 저장한다.라는 발상으로 다음과 같이 구현하였다.(잘못된 코드)class Solution: def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> O..

[LeetCode] 224. Basic Calculator

1. 문제 이해문자열 s가 주어진다.s는 '+', '-', '(', ')', ' '으로 이루어진다.s의 계산값을 리턴한다. Example 3:Input: s = "(1+(4+5+2)-3)+(6+8)"Output: 23 2. 풀이 과정두 자릿수 이상의 수를 처리할 수 있어야 한다.공백도 처리해야 한다. 문자열 s를 순회하면서 수와 연산자를 분리하여 처리한다. 현재 처리 중인 숫자를 저장하는 변수 current_number를 만든다.현재 부호를 처리하는 변수 sign을 만든다. 여는 괄호 '('를 만나면 현재까지 괄호 밖에서 누적된 결과를 값과 부호 두 가지 형태로 저장한다.elif char == '(': sign_stack.append(result) sign_stack.append(sign) ..

1. 문제 이해두 개의 문자열 ransomNote와 magazine이 주어진다.만약 ransomNote가 magazine에 있는 문자들로 construct 될 수 있으면 true를 리턴한다. 아니면 false를 리턴한다. 2. 풀이 과정파이썬의 Counter 객체를 활용한다.두 문자열 모두 각각 Counter 객체를 생성한다.(-> 각 문자의 개수로 구성된 딕셔너리가 생성된다.) ransomNote의 Counter 객체에서 magazine의 Counter 객체를 뺀다.만약 magazine 문자열이 ransomNote의 문자열을 포함하고 있으면 빈 딕셔너리 {}를 리턴한다. 3. 전체 코드class Solution: def canConstruct(self, ransomNote: str, magaz..

1. 문제 이해m*n matrix가 주어진다.spiral(나선형) order로 matrix를 순회하고 그 순서에 맞는 요소들의 배열을 리턴한다. 2. 풀이 과정처리해야 할 영역의 경계선을 정하고, 한 줄 읽을 때마다 경계선을 안쪽으로 밀어버리는 방식을 구상한다.top, bottom, left, right라는 4개의 변수를 사용하여 현재 처리해야 할 사각형의 경계를 설정한다. top 왼쪽 -> 오른쪽: top 행을 읽는다. 다 읽으면 top을 1 증가시킨다.위 -> 아래: right 열을 읽는다. 다 읽으면 right를 1 감소시킨다.오른쪽 -> 왼쪽: bottom 행을 읽는다. 다 읽으면 bottom을 1 감소시킨다.아래 -> 위: left 열을 읽는다. 다 읽으면 left를 1 증가시킨다. matri..

1. 문제 이해주어진 스도쿠 board가 valid한지 판단한다.(bool을 리턴한다.)채우는 것X, 주어진 board가 스도쿠 규칙을 위반하는지 판단하는 것이다. 2. 풀이 과정규칙 위반 여부를 확인하기 위해 행, 열, 박스별로 중복여부를 확인해야 한다.행, 열, 박스 각각 9개의 Set()을 만든다.(Set() 자료형은 특정 숫자를 O(1)에 찾을 수 있다.) 행과 열을 순회한다.행과 열 Set은 그대로 r, c를 인덱스로 사용한다.하지만 박스 Set은 어떻게 인덱스를 구할까?(r // 3)*3 + (c // 3) 공식을 사용한다. 행, 열, 박스 중 만약 하나라도 해당 인덱스의 Set에 존재한다면 False를 리턴한다.본 적 없는 숫자라면 기록한다. 모든 검사를 무사히 통과했다면 유효한 스도쿠 b..

1. 문제 이해두 문자열 s(길이 m), t(길이 n)이 주어진다.t의 모든 문자가 포함된 s의 가장 짧은 substring을 리턴한다. 2. 풀이 과정슬라이딩 윈도우를 생각하며 구현했지만 브루트 포스로 구현되었다;;class Solution: def minWindow(self, s: str, t: str) -> str: if not s or not t: return "" if s == t: return t len_s = len(s) len_t = len(t) target_counts = Counter(t) if t > s: return "" ..

1. 문제 이해문자열 s와 문자열들의 배열 words가 주어진다.(word의 요소들은 모두 길이가 같다.)words에 있는 문자열들을 전부 활용하여 concatenated string들을 만든다.이 concatednated string들 중 s의 substring이 존재한다면 그 substring들의 s에서의 시작 인덱스들의 배열을 리턴한다. 2. 풀이 과정너무 복잡하다..ㅠ 단어 길이(word_len)만큼 슬라이딩 윈도우를 이동시킨다.모든 가능한 단어 경계를 살펴보기 위해 시작 인덱스(offset)을 0부터 단어 길이(word_len) - 1만큼 순회시킨다. 각 offset 루프 안에서 오른쪽 포인터 j를 word_len만큼씩 계속 증가시키며 윈도우를 오른쪽으로 확장한다.윈도우에 새로 들어온 단어(n..

1. 문제 이해문자열 s가 주어진다.중복된 문자 없는 가장 긴 substring의 길이를 리턴한다. 2. 풀이 과정어떻게 중복인지 아닌지 판단하지?-> Set() 자료형을 활용한다.Set() 자료형은 문자가 윈도우에 포함되었는지 여부를 O(1)에 확인 가능하다. 슬라이딩 윈도우 기법을 사용한다.(한 번의 순회로 유효한 substring 여부를 확인한다.) right 포인터를 이동시키면서 s[right]를 윈도우에 포함시킨다. s[right]를 추가하면서 윈도우에 중복이 발생했는지 확인한다.만약 중복이 발생했다면, left 포인터를 오른쪽으로 이동시키며 윈도우의 크기를 줄여나간다.(left를 이동시킬 때, 동시에 윈도우에서 가장 왼쪽의 문자를 제거한다.)중복이 없어질 때까지 반복한다. 중복이 없는 유효한..

1. 문제 이해양의 정수 배열 nums과 양의 정수 target이 주어진다.배열의 요소로 만들 수 있는 요소들의 합이 target 이상인 subarray 중, 최소의 요소를 가지는 subarray의 길이를 요소 개수를 리턴한다.(subarray는 배열의 연속된 요소들이다.) 2. 풀이 과정먼저 배열을 정렬하고 정렬된 배열에서 큰 수부터 집어넣는 방식을 구상하였다.해당 풀이는 다음과 같다.class Solution: def minSubArrayLen(self, target: int, nums: List[int]) -> int: nums.sort(reverse=True) cnt = 0 nums_sum = 0 for i in range(len(nums)..