Problem : https://leetcode.com/problems/extra-characters-in-a-string Difficulty : Medium Status : Solved Time : 00:22:04  문제 설명  더보기0-인덱스의 문자열 s와 단어들의 사전인 dictionary가 주어진다. s를 하나 이상의 겹치지 않는 부분 문자열로 나누며, 부분 문자열은 dictionary 내에 존재해야 한다. 이 부분 문자열 어디에도 속하지 않는 잉여 문자들이 존재할 수 있다. s를 최적으로 쪼갠다고 가정할 때, 남는 잉여 문자들의 최소 개수를 반환하라. 풀이 순수 DP로도 풀 수 있다. 조금 비효율적이겠지만.현재 idx를 기준으로현재 idx의 문자가 잉여 문자임을 가정한다. 그렇다면 dp[idx+..

Problem : https://leetcode.com/problems/lexicographical-numbers Difficulty : Medium Status : Solved Time : 00:14:11  문제 설명  더보기정수 n을 입력으로 받았을 때, [1, n] 범위의 정수를 사전식 순서대로 정렬하여 반환하라. 이 때, O(n)시간복잡도와 O(1) 추가 공간복잡도 알고리즘을 사용해야만 한다. 풀이 사전식 순서 = DFS. 사전식 순서의 규칙을 떠올려보자.한 숫자가 다른 숫자의 진부분집합이면, 그 숫자가 앞에 와야 한다 (예 : 111 -> 1111 -> 1112)그렇지 않다면..처음 자리부터 두 숫자의 교집합을 구하고 (예 : 111452,)교집합이 아닌 자리수부터 둘을 비교하여, 더 작은 숫자..

Problem : https://leetcode.com/problems/different-ways-to-add-parentheses Difficulty : Medium Status : Solved Time : 00:18:44  문제 설명  더보기주어진 문자열과 부호로 이루어진 수식을 입력으로 받아, 숫자와 연산자를 그룹화하는 모든 가능한 경우의 수를 계산하여 반환하라. 어떤 순서로 반환하여도 상관 없다. 생성된 테스트케이스는 출력값이 32비트 정수 내에 존재하며, 결과의 서로 다른 가짓수는 10^4를 초과하지 않는다. 풀이 처음에는 DP로 풀면서 뭐야, 왜 이렇게 복잡해? 싶었으나.. 내 착각이었다. DP로 풀면 결국 O(N^3)에 가까운 비효율적인 방식의 풀이가 되므로, 조금 다른 접근 방식이 필요하다..

Problem : https://leetcode.com/problems/largest-number Difficulty : Medium Status : Solved Time : 00:15:23  문제 설명 더보기음의 정수가 아닌 nums를 입력으로 받아, 이들을 하나로 이었을 때 가장 큰 수가 되도록 정렬하여 반환하라. 결과값이 매우 클 수 있으므로, 정수 대신 문자열 형태로 반환하도록 한다. 풀이 분명히 어디서 많이 봤었는데...? 하는 문제. 정렬을 그리디하게 수행하면 되는데, 임의의 수 a, b에 대해서 (a, b를 이은 결과) >= (b, a를 이은 결과)가 항상 유지되도록 정렬하면 된다. 그리디 + 정렬 문제. 풀이 코드class Solution: @staticmethod def com..

Problem : https://leetcode.com/problems/uncommon-words-from-two-sentences Difficulty : Easy Status : Solved Time : 00:08:23  문제 설명  더보기번역여기서 문장이란, 알파벳 소문자로 이루어진 단어들이 스페이스바 공백 하나로 구분되는 문자열을 의미한다. 또한 어떤 단어가 한 문장에서 오직 딱 한번 나타나고, 다른 문장에서는 나타나지 않을 때 그 단어를 평범하지 않다고 하자. 문장 s1, s2가 주어졌을때, s1과 s2 안의 평범하지 않은 단어 리스트를 반환하라. 단어의 순서는 상관이 없다. 풀이 오랫만의 풀이가 되었다. 일에 이리 치이고 저리 치이다보니 이렇게 늦어졌다. 핵심은 uncommon을 빠르게 구하는 ..

Problem : https://leetcode.com/problems/evaluate-boolean-binary-tree/  Difficulty : Easy Status : Solved Time : 00:04:22  문제 설명   풀이 DFS로 간단히 접근하자.만약 현재 노드가 리프노드라면, 현재 노드값이 1인지의 boolean 값을 검사하여 반환하자.리프노드가 아니라면, 조건상 Full binary tree이므로 왼쪽과 오른쪽 서브트리가 반드시 존재한다. 왼쪽, 오른쪽 결과물을 현재 노드값에 따라 or 연산, 혹은 and 연산을 가하여 바로 반환하면 된다.비재귀로도 가능하겠지만 재귀면 역시 간단하게 풀린다. 풀이 코드(Python)# Definition for a binary tree node.# c..