65. Valid Number
문자열이 valid 한 수인지 판단하는 문제. 딱 보니 정규식으로 풀린다... 디버깅 시 위 사이트를 이용함. 문제에 나온 그대로 정규식으로 만들어주면 된다.
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
Posts 165
164 163 84. Largest Rectangle in Histogram
히스토그램이 있고 여기서 가장 큰 직사각형의 넓이를 구하는 문제. 이건 유명한 문제라 어떻게 보면 상식? 느낌. 스택을 쓰면 O(n)으로 풀 수 있다. 일단 키 포인트는 한 지점 까지의 최대 넓이를 구할 때 그보다 왼쪽에 큰 값이 있다면 그 큰 값은 무시된다는 것이다. 왜냐하면 현재 지점의 높이가 더 낮기 때문에 직사각형을 그렸을 때 포함되지 않기 때문이다…
162 1641. Count Sorted Vowel Strings
n 개의 모음을 이어 붙일 수 있다. 이때 사전 순으로 정렬된 문자열의 개수를 구하는 문제. 딱 보니 DP로 풀어야겠다는 생각이 든다. 로 두면 DP[i][j] = DP[i - 1][k] (0 <= k <= j)가 된다. 추가로 DP[i] 행은 계속 덮어 띄워지므로 1차원으로 줄일 수 있다. DP[j]: j번째 모음으로 시작하는 문자열의 개수
161 32. Longest Valid Parentheses
괄호로 된 문자열이 주어지고 valid한 괄호 부분 문자열의 최대 길이를 구하는 문제. 딱 보니 스택이 생각난다. ( 괄호가 보이면 스택에 현재 인덱스를 넣고 ) 괄호가 보이면 스택에서 빼는 방식이다. 뺄 때 현재 인덱스에서 스택의 마지막 인덱스를 빼면 길이가 된다. 여기서 ()() 같이 서로 이어져야 되므로 스택은 기본적으로 1개의 원소가 들어가 있어야 …
160 1. Two Sum
배열에서 두 개의 합이 target이 되는 두 인덱스를 구하는 문제. O(n^2) 풀이는 너무 쉬우므로 O(n) 풀이를 보자. 먼저 2개의 합을 구한다는 것은 하나를 골랐으면 다른 수는 자동으로 정해진다는 것이다. 즉, nums[i] 를 골랐다면 다른 수는 무조건 target - nums[i] 이어야 한다. 여기서 hashmap으로 target-nums[i…