슬라이딩 윈도우 초기검사, map iterator 선언

문제 링크입니다 : 2020 카카오 여름인턴 3번 문제

 

 

슬라이딩 문제 + map 문제가 나왔다.

 

유형은 거의 2019 카카오 개발자 겨울 인턴쉽 - 징검다리 건너기와 거의 같았다.

 

시간 압박을 받으면서 문제를 풀어서 실수를 많이 했다.

 

같은 실수로 인한 다시 시간 낭비를 하지 않기위해서 이 여기에 남긴다.

 

슬라이딩 윈도우를 설정해서 간격을 최초로 잡으면 잡은 간격에 대해서도

 

최소 간격이 되는지 살펴보자. 

 

// 2019 카카오 개발자 겨울 인턴십
// 징검다리 건너기

#include <string>
#include <vector>
#include <map>
#define INF 987654321

using namespace std;

int solution(vector<int> stones, int k) {
    int answer = 0;
    
    multimap<int, int> m;
    multimap<int, int>::iterator iter;
    
    // 최초 구간잡기
    for(int i = 0; i < k; i++) {
        m.insert({stones[i], -i});
    }

    int min = INF;
    iter = m.end();
    int max = (*--iter).first;    
    
    
    // 최초 구간에 대해서 min 확인
    if(min > max) min = max;
    
    // 슬라이딩 윈도우 움직이기
    for(int i = k; i < stones.size(); i++) {
    	// 원소 하나 더하고 min 조건이 되도록 과정 수행
        iter = m.find(stones[i - k]);
        m.erase(iter);
        m.insert({stones[i], -i});
        
        iter = m.end();
        int max = (*--iter).first;
       
       	// min 체크
        if(min > max) min = max;
    }
    
    answer = min;
    
    
    return answer;
}

 

// 1. 최초 구간 만들기
for (...) {
}

// 2. 최초 구간에 대한 min조건 확인하기
if(...) {
	min = ...;
}

// 3. 윈도우 움직이기
for (...) {
	// 4. 하나 더해주고, min 조건이 되는 과정 수행
    
	// 5. min인지 확인
	if(...) {
		min = ...;
	}
}

 

 

그리고 map을 사용하면 습관적으로 iterator도 선언해두자. 분명히 쓸 일이 있다.

 

map<string, int> m;
map<string, int>::iterator iter;

 

map은 key는 오름차순으로 자동정렬된다.

multimap의 경우, key가 같으면 value는 내림차순으로 자동 정렬된다.

 

 

 

 

개발 환경 : vscode

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