SlidingWindow2 2020 카카오 인턴십 문제 ② 2020 카카오 인턴십 #4 보석 쇼핑 map과 two pointer을 사용해 푸는 문제 i부터 j까지 구간에 모든 보석을 가지고 있는가를 판단할 때 map을 사용, 아니라면 j, 맞다면 i를 증가하여 왼쪽에서 오른쪽으로 이동하며 가장 짧은 구간을 구한다. 처음엔 구간 길이에 대한 이분탐색으로 접근했다. 시간초과 났음 더보기 비슷한 문제를 다른 코테에서 본 적 있다. 이 문제의 2차원 버전이었는데,,, 아쉽다 map M; vector solution(vector gems) { vector answer; int N=gems.size(); // Gems for(string g:gems){ auto iter=M.find(g); if(iter==M.end()) M.insert({g,0}); } int G=M.s.. 2021. 5. 10. BOJ11003 최솟값 찾기 www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net i-L+1 ~ i 번 째 수 중 최솟값 출력 덱 이용하기 내 앞의 수가 나보다 크다 ⇒ 그 수는 필요없다. 내 앞의 수가 나보다 작다 ⇒ 내가 나중에 필요할 수도 있다. push는 뒤에서만 해준다. 덱을 앞에서부터 볼 때 읽은 순으로, 값은 오름차순으로 정렬되도록 한다. 1. 범위를 벗어난 값은 pop front 2. 앞의 수 중 나보다 큰 것 pop back * 이때 앞의 수의.. 2021. 1. 12. 이전 1 다음
