2019 카카오 개발자 겨울 인턴십 문제 ②

 

2019 카카오 개발자 겨울 인턴십

 

 

 

#4 징검다리 건너기

오래 고민하고 겨우 푼 다음 정확성 효율성 다 발리고 질문하기 참고해 이분탐색임을 깨달음......

아효 이렇게 간단히 풀리는 것을

 무려 스택을 이용해 풀어봤지만 효율성은 둘째치고 정확성이 해결되지 않앗음 흠

    int l=1, r=INF;
    int mid=(l+r+1)>>1, cnt=0;
    while(l<r){
        bool ava=true;
        cnt=0;
        for(int s:stones){
            if(s>=mid) cnt=0;
            else {
                cnt++;
                if(cnt>=k) { ava=false; break; }
            }
        }   
        if(ava) l=mid;
        else r=mid-1;
        mid=(l+r+1)>>1;
    }
    answer=mid;

 

 

 

#5 호텔 방 배정

disjoint set으로 풀었는데 수의 범위때문에 hash한 번 해줬다.

처음엔 새로운 숫자에 대해 {인덱스,숫자}를 par에 추가하는 방식으로 하려했지만

그렇게 하면 par이 정렬이 안되고 union하기 굉장히 어려워졌다.

par을 오름차순으로 관리하기 위해 하나의 인덱스(p)에 대해 min값(mn)과 max값(mx)을 저장하는 구조체로 정의함

오히려 4번문제보다 훨씬 빨리 감 잡고 품

typedef pair<int,long long> pil;
bool sortR(pil A, pil B){
    return A.second<B.second;
}
bool originalR(pil A, pil B){
    return A.first<B.first;
}
vector<pil> R;

struct node{
    int p;
    long long mn, mx;
};
vector<node> par; 
int find_(int n){
    if(par[n].p==n) return n;
    par[n].p=find_(par[n].p);
    return par[n].p;
}
vector<long long> solution(long long k, vector<long long> room_number) {
    vector<long long> answer;
    
    // make R & par
    int N=room_number.size();
    for(int i=0;i<N;++i) R.push_back({i,room_number[i]});
    sort(R.begin(),R.end(),sortR);
    int j=0;
    par.push_back({0,R[0].second,R[0].second}); R[0].second=0; 
    for(int i=1;i<N;++i){
        if(R[i].second==par.back().mn) R[i].second=j;
        else j++, par.push_back({j,R[i].second,R[i].second}), R[i].second=j;
    }
    sort(R.begin(),R.end(),originalR);
    
    // Union Find
    for(pil r:R){
        int idx=find_(r.second);
        long long room=par[idx].mx;
        answer.push_back(room);
        
        room++;
        if(idx<par.size()-1 && par[idx+1].mn==room) par[idx].p=find_(par[idx+1].p);
        else par[idx].mx++;
    }
    
    return answer;
}