목록MMRECT2 (1)

Software Engineering Note

최소, 최대 정사각형 찾기 2

문제: MMRECT2 / 구현 MMRECT1 문제랑 똑같은데 점의 갯수가 최대 20,000 개까지 입력될 수 있다. MMRECT1 처럼알고리즘으로 풀면 TLE를 면치 못하겠다. 해서, 메모리를 좀 이용하기로 했다. 해결전략 1. x좌표가 같은 점들을 한 곳에 모아놓는다. (map)2. 루프를 돌면서 입력된 점을 하나씩 꺼내고, map에서 좌표리스트를 꺼낸다.3. 좌표리스트를 돌면서 다음을 수행 (정사각형의 조건을 생각해보자)- x좌표는 어차피 같으니까 y 차이를 구한다. (=dist)- 좌표 p1, p2에서 같은 방향으로 dist만큼 떨어진 점이 있는지 찾아본다.- 예를 들어, y 값이 2 차이나면 두 점의 왼쪽에 2만큼 떨어진 곳에 점이 있거나, 오른쪽으로 2만큼 떨어진 곳에 점이 있어야한다.4. 정사..
알고리즘/알고스팟 2015. 1. 3. 18:33
이전 Prev 1 Next 다음