연속된 element로 구성된 nums의 부분집합 중, 합이 k가 되는 부분집합의 갯수를 리턴하라 각 부분합을 원소로 표현한 sum이라는 배열을 만들고, map이라는 딕셔너리를 만들었다. 그 후 sum에서 k를 뺀 값이 key로 딕셔너리에 존재하면 answer를 하나 추가해주었고, 그렇지 않으면 sum만 딕셔너리에 추가해주었다. 사실 골머리를 앓았던 문제라서 도식으로 정리해보았다. 두번째를 예시로 들어본다. [ 0, 1, 2, 3 ]이라는 배열이 들어왔을 때, 각 element를 연쇄적으로 더한 sum이라는 배열을 만들었다. 얘는 [ 0, 1, 3, 6 ]이 될 것이다. 실제 주어진 배열은 [ 1, 2, 3 ] 이지만 1개의 원소만 가진 부분합도 카운팅되므로 편의상 0을 넣었다. 저렇게 만든 sum 배열..

s의 부분집합 중 가장 긴 palindromic한 요소를 찾아라! DP문제고 투포인터의 원리(실제로 투포인터는 아님)를 이용하여 문제를 풀었다. i를 Loop를 돌리면서 j라는 포인터를 두고, 두개의 스트링이 같은 지점까지 모두 검사한다. 만약 두개의 스트링이 같다면, left는 한칸 줄이고, right는 한칸 늘리면서 최대 palindromic까지 검사한다. 이렇게 검사한 결과가 max의 길이보다 크다면, max를 해당 값으로 바꿔준다(substring이용)

배열의 subset인 triplet을 구해서, 해당 원소의 총합이 0이 되는 배열을 묶어 리턴하라는 문제다. 오름차순으로 배열을 정렬한다. 이후 포인터를 3개 두고 Loop를 돌린다. i는 고정시키고 나머지 두개의 포인터를 조절하는 방식으로 로직을 짯다. 이때 i와 i-1이 같다면, i-1을 검사할때 i도 검사된거나 다름 없으므로 continue를 사용하여 검사하지 않도록 한다. 여느 투포인터 검사처럼 r이 l보다 큰 시점까지만 검사해주고, 조건에 부합하는 solution은 리턴배열에 push한다. 이때 l은 늘리기만, r은 줄이기만 하는 검사를 진행하는데, 인접 원소와 값이 같다면 검사를 건너뛸 수 있도록 while문으로 처리해준다. 또한 sum이 음수라면 l을 옮기고, 양수라면 r을 줄이는 식으로 조..

coins배열의 원소들을 합하여 amount로 입력된 값을 만들려고 한다.(원소들은 중복 사용이 가능하다) 이때 만들 수 있는 갯수가 가장 적은 케이스를 찾아 해당 갯수를 리턴한다. 만드는것이 불가능하다면 -1을 리턴한다. 전형적인 DP문제로, amount만큼을 갯수로 가진 배열을 만들어 각 부분의 solution을 구해 global과 비교하면 된다. dp라는 배열을 만들고 amount가 0일때의 값을 입력한다. 그 뒤, 0부터 amount까지에 대한 Loop를 돌면서 coin의 각 원소와 비교한다 예컨데 [ 1, 2, 5 ]인 coins에 대해 i가 5라고 해보자. 일단 coin이 i보다 커지면 의미가 없으므로, i는 coin보다 항상 크거나 같아야 한다. 이 조건을 만족하는 경우에 대해, 해당 coi..

전화기의 숫자마다 알파벳이 매핑되어 있는데, 숫자 조합을 선택했을 때 숫자에 매핑된 알파벳으로 만들 수 있는 조합 을 찾는 문제다 기본적으로 backTracking문제다 keyMap이라는 딕셔너리에 매핑관계를 정의한다. 이후 backtrack이라는 함수를 만들었는데, 이는 path와 i를 인자로 갖는다. 콘솔을 다음과 같이 찍어 확인해보았다. 각 digit을 key로 두고 keyMap을 참고하여 letter를 찾아낸다. 그리고 letter 하나당 다음 조합을 재귀로 돌리는 방식이다. 이때 path의 조합이 모두 구해지면 digit의 길이와 같아질 것이므로 경계값을 걸어둔다

input 배열인 nums에 대해 같은 숫자들(0,1,2)을 오름차순으로 모두 인접하게 만들라는 문제이다. 단, sort 메소드 쓰지말고 O(1)을 지키라고 한다. 단순한 방법으로 접근해보았다. 일단 0,1,2가 몇개 있는지 세었다. 이후 개수만큼 배열을 만들어 리턴해주었다.