11.16

NHN pretest 2차 김칫국을 마시며... 그게 아니더라도 준비는 해야하니까!
python은 언제든 돌아갈 수 있으니, 이제부터는 C++로 준비를 해볼까 한다. (NHN은 코딩테스트를 C,C++,JAVA 로만 볼 수 있었으니까)

C++로 문제 풀 때 https://www.onlinegdb.com/가 좋은 것 같다.

오늘 푼 문제는 2358-평행선 이다. 엄청 어려운 문제는 아니었지만, 단순히 생각하고 풀다가 오답을 받은 문제.

첫 접근

처음에는 이중 for문을 이용하여, 두 점의 좌표를 비교했다. x좌표나 y좌표가 같은 경우에는 x축 혹은 y축과 평행하니까 문제를 풀 수 있다고 생각했다.

그리고 직선을 만드는 거라, 하나의 직선이 만들어 진 후 그 위에 있는 점은 포함을 시키는게 아니더라...

예를 들어 (0,0) , (1,0) 두 점을 선택하여 직선을 만들게 되면, x축 위에 어떤 점이 찍히더라도 새로운 직선으로 추가되지 않는다.

한 번 틀리고나서 같은 좌표가 주어져도 직선을 만들 수 있다는 것을 보고 그 부분을 수정했더니 시간초과 바사삭

map을 이용하여 x와 y좌표가 등장한 횟수만큼 더해준 이후 2번 이상 등장하면 +1 하는 방식으로 문제를 해결했다.

코드

// 2358 평행선

#include<iostream>
#include<vector>
#include<utility>
#include<map>

using namespace std;

int main(){
    vector<pair<int,int>> arr;
    map<int,int> X;
    map<int,int> Y;
    int point_num;
    int x,y;
    int answer = 0;
    
    cin >> point_num;
    
    // 주어진 점들 입력
    for(int i=0;i<point_num;i++){
        cin >>x>>y;
        arr.push_back(make_pair(x,y));
    }
    
    for(int i=0;i<point_num;i++){
        // x좌표
        if(X.find(arr[i].first) == X.end()){
            X.insert(make_pair(arr[i].first,1));
        }else{
            X[arr[i].first]++;
        }
        
        //y좌표
        if(Y.find(arr[i].second) == Y.end()){
            Y.insert(make_pair(arr[i].second,1));
        }else{
            Y[arr[i].second]++;
        }
    }
    
    for(auto it=X.begin();it!=X.end();it++){
        if(it->second >=2){
            answer++;
        }
    }
    
    for(auto it=Y.begin();it!=Y.end();it++){
        if(it->second >=2){
            answer++;
        }
    }
    
    
    cout << answer<<"\n";
    
    return 0;
}

좋은 웹페이지 즐겨찾기