Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
Tags
- mfc
- Django REST Android
- android push
- Django REST
- dart
- flutter firestore
- UWP
- Django REST framework
- 안드로이드 구글맵
- Flutter TextField
- RxJava
- NDK
- 코틀린
- RxAndroid
- Rxjava2
- livedata
- 안드로이드
- Android
- C++
- C
- Python
- Java
- android architecture component
- 프로그래머스
- C/C++
- 알고리즘
- Android P
- FLUTTER
- Kotlin
- kodility
Archives
- Today
- Total
개발하는 두더지
좌표 압축 알고리즘 본문
좌표 압축 알고리즘 언제사용할까?
순위가 중요한 알고리즘에서 입력값의 개수보다 입력값의 범위가 클때 사용한다.
예를 들면 캠핑 문제에 적용할 수 있다. ( 프로그래머스 카카오 캠핑 문제 풀러가기 )
문제에서 좌표는 0 이상 2^31 이하의 값을 가질 수 있지만 최대 입력값은 5000이다.
문제의 특성상 대각에 위치한 두 좌표를 이용해 직사각형을 만들고 그 직사각형안에 또 다른 좌표가 있는지 확인해야 한다.
아래와 같은 입력값이 있다고 하자.
int pin[][] = new int[][]{{0,0}, {1,1}, {0,2}, {2,0}, {0,3}, {3,2}, {1,4}, {4,4}, {100, 50}, {150, 30}};
0,0 ~ 4,4 사이는 1칸씩 차이라 공간적인 문제가 없지만
0,0 ~ 150,30 을 비교하기 위해서는 150 * 30의 공간을 탐색해야 한다.
0,0 ~ 2^31, 2^31 라면 2^31 * 2^31의 공간을 탐색한다.
좌표가 공간내에 많이 차지한다면 필요한 검색이겠지만 앞부분에 몰려있다면 나머지 부분은 불필요한 공간 탐색이다.
좌표 압축을 통해
0,0 ~ 150,30 -> 0,0 ~ 6,5 를 탐색하게 된다면 시간적, 공간적으로 상당히 효율적이다.
소스
package com.example.lib;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
public class myClass {
public int solution(int n, int[][] data) {
int answer = 0;
for(int i = 0; i < data.length; i++) {
System.out.println(Arrays.toString(data[i]));
}
// 2개의 ArrayList에 x, y 좌표값을 담음
ArrayList<Integer> xList = new ArrayList<>();
ArrayList<Integer> yList = new ArrayList<>();
for(int i = 0; i < n; i++) {
xList.add(data[i][0]);
yList.add(data[i][1]);
}
// x, y 좌표 중복제거
ArrayList<Integer> uniqueXList = new ArrayList<>(new HashSet<>(xList));
ArrayList<Integer> uniqueYList = new ArrayList<>(new HashSet<>(yList));
// 오름차순 정렬
Collections.sort(uniqueXList);
Collections.sort(uniqueYList);
for(int i = 0; i < n; i++) {
int x = uniqueXList.indexOf(new Integer(data[i][0]));
int y = uniqueYList.indexOf(new Integer(data[i][1]));
data[i][0] = x;
data[i][1] = y;
}
System.out.println();
for(int i = 0; i < data.length; i++) {
System.out.println(Arrays.toString(data[i]));
}
return answer;
}
public static void main(String[] args) {
myClass mc = new myClass();
int pin[][] = new int[][]{{0,0}, {1,1}, {0,2}, {2,0}, {0,3}, {3,2}, {1,4}, {4,4}, {100, 50}, {150, 30}};
System.out.println(mc.solution(pin.length, pin));
}
}
결과
# 좌표압축 전
[0, 0]
[1, 1]
[0, 2]
[2, 0]
[0, 3]
[3, 2]
[1, 4]
[4, 4]
[100, 50]
[150, 30]
# 좌표압축 후
[0, 0]
[1, 1]
[0, 2]
[2, 0]
[0, 3]
[3, 2]
[1, 4]
[4, 4]
[5, 6]
[6, 5]
참고
'알고리즘' 카테고리의 다른 글
[리트코드 94] Binary Tree Inorder Traversal (0) | 2018.09.15 |
---|---|
[프로그래머스] 행렬의 곱셈 (0) | 2018.04.20 |
[HackerRank] Climbing the Leaderboard 알고리즘 풀이 (0) | 2018.04.14 |
삽입정렬, 선택정렬, 버블정렬 시간복잡도 O(n^2) 정렬 알고리즘 (0) | 2018.04.10 |
[프로그래머스] 최소값 만들기 - Level 2 (0) | 2018.04.10 |
Comments