71. Simplify Path
unix path가 주어질 때 간단화 하는 문제. 즉, 여러 슬래시나 .. 같은 디렉토리 변경 등을 다 처리후 최소화된 경로로 만드는 문제. 스택을 쓰면 되는 간단한 문제. 먼저 슬래시 기준으로 split을 해준다. 일반적인 ., .. 같은 디렉토리 명렁어가 아닌 경우 스택에 넣어주고, ..의 경우에는 스택에서 빼주면 된다. 비어있는 문자열은 연속된 슬래시…
zeikar
Ideas → Reality. Always shipping (•̀ᴗ•́)و
medium 79
307 306 131. Palindrome Partitioning
문자열이 주어질 때 적당히 잘라서 모든 substring이 팰린드롬이 되게 배열을 반환하는 문제. 백트래킹으로 하면 간단하다. 애초에 모든 substring 경우의 수를 반환해야 해서 다 탐색할 수밖에 없다. 다만 그냥 하면 중복되는 substring 체크가 많기 때문에 dp를 섞어주면 빠르게 뽑을 수 있다. 시간 복잡도는 O(2^N * N) 공간 복잡도는…
305 128. Longest Consecutive Sequence
배열이 주어질 때 가장 긴 원소들의 연속 증가 길이를 구하는 문제 (순서는 상관 없음) O(n log n) 풀이는 정렬하면 되니까 쉽다. **O(n)**은 약간 생각해야 함. 일단 O(n)이니까 hashmap 방식으로 가야하고 hashmap으로 구현하려면 각 원소들을 한 번씩만 순회해야 한다. 원소들을 set에 넣어두고 set의 처음 지점인 원소부터 쭉 올…
304 1514. Path with Maximum Probability
간선에 확률이 있는 그래프가 주어진다. 시작점에서 끝점으로 갈 때 확률의 최대를 구하는 문제. 그냥 다익스트라를 돌려주면 된다. 일반 다익스트라가 합이 최소가 되게 한다면 여기서는 곱이 최대가 되게 뽑아주면 된다.
303 592. Fraction Addition and Subtraction
분수들의 식이 주어질 때 계산하는 문제 스트링 파싱 후 계산하면 된다. 초등학교 때 배운 분수의 덧셈 그대로 구현하면 되는데 분모는 최소공배수로 맞추고 분자끼리 더한 후 최대공약수로 분자와 분모를 각각 나눠주면 된다. 정규표현식으로 파싱이 깔끔하게 되는거 같은데 난 무식하게... 하나씩 파싱했다 ㅋㅋ
300 1140. Stone Game II
돌들이 있고 Alice와 Bob이 차례로 돌을 가져갈 때 최대가 되게 가져가는 점수를 구하는 문제. 1 - 2*M개의 돌을 가져갈 수 있다. 이런 게임류 문제가 익숙하지 않으면 꽤 어렵다. 이렇게 두면 좀 보일까 싶은데 쉽지 않다. 여기서 Alice와 Bob의 관계를 생각해봐야 하는데 Alice는 Bob이 최소로 가져가게 골라야 한다. 그럼 Alice가 가…
299 650. 2 Keys Keyboard
복사, 붙여넣기만 가능한 키보드에서 특정 길이를 만드는 최소 횟수를 구하는 문제 일단 간단히 DP로 풀리긴 한다. dp[i][j] = i길이를 j만큼 붙여넣어 만들때 최소 횟수. O(n^2) 그런데 여기서 수학적으로 접근하면 O(n)으로 가능하다. 자세한건 에디토리얼 참고.
298 264. Ugly Number II
소인수가 2, 3, 5로만 이루어진 수를 ugly number라 할 때 n번째 ugly number를 구하는 문제 n범위가 작아서 무식하게 구해도 통과는 된다. 좀 더 O(n)으로 잘 구해볼 수 있을까.. 약간의 dp를 쓸 수 있다. 일단 다음 수는 이전의 ugly number들 뒤에 2, 3, 5를 곱한 수가 된다. 그 중 제일 작은 수가 다음 수가 된다…
297 1937. Maximum Number of Points with Cost
2차원에서 점수를 먹는 문제. 먹을 때 이전에 먹은 열과 비교해서 그 차이만큼은 빼야 한다. 3차원 dp는 쉽다. 다만 시간 초과. 2차원으로 어떻게 하면 줄일 수 있을까? 왼쪽에서 왔을 때의 최대와 오른쪽에서 왔을 때의 최대를 같이 구해서 그 중 최대값으로 업데이트하면 된다. 에디토리얼 참고. 간단하게 설명하면 left_max[i]는 i보다 왼쪽의 점수 …
296 624. Maximum Distance in Arrays
배열이 여러개 주어질 때 서로 다른 배열끼리 가장 큰 원소의 차이를 출력하는 문제. 그리디? 라고도 볼 수 있다. 일단 차가 가장 크려면 각각 다른 배열의 최대와 최소를 빼줘야 한다. 중간에 있는 원소는 필요 없다. 간단하고 직관적으로 짜려면 모든 배열의 최대와 최소를 구한 뒤 같은 배열이라면 두번째 최대 혹은 두번째 최소로 답을 구할 수 있긴 하다. 힙으…