코딩테스트 - 패스트캠퍼스 챌린지 30일차

수강한 강의

Part 3. 알고리즘 유형별 풀이

Chapter 02 알고리즘
- 두 포인터 (Two Pointers) - 응용 편

학습 후기
어느덧 챌린지 30일 차가 되었다. 매일 강의를 듣고 블로그에 글을 쓰며 며칠이 지났는지 확인하지 않았지만 오늘 문뜩 글 첫 제목을 쓰는데 30일 차여서 좀 놀랍다. 앞으로 남은 20일 더 힘내서 공부하자

백준 13144번 문제
수열에서 연속한 1개 이상의 수를 뽑았을 때 같은 수가 여러 번 등장하지 않는 경우의 수
정답이 최대치일 때를 생각해본다. 1~10만까지 차례로 늘어나는 배열이라면 모든 구간이 카운트되기에 그때 계수는 50억이므로 Long을 자료형으로 선택한다.
접근법
1. 가장 쉬운 방법 O(N^3)
1) 왼쪽 시작을 L로 결정: 총 O(N)
2) 오른쪽 끝을 R로 두면 L부터 시작해서 R까지 늘려가면서 범위를 정함: O(N)
3) R을 이동해서 추가된 원소가 [L, R - 1] 안에 있는지 확인: O(N)
따라서 이 경우 시간 복잡도 O(N^3)이 된다.

2. 개선된 방법 O(N^2)
위 1번에서 3) 경우를 카운트 배열을 사용하여 기록해 놓는다.
배열에 [L, R-1] 사이에 있는 수를 카운트 배열로 놓고 새로 R을 구해서 [L, R-1] 사이에 R이 포함되어있는지 구해본다면 해당 인덱스만 탐색하면 되니 O(1)로 줄어 총 시간 복잡도는 O(N^2)으로 줄지만 여전히 N이 10만 일 경우 시간 복잡도가 초과된다.

3. 투 포인터 방법 O(N)
1) 왼쪽 시작 L의 이동 횟수 N번: O(N)
2) 오른쪽 끝을 R을 이전의 R부터 시작해서 이동
3) R을 이동해서 추가된 원소가 [L, R-1] 안에 있는지 확인은 개선된 방법에서 사용했던 것처럼 배열을 쓰면 O(1)로 해결 가능
4) L, R이 각자 최대 N번 이동하니까, O(N)으로 N이 10만이더라도 시간 복잡도를 충분히 만족한다.

수강 인증샷

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.