junhwa100 님의 블로그

[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)..

1. 문제 이해정수 배열 nums가 주어진다.다음 조건을 만족하는 세 수의 조합을 모두 리턴한다.- 세 수의 인덱스는 모두 다르다.- 세 수의 합은 0이다. 2. 풀이 과정먼저 오름차순으로 정렬한다. 배열을 순회하며 첫 번째 요소(a)를 고정한다. 이때 나머지 두 수의 합, target은 -a가 되어야 한다.반복문이 진행될 때, 이전에 이미 사용했던 같은 값의 a를 만나면 건너뛴다.(모든 조합을 이미 찾았기 때문) a를 고정한 상태에서 나머지 배열에 투 포인터를 적용한다.left, right 포인터를 만들어 배열 양측 끝의 인덱스로 초기화한다. left 만약 세 수의 합이 0이 되는 경우, 세 수의 조합을 정답 배열에 추가한다. left, right 포인터를 모두 업데이트한다.(left += 1, r..

1. 문제 이해문자열 배열과 최대 너비(maxWidth)가 주어진다.텍스트의 각 줄이 정확히 최대 너비만큼의 문자를 가지며 완전히 좌우 정렬되도록 포맷팅한다. (조건)- 각 줄에 최대한 많은 단어를 채워 넣는다. 필요한 경우 공백(' ')을 채워 넣는다.- 단어들 사이의 여분의 공백은 가능한 한 고르게 분배되어야 한다.- 한 줄의 공백 개수가 단어들 사이의 빈 공간에 균등하게 나누어지지 않는다면, 왼쪽에 있는 빈 공간이 오른쪽에 있는 빈 공간보다 크도록 한다.- 텍스트의 마지막 줄에 대해서는, 왼쪽 정렬이 되어야 하며, 단어들 사이에 여분의 공백을 삽입하지 않는다. 2. 풀이 과정주어진 단어 배열을 maxWidth가 초과하지 않도록 각 줄에 들어갈 단어들로 묶는다.단어들을 순회하면서 현재 줄에 단어를 ..