unordered_set
-
[프로그래머스] 보석 쇼핑문제 풀이 2020. 9. 28. 15:22
보석 쇼핑 풀이)처음에는인덱스 0부터 ~ 모든 보석을 포함하는 마지막 인덱스를 찾고, 그 안에서 구간을 줄여나가면서 풀었더니틀렸던 문제다.예외 존재) ["DIA","EM","EM","RUB","DIA"] 일경우 answer = [3, 5] output = [1, 4] 가 나옴 그렇다고 2중 포문을 사용해서 구간을 찾기에는 보석 배열이 100,000 크기까지 될 수 있으므로 시간초과가 생긴다. => 투포인터 방법을 사용해서 풀어야 하는 문제이다. unordered_map, 투 포인터 사용 풀이법 1. 먼저 보석의 총 개수를 unordered_map을 이용해서 구한다. 2. left, right 두 개의 인덱스 포인터를 이용해서 가장 짧은 구간을 찾는다. -> left와 right 인덱스를 조건을 생각하며 ..