✅ 한 것들

• 프로그래머스
• 면접 대비 : 질문 시뮬, CS 복습

⚔️ 프로그래머스

캠핑

int solution(int n, vector<vector<int>> data) {
    int answer = 0;
    
    // 두 성분의 순위가 붙어있어야 한다
    // x에 대해 정렬한 data를 순회하면서 map에 인덱스를 기록
    // for문 2개로 원본 data 순회하면서 조합에 대해 두 성분의 인덱스 사이에 있는 쐐기 검증
    vector<pii> xSortData;
    for(vi d : data) xSortData.push_back({d[0],d[1]});
    sort(xSortData.begin(),xSortData.end());
    map<pii,int> rank;
    
    int x, y;
    for(int i=0; i<n; i++) { rank[xSortData[i]] = i; }    
    int idx1, idx2, idxl, idxr;
    int x1,y1,x2,y2,xk,yk;
    for(int i=0; i<n; i++)
    {
        idx1 = rank[{data[i][0],data[i][1]}];
        tie(x1,y1) = xSortData[idx1]; // 첫번째 쐐기
        for(int j=i+1; j<n; j++)
        {
            idx2 = rank[{data[j][0],data[j][1]}];
            tie(x2,y2) = xSortData[idx2]; // 두번째 쐐기
            if(x1==x2 || y1==y2) continue; // 면이 아니라 선이라면 넘어간다
                
            idxl = (idx1 < idx2) ? idx1 : idx2;
            idxr = (idx1 < idx2) ? idx2 : idx1;            
            bool canBeAnswer = true;
            for(int k=idxl+1; k<idxr; k++)
            {
                tie(xk,yk) = xSortData[k];
                if(xk==x1 || xk==x2) continue; // 경계에 있다면 넘어간다
                if((y1<yk && yk<y2)||(y1>yk && yk>y2))
                {
                    // x는 이미 사이에 있다. y까지 사이에 있다면 박으면 안됨
                    canBeAnswer=false; 
                    break; 
                }
            }
            if(!canBeAnswer) continue;
            answer++;
        }
    }
    
    return answer;
}

시간 복잡도 상으로 n^3이니 사실상 틀렸지만, 통과는 됐다.

• data를 바로 sort하고 x 인덱스에 대해 nC2를 하면 됐는데, 이전 로직에서 넘어오다보니 코드가 지저분해졌다.
• 로직을 전환하면 이전 코드 재사용과는 별개로, 0부터 생각하는 버릇 들이기.

범위가 너무 넓어서 좌표 안에 있나 없나 미리 기록해두는 건 불가능하다고 생각했는데,
좌표 압축 해버리면 5000으로 줄어드니 충분히 가능했다.

그 결과

https://blog.naver.com/jaejin_me/221144318795

이렇게 푸는게 정석이었다.