[백준 3089] 네잎 클로버를 찾아서 (C++)

문제 링크: https://www.acmicpc.net/problem/3089

3089번: 네잎 클로버를 찾아서

1. 주의할 점

- 2차원 배열을 만들 생각 하지말자

- 네잎클로버를 따지 않는다 -> 런타임에러 3번...

- Vector를 Sorting해놓아야 한다 -> 안하면 TLE 발생(LogN에 찾을 수 있는 것을 N에 찾으려고 하기 때문)

 

2. 구현

- X, Y의 범위는 -10만 ~ 10만이므로 입력받는 값에 10만씩을 더한다. 이후, X값에 어떤 Y값들이 있는지 나타내기 위해 Vector CX와 CY를 사용했다.

- 명령을 입력받을 때 마다 그에 맞는 작업을 수행한다.

- 최종 출력은 X - 10만, Y - 10만을 출력한다.

 

#define MAX 100000
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

vector<int> cx[2 * MAX], cy[2 * MAX];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int num, order, x, y, ex = MAX, ey = MAX, ty, tx;

	cin >> num >> order;
	for (int i = 0; i < num; i++) {
		cin >> x >> y;
		cy[y + MAX].push_back(x + MAX);
		cx[x + MAX].push_back(y + MAX);
	}
	for (int i = 0; i < 2 * MAX; i++) {
		if (cy[i].size() > 0)	sort(cy[i].begin(), cy[i].end());
		if (cx[i].size() > 0)	sort(cx[i].begin(), cx[i].end());
	}
	char c;
	for (int i = 0; i < order; i++) {
		cin >> c;
		if (c == 'U') {		//x값은 같다
			ty = 2 * MAX + 1;
			tx = ex;
			for (int j = 0; j < cx[ex].size(); j++) {
				int ny = cx[ex][j];
				if (ny > ey) { 		
					ty = ny;
					break;
				}
			}
			ex = tx; ey = ty;
		}
		else if (c == 'D') {
			ty = 0;
			tx = ex;
			for (int j = cx[ex].size()-1; j >=0; j--) {
				int ny = cx[ex][j];
				if (ny < ey) {		
					ty = ny;
					break;
				}
			}
			ex = tx; ey = ty;
		}
		else if (c == 'L') {
			ty = ey;
			tx = 0;
			for (int j = cy[ey].size()-1; j>=0; j--) {
				int nx = cy[ey][j];
				if (nx < ex) {
					tx = nx;
					break;				
				}
			}
			ex = tx; ey = ty;
		}
		else if (c == 'R') {
			ty = ey;
			tx = 2 * MAX + 1;
			for (int j = 0; j < cy[ey].size(); j++) {
				int nx = cy[ey][j];
				if (nx > ex) {
					tx = nx;
					break;					
				}
			}
			ex = tx; ey = ty;
		}
	}
	cout << ex - MAX << " " << ey - MAX;
	system("pause");
	return 0;
}