[Programmers] 보석 쇼핑

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/67258

프로그래머스

투 포인터 알고리즘을 이용해 푸는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. 보석의 종류 개수와 주어진 진열대 크기를 구해줍니다.

2. 정답이 아닌 케이스는 주어지지 않으므로 answer를 최대 범위인 1 ~ 진열대 크기로 초기화하고 투 포인터 알고리즘을 적용할 것이므로 start, end 변수를 선언한 뒤 각각을 0으로 초기화해줍니다.

3. set과 map을 선언하여 현재 구간 내 존재하는 보석의 종류를 set에 각각의 보석의 개수를 map에 저장해줍니다.

4. end가 진열대 끝까지 갈 때까지 투 포인터 알고리즘을 진행합니다.

4.1 주어진 보석의 종류의 개수와 3번에서 선언한 set의 크기가 같다면 조건에 부합하므로 answer를 업데이트해주고 start를 앞당기면서 범위를 좁힙니다.

4.2 주어진 보석의 종류의 개수보다 3번에서 선언한 set의 크기가 작다면 조건에 부합하지 않으므로 end를 한 칸 뒤로 보내면서 범위를 넓힙니다.

5. 4번을 모두 진행했을 때 구해진 answer를 반환해줍니다.

 

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~