인프런 JAVA 알고리즘 정리(Two pointers, Sliding window 1번~6번)

1. 두 배열 합치기 // 두 개의 배열을 합쳐서 오름차순 정렬 -> 효율적으로 접근해봐라  - 투 포인터

- Arrays.sort 의 시간복잡도는 평균 O(nlog(n)) , 최악O(n^2) 

- O(n) 으로 접근하도록 -> 투 포인터 알고리즘 

 

2. 공통원소 구하기 // 두 개의 배열에서 공통 원소를 추출해사 오름차순 정렬 시켜 - 투 포인터

- 두 배열을 오름차순 정렬

- 변수 2개 선언

- 두 배열이 같으면 출력, 한쪽이 크다? 작은쪽 변수를 1증가

- 한쪽이 끝날 때 까지 진행.

 

3. 최대 매출 // 배열이 있으면 N일 동안의 최대 매출 출력 - 슬라이딩 윈도우

10일의 매출중 연속된 3일의 매출의 최대 값은

연속 3일간 최대 매출은 56원

 

4. 연속부분수열  // 투 포인터 + 슬라이딩

작다면 last를 키워본다. 크다면 줄여본다.

 

5. 연속된 자연수의 합  // 15가 입력되면 

1+2+3+4+5=15

7+8=15

4+5+6=15

위와 동일한 형식

 

 

6. 최대 길이 연속부분수열 // 투 포인터

문제 출처 : 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 / 인프런

이 문제는 글로 설명하기가 어렵다...