'투 포인터 알고리즘' 태그의 글 목록

[JavaScript/section 5] 08 - 모든 아나그램 찾기

2022.09.22

📌 08 - 모든 아나그램 찾기(해쉬, 투포인터, 슬라이딩 윈도우) S문자열에서 T문자열과 아나그램이 되는 S의 부분문자열의 개수를 구하는 문자이다. 나의 풀이 방법 아나그램이 되는지 확인하기 위해 해쉬의 특징을 사용했고, 부분 문자열을 구하기 위해 슬라이딩 윈도우 방식과 slice() 함수를 사용하였다. 문제를 해결하고 나서 잘 풀었다고 생각했지만.. 코드를 다시 보니 부분 문자열을 구하는 부분에 있어서 이중 for 문을 사용했기 때문에 효율성(시간 복잡도) 측면에서는 좋지 않다라고 생각했다. for 문을 돌기 전에 t의 해쉬 값을 구한다. for 문을 돌면서 s문자열에 slice() 함수를 이용하여 i 번째 인덱스부터 t문자열 길이 + i 전까지를 잘라준 후 str 변수에 저장한다. (부분 문자열을 ..

Algorithm/인프런(inflearn)

[JavaScript/section 5] 04 - 연속 부분수열 2

2022.09.19

📌 04 - 연속 부분수열 2(투 포인터 알고리즘) N개의 수로 이루어진 수열이 주어진다. 이 수열에서 연속부분수열의 합이 특정 숫자 M이하가 되는 경우가 몇 번 있는지 출력하는 문제이다. 나의 풀이 방법 for 문을 차례대로 돌며 포인터 rt의 위치를 이동시킨다. 포인터가 가리키고 있는 값을 sum에 누적시켜준다. sum이 m보다 작거나 같은 경우 answer++을 해준다. 포인터 rt가 가리키고 있는 값이 m 이하이고 sum과 같지 않다면 answer++을 해준다. 포인터 rt가 1씩 증가할 때마다 가리키고 있는 값이 특정 숫자 M이하가 되는 경우를 생각해야 하기 때문이다. 위 과정에서 sum이 m보다 크고 같아질 경우 포인터 lt가 가리키고 잇는 값을 sum에서 빼준다. sum이 m 이하이고 포인터..

Algorithm/인프런(inflearn)

[JavaScript/section 5] 03 - 연속 부분 수열 1

2022.09.19

📌 문제 N개의 수로 이루어진 수열이 주어진다. 이 수열에서 연속 부분 수열의 합이 특정 숫자 M이 되는 경우가 몇 번 있는지 구하는 문제이다. 만약 N=8, M=6이고 수열이 다음과 같다면 1 2 1 3 1 1 1 2 합이 6이 되는 연속 부분 수열은 {2, 1, 3}, {1, 3, 1, 1}, {3, 1, 1, 1}로 총 3가지이다. 📝 풀이 🧑🏻‍💻 나의 풀이 방법 lt(왼쪽을 담당할 포인터), rt(오른쪽을 담당할 포인터)를 인덱스 0으로 초기화한다. rt 포인터를 한칸씩 이동(증가)시키면서 포인터에 해당하는 값을 sum에 누적시킨다. 위 과정에서 sum이 m보다 크거나 같으면 다음 평가를 위해 while문을 돌면서 lt 포인터에 해당하는 값을 sum에서 빼주고 한칸 이동시켜야 한다. 이전에 su..

Algorithm/인프런(inflearn)

[JavaScript/section 5] 02 - 공통원소 구하기

2022.09.18

📌 문제 A, B 두 개의 집합이 주어지면 두 집합의 공통 원소를 추출하여 오름차순으로 출력하는 문제이다. 📝 풀이 🧑🏻‍💻 나의 풀이 방법 arr1을 sort() 메서드를 사용하여 오름차순으로 정렬한다. arr1을 하나씩 돌면서 includes() 메서드를 사용하여 해당 값이 arr2에 존재(true)한다면 answer에 값을 삽입한다. function solution(arr1, arr2) { const answer = []; arr1.sort((a, b) => a - b); for (let x of arr1) { if (arr2.includes(x)) answer.push(x); } return answer; } let a = [1, 3, 9, 5, 2]; let b = [3, 2, 5, 7, 8];..

Algorithm/인프런(inflearn)

[JavaScript/section 5] 01 - 두 배열 합치기

2022.09.17

📌 문제 오름차순으로 정렬이 된 두 배열이 주어지면 두 배열을 오름차순으로 합쳐 출력하는 문제이다. 📝 풀이 🧑🏻‍💻 나의 풀이 방법(강사님 풀이 방법과 동일😁) 두 배열을 하나로([...arr1, ...arr2]) 합치고 sort() 메서드를 사용하여 정렬함으로써 문제를 해결할 수도 있지만, sort() 메서드를 사용했을 경우 브라우저 엔진마다 다르지만 평균적으로 시간복잡도가 O(nlogn)에 해당한다. 이에 비해 투 포인터 알고리즘을 사용하면 시간복잡도는 O(n + m)이므로 매우 효율적이다. 포인터 p1, p2가 각 배열의 길이보다 작은 경우 while문을 돌며 arr1[p1]과 arr2[p2]를 비교한다. 오름차순으로 합쳐야 하므로 더 작은 값을 answer에 push() 메서드를 사용하여 삽입하..

[JavaScript/section 5] 08 - 모든 아나그램 찾기

[JavaScript/section 5] 04 - 연속 부분수열 2

[JavaScript/section 5] 03 - 연속 부분 수열 1

[JavaScript/section 5] 02 - 공통원소 구하기

[JavaScript/section 5] 01 - 두 배열 합치기

티스토리툴바