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;
}
Author And Source
이 문제에 관하여(11.16), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@inkyu0103/11.16저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)