[투포인터] 프로그래머스#67258 - 보석 쇼핑

[ye-yo]

⚠️ 나의 풀이

• Set을 이용해 중복 제거하여 필요한 최소 보석 개수 계산
• for문을 2번 돌거나 while문을 돌면서 범위에 존재하는 보석의 조합이 Set을 통해 중복 제거한 보석 조합과 일치하는지 비교
• 일치하면 해당 시작, 끝 index를 answer에 담아 return

=> 정확성에서 2개 문제 시간 초과, 효율성 테스트 통과 못함

❗️ 오답 원인 분석

• 이중 for문으로 해결할 수 없음 : gems 배열 크기 최대 10만
• Set에 담은 배열을 비교하기보다 각 요소를 count해서 모든 보석의 count > 0 인지 확인하는 것이 더 효율적!
• 이런 문제는 투포인터 알고리즘(슬라이딩 윈도우 알고리즘) 을 이용해 풀 수 있음

🔑 풀이 핵심

*투포인터 알고리즘(슬라이딩 윈도우 알고리즘)

어떤 특정 조건을 만족하는 연속 구간을 구할 때 O(N) 으로 풀 수 있도록 도와주는 알고리즘

• 두 개의 포인터 l(left), r(right)를 가지고 각각을 조건에 따라 증가시켜나가면서 확인하는 방법
• left, right 둘 중 하나라도 범위를 벗어나면 탐색 종료(그러나 본 문제에서는 right만 체크해도 됨)

Map 객체 장점 :

1. size 속성으로 객체 크기를 쉽게 확인 가능
2. 데이터 추가, 삭제 시 일반 Object 객체보다 성능이 좋음.