시작
백준 알고리즘 문제 분류에서 링크드 리스트 태그서 이름이 가장 맘에 드는 개구리 공주를 선택하여 도전하였습니다. 간단한 알고리즘 문제부터 풀고 도전했어야 하는데 개구리 공주에 끌려 먼저 풀게 되었습니다. 최적의 풀이는아니지만 필자가 해결한 방법을 소개하고자 합니다.
풀이
1. N 개의 점의 수를 필터하기
A, B, C, D 의 대각선 방향으로 이동하는 경우만 존재하므로 점 (X, Y ) 기준으로 상하좌우 방향으로는 갈 수 없습니다. 첫번째 점의 위치와 비교해 (X+Y % 2) 의 결과가 첫번째 점의 결과랑 다른 경우에는 절대로 그 점에 개구리가 도달할 경우는 없기 때문에 N개의 점 좌표를 저장하지 않고 점의 개수를 줄일수 있습니다.
2. 점 데이터 저장하기 (X+Y, X-Y 비교)
점은 대각선으로만 이동하기 때문에 갈 수 있는 곳이 한정적이라고 했습니다. 특정한 점 (5, 6)이 이동할 수 있는 경우를 그려보고 점들 사이에 규칙있는 생각해보았습니다. 대각선으로 이동한다는 특성때문에 점은 X+Y, X-Y 값이 같은 곳으로만 이동할 수 있다는 규칙을 찾았습니다.
이동 방향이 A, D 인 경우는 X-Y 가 같은 점들을 비교하면 되고 B, C 인 경우는 X+Y 가 같은 점들을 비교하면 됩니다. 다음 점을 찾아가는 비교 로직을 정리해 보았습니다.
- 첫번째 점(시작점)과 방향이 주어진다.
- 전체 점들 중에서 첫번째 점(시작점)이 갈 수 있는 점들의 리스트를 구한다. (X+Y, X-Y 값으로 비교)
- 리스트 중에서 가장 가까운 점을 가져온다. (X 좌표 or Y좌표 어느 것으로도 비교하여도 상관없음)
- 점이 없는 경우 다음 방향으로 진행한다.
N개의 점에서 해당 조건이 맞는 점들을 가져오는 경우에는 O(n)이 걸리기 때문에 비효율적이라고 생각했습니다. 데이터를 집어넣을때 X+Y, X-Y 으로 인덱싱할 수 있는 자료구조를 생각했습니다. 두 정보를 모두 인덱싱할 수 있는 방법은 도저히 생각이 나지 않아서 X+Y 인덱싱 HashMap, X-Y 인덱싱 HashMap 두 개를 만들었습니다. 이렇게 두 개의 자료구조를 만들면서 점을 삭제할 때 나타나는 무결성의 문제를 코드로 직접 해결해야 했습니다. 좋은 방법은 아니지만 더 이상 생각나지 않았습니다.
코드
위의 로직으로 해결한 코드를 공유합니다. JAVA로 작성하였습니다. 더 좋은 해결 방법이 있다면 피드백 언제든지 환영합니다 ~~
import java.util.HashMap;
import java.util.Scanner;
import java.util.TreeSet;
class Point implements Comparable<Point> {
// 0 ≤ X, Y ≤ 1,000,000,000 이므로 long Type를 사용
public long x;
public long y;
public Point(long firstX, long firstY) {
this.x = firstX;
this.y = firstY;
}
@Override
public int compareTo(Point o) {
if (this.x > o.x) return 1;
else if(this.x == o.x) return 0;
else return -1;
}
}
public class backjoon_2983 {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long loopSize= scanner.nextInt();
long jump = scanner.nextInt();
String str = scanner.next();
char[] directions = str.toCharArray();
long firstX = scanner.nextInt();
long firstY = scanner.nextInt();
long filter = (firstX + firstY) % 2;
HashMap<Long, TreeSet<Point>> sumMap = new HashMap<Long, TreeSet<Point>>();
HashMap<Long, TreeSet<Point>> diffMap = new HashMap<Long, TreeSet<Point>>();
for (int i = 0; i < loopSize-1; i++) {
long x = scanner.nextInt();
long y = scanner.nextInt();
if ((x+y)%2 == filter) {
Point newPoint = new Point(x,y);
TreeSet<Point> sumList = sumMap.get(x+y);
if (sumList == null) {
sumList = new TreeSet<Point>();
}
sumList.add(newPoint);
sumMap.put(x+y, sumList);
TreeSet<Point> diffList = diffMap.get(x-y);
if (diffList == null) {
diffList = new TreeSet<Point>();
}
diffList.add(newPoint);
diffMap.put(x-y, diffList);
}
}
long loopX = firstX;
long loopY = firstY;
for (char ch : directions) {
long key = (ch == 'A' || ch == 'D') ? loopX-loopY : loopX+loopY;
TreeSet<Point> vlist = (ch == 'A' || ch == 'D') ? diffMap.get(key) : sumMap.get(key);
if (vlist == null || vlist.size() == 0) {
continue;
} else {
boolean isXAdd = (ch == 'A' || ch == 'B') ? true : false;
Point exPoint= new Point(loopX, loopY);
Point hitPoint = (isXAdd)
? vlist.higher(exPoint)
: vlist.lower(exPoint);
if (hitPoint == null) {
continue;
}
loopX = hitPoint.x;
loopY = hitPoint.y;
vlist.remove(hitPoint);
if (vlist.size() == 0) {
vlist = null;
}
if (ch == 'A' || ch == 'D') {
diffMap.put(key, vlist);
TreeSet<Point> dlist = sumMap.get(hitPoint.x+hitPoint.y);
dlist.remove(hitPoint);
if (dlist == null || dlist.size() == 0) {
dlist = null;
}
sumMap.put(hitPoint.x+hitPoint.y, dlist);
} else {
sumMap.put(key, vlist);
TreeSet<Point> dlist = diffMap.get(hitPoint.x-hitPoint.y);
dlist.remove(hitPoint);
if (dlist == null || dlist.size() == 0) {
dlist = null;
}
diffMap.put(hitPoint.x-hitPoint.y, dlist);
}
}
}
System.out.println(loopX +" "+loopY);
}
}
마침
알고리즘 문제를 풀기전에 언어의 선택의 중요함을 느낄 수 있었습니다. 백준 알고리즘 맞은 사람 내역에서 걸린 시간별로 데이터를 볼 수 있는데 온통 C 가 점령하고 있었습니다. 확실히 시스템에 가까운 저수준의 언어일 수록 속도면에서 차이가 있었습니다. 이문제만 놓고 본다면 시간으로는 JAVA 제일 빠른속도와 C++가 가장 빠른 속도 20배정도 차이가 나는 것을 확인할 수 있었습니다. 알고리즘 대회 같은 경우에는 속도가 확실한 C++ 로 작성하는 것이 맞다고 생각합니다. 대회까지 생각하시는 분들은 언어를 익힐 시간이 되신다면 C++로 작성하는 것을 추천합니다.
또한 JAVA 코딩을 작성하는데 어려움이 있었습니다. 6개월 정도 Java 코드 작성을 안해보았고 그동안 동적 타입 언어를 주로 사용하였기에 변수 타입 지정하는게 귀찮았고 Java Collections 라이브러리에서 원하는 자료구조를 찾는데 꽤 걸렸습니다. 그리고 어색한 자바를 위해 자동 완성이 필요했기에 IDE 도 새로 설치하였습니다. 문제는 해결했지만 개운하지 않는 느낌이 드는 문제였습니다. 어쨌든 문제를 해결했으니 Peace Out!! 🙂