특정 부분집합을 찾아야 하는데, 이 부분집합만 오름차순으로 sort하면 배열 안의 모든 원소가 오름차순으로 sort되는 부분집합을 말한다 나는 전체 원소를 오름차순으로 만들어 index로 두고, start를 이용하여 처음부터 끝까지 비교하여 완전 같은지 파악한 후 어디서 같지 않은지 표기한다. end도 마찬가지 방식으로 어디서부터 다른지 표기한다 이후 해당 지점을 구하기 위해서 end에서 start를 빼서 센다

점프게임 1과 조건은 같지만, last index까진 무조건 도착한다는 전제이다. 이때 0부터 시작해서 가장 적은 횟수로 last index까지 가려면 몇회가 소모되느냐이다 Greed를 쓸껀데 여기에서 착각하지 말아야 하는 점은 범위단위로 움직인다는 것이다. count, now, max라는 세가지 변수를 두었다 순서대로 배열을 하나씩 돌면서 이를 업데이트 해줄 것이다. max를 local마다 업데이트 할 것이고, 이는 각 지점에서 최대로 갈 수 있는 지점까지의 값이다 모든 배열에서 로직이 돌면 global max를 찾을 수 있다. index=0에서 시작하니 count가 하나 올라가고 max가 변경된다. 이때 주의점은 범위단위라는 것인데, now와 실제 minmum이 별개로 움직인다는 뜻이다. 예컨데 문제..

각 element의 값은 해당 index로부터 element의 값만큼 떨어진 index로 점프할 수 있음을 나타낸다 이때 마지막 index로 갈 수 있는지의 여부를 묻는 문제이다. 이렇게 단순히 배열을 순회하는 케이스에서는 greedy로 풀어내면 수월하다. target을 배열의 마지막 index로 설정한다. target을 배열의 맨뒤부터 설정하고, 각 원소로부터 target까지 갈 수 있는지 여부를 판단한다 한곳에서라도 방법이 있다면 해당 위치로 타겟을 바꾸어 검사한다 예컨데 [3,2,1,0,4] 은 false인데, 0,1,2,3 위치에서 어떻게 하더라도 index=4로 갈 수 없기 때문이다. 만약 [3,3,1,0,4] 라면 true일 것이다. index=1의 위치에서 index=4로 갈 수 있기 때문이..

연속된 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 배열..

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

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