투포인터
-
[프로그래머스] 쿠키 구입문제 풀이 2020. 9. 30. 17:37
쿠키구입 문제) https://programmers.co.kr/learn/courses/30/lessons/49995 풀이)투포인터를 이용해서 푼 문제이다. 과정1. for문을 통해 인덱스 0 ~ cookie.size() - 2 까지 차례로 시작 인덱스 start 로 정한다. 1.1. 시작인덱스 start + 1 을 마지막 인덱스 end 로 둔다. 1.2. (0 ~ 시작 인덱스 start) / (마지막 인덱스 end ~ cookie.size() - 1) 범위로 나눠 start와 end 두 인덱스 포인터를 이동시키며 두 쿠기 구간의 합을 비교한다. *start 포인터는 왼쪽으로 이동, end 포인터는 오른쪽으로 이동한다. *오른쪽 구간의 합이 크면, 왼쪽 구간을 늘린다 = start 포인터를 한칸 왼쪽으로..
-
[프로그래머스] 보석 쇼핑문제 풀이 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 인덱스를 조건을 생각하며 ..