Algorithm/인프런(inflearn)86 [ 자바스크립트(JavaScript) ] section05 - 8 - 모든 아나그램 찾기 📍 section05 - 8 - 모든 아나그램 찾기 S 문자열에서 T문자열과 아나그램이 되는 S의 부분 문자열의 개수를 구하는 문제이다. 문제가 조금 어려울 수 있는데, 요구사항을 하나씩 구현하면 된다. 이전까지 아나그램 문제를 풀 때는 hash의 특징을 사용했고, 부분 문자열을 구하는 방식은 slidingWindow을 이용하여 풀었다. 여기에 인덱스 관리를 위해 twoPointer 방식만 적용해주면 된다. 나는 while문을 사용해서 풀었는데, 올바른 방향으로 풀었는지 궁금해서 질문을 남겼더니 선생님께서 칭찬해주셨다.( ☺️ ☺️ ) 이것보다 더 짧은 코드로 짜고 싶다는 생각이 들었다. 나는 이렇게 풀었다. 1. 투 포인터를 사용해 rt++가 되면서 sum을 구한다. 2. sum의 길이가 m과 동일하면.. 2021. 8. 30. [ 자바스크립트(JavaScript) ] section05 - 7 - 아나그램 📍 section05 - 7 - 아나그램 Anagram은 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어를 아나그램이라고 한다. 이 문제를 hash로 풀면 O(N)으로 간단하게 풀 수 있다. 여기서 아나그램이 성립하지 않는 경우를 생각하면 편하다. 문자열 s1의 원소를 hash값으로 만든다. 비교할 문자열 s2를 반복문으로 순회하면서 아나그램이 되지 않는 경우를 찾는다.(아나그램이 성립하지 않는 경우: s2의 값이 hash값에 존재하지 않는 경우, hash값의 value가 1보다 작은경우) 조건문밖에는 hash의 key값을 -1씩 빼준다. let s1 = "AbaAeCe"; let s2 = "baeeACA"; let s1H = new Map(); console.log(solutio.. 2021. 8. 29. [ 자바스크립트(JavaScript) ] section05 - 6 - 학급회장 📍 section05 - 6 - 학급회장 투표용지를 보고 어떤 기호의 후보가 학급회장이 되었는지 출력하는 문제이다. 이런 유형은 해쉬(hash)로 풀면된다. JS에서 hash 문제는 key:value 형태인 object로 풀면 될 줄 알았는데, ES6 문법에 새로운 자료구조인 Map 형으로 푸는것이 더 쉬웠다. 기본적으로 object의 key는 string | symbol형만 가능하지만 Map의 key는 함수, 객체, 모든 기본 요소를 포함할 수 있다. 또한 object는 nonIterable이라서 for문 대신 Object.entries() | Object.keys() | Object.values()를 사용했지만 Map은 iterable 하기 때문에 for문을 사용할 수 있다. 또한, object의 순.. 2021. 8. 29. [ 자바스크립트(JavaScript) ] section05 - 5 - 최대 매출 📍 section05 - 5 - 최대 매출 연속된 K일 동안의 최대 매출액을 구하는 slidingWindow 문제인데 여기서 문제인 건 slidingWindow을 처음 배운것이다. twoPointer를 배웠다면 범위를 많이 벗어나지 않아서 다행이었다. N의 범위는 100,000까지인데, 만약, 시간복잡도가 O(N^2)이었다면 시간초과 판정을 받았을 것이다. 되도록 O(nlogn)이내로 끊자. 이 문제의 핵심 요지는연속된 3일간인데, 나는 while문으로 투 포인터를 사용하면서 rt-lt+1===k을 지키는 선에서 최대매출을 계산했다. 그와 비슷하게 강사님은 for문으로 푸셨는데, 이전에 k번째까지의 합을 구해놓고, sum을 누적하면서 k번째 이전의 인덱스를 계속 빼줬다. 즉, 이전 단계+현재 단계에 중복.. 2021. 8. 27. [ 자바스크립트(JavaScript) ] section05 - 4 - 연속 부분수열2 📍 section05 - 4 - 연속 부분수열2 연속 부분수열1보다 약간 더 어려운 문제였다. 이전 문제는 다음 rt 포인터가 기준보다 커지면 arr[lt++]처리를 해줬는데, 이 문제는 특정 기준 값 이하인 경우 새로운 숫자가 포함된 연속 부분 수열을 구해주면 된다. 그럼 이전 숫자는 안 구하는지 궁금할 수 있는데, 이전 숫자가 끝에 있으면서 연속 수열인 값은 이전 과정에서 구했기 때문에, 새로운 경우의 수만 누적해주면 된다. 반복문을 따라 sum+=arr[rt]를 누적한다. 만약, sum>target이면 sum target) { sum -= arr[lt++]; } ans += rt - lt + 1; } return ans; } 2021. 8. 27. 이전 1 ··· 7 8 9 10 11 12 13 ··· 18 다음
