프로그래머스 - 나머지 한 점

링크: https://programmers.co.kr/learn/courses/18/lessons/1878

문제

코딩 테스트의 데모 문제, 연습 문제로 많이 등장하는 문제입니다.

직사각형을 나타내는 네 개의 꼭짓점 중 세 개의 좌표가 주어졌을 때, 나머지 한 좌표를 구하는 문제죠.

좌표의 범위에 따라 해결 방식이 다를 수 있습니다. 여기서는 좌표의 범위가 10억까지인 프로그래머스 문제의 풀이를 다룹니다. (백준에서는 1000 이하의 정수)

네 점의 x좌표들은 모두 2번씩 등장합니다. 마찬가지로 y좌표들도 2번씩 등장해야하죠. 그럼 x, y 좌표들 중 1번만 등장한 녀석들이 문제의 정답입니다.

이것을 카운팅하는 것이 곧 문제를 해결하는 것인데, 좌표가 10억까지 주어지는 경우라면 해시(Hash)와 같은 적당한 자료구조의 도움이 필요합니다. C++의 경우에는 map이라는 것을 사용하면 됩니다. 자세한 것은 코드에..

코드

	#include <iostream>
	#include <vector>
	#include <map>
	using namespace std;
	typedef map<int, int> mii;
	// 두번 등장하지 않은 수를 찾는다.
	int find(mii& dat){
	for(auto& a : dat){
	if(a.second != 2){
	return a.first;
	}
	}
	// 사실 없는 경우는 없다.
	return -1;
	}
	vector<int> solution(vector<vector<int> > v) {
	mii x, y;
	for(int i=0; i<3; ++i){
	x[v[i][0]]++;
	y[v[i][1]]++;
	}
	vector<int> ans(2);
	ans[0] = find(x);
	ans[1] = find(y);
	return ans;
	}

view raw programmers-나머지-한-점.cpp hosted with ❤ by GitHub

비슷한 문제

• BOJ 3009 - 네 번째 점