1. 오늘 학습한 내용
백준 정렬 18870번 문제
2. 알게 된 내용
처음 나의 생각
- 나는 버블정렬 밖에 스스로 구현을 잘 못하니까 버블정렬을 써봐야지..
결과 ) 버블정렬을 쓰니까 시간초과가 떴다 (당연한 결과일 것 같았지만 한번 해봤는데 역시나..!)
해결 ) 그래서 합병정렬을 써보려고 했다. 그러나 나는 합병정렬을 스스로 구현할 수 없어서 다른 분의 코드를 참고하면서 해결하였다.
- 입력값 순서대로 담아져 있는 배열과, 정렬한 배열을 하나하나 비교하면서 같으면 그 인덱스를 출력해봐야지...
결과 ) 이 방법으로 구현하면, 이중반복문+if문을 써서 3중으로 작동해서 시간초과가 떴다.
해결 ) 다른 분의 설명을 참고해보니까 그냥 이 값들의 순위만 구하면 되는 것이니까 중복값을 담지 않는 Map을 이용하면 된다고 한다.
합병정렬(병합정렬)의 코드
배열을 { (left) ~ (mid) }, { (mid+1) ~ (right) } 두 가지 파트로 나눈다.
그 후 a[왼쪽 파트에서 가장 앞 인덱스] 값과 a[오른쪽에서 가장 앞 인덱스] 값을 비교해서 더 작은 값을 sorted 배열에 하나씩 넣는다.
만약 한 파트가 다 끝나면, 나머지 파트의 값들을 sorted 배열에 넣는다.
이 과정을 재귀를 이용해서 부분리스트가 1개일 때까지 계속 쪼개면서 작동하도록 한다.
public class Merge_Sort {
private static int[] sorted; // 합치는 과정에서 정렬하여 원소를 담을 임시배열
public static void merge_sort(int[] a) {
sorted = new int[a.length];
merge_sort(a, 0, a.length - 1);
sorted = null;
}
// Top-Down 방식 구현
private static void merge_sort(int[] a, int left, int right) {
/*
* left==right 즉, 부분리스트가 1개의 원소만 갖고있는경우
* 더이상 쪼갤 수 없으므로 return한다.
*/
if(left == right) return;
int mid = (left + right) / 2; // 절반 위치
merge_sort(a, left, mid); // 절반 중 왼쪽 부분리스트(left ~ mid)
merge_sort(a, mid + 1, right); // 절반 중 오른쪽 부분리스트(mid+1 ~ right)
merge(a, left, mid, right); // 병합작업
}
/**
* 합칠 부분리스트는 a배열의 left ~ right 까지이다.
*
* @param a 정렬할 배열
* @param left 배열의 시작점
* @param mid 배열의 중간점
* @param right 배열의 끝 점
*/
private static void merge(int[] a, int left, int mid, int right) {
int l = left; // 왼쪽 부분리스트 시작점
int r = mid + 1; // 오른쪽 부분리스트의 시작점
int idx = left; // 채워넣을 배열의 인덱스
while(l <= mid && r <= right) {
/*
* 왼쪽 부분리스트 l번째 원소가 오른쪽 부분리스트 r번째 원소보다 작거나 같을 경우
* 왼쪽의 l번째 원소를 새 배열에 넣고 l과 idx를 1 증가시킨다.
*/
if(a[l] <= a[r]) {
sorted[idx] = a[l];
idx++;
l++;
}
/*
* 오른쪽 부분리스트 r번째 원소가 왼쪽 부분리스트 l번째 원소보다 작거나 같을 경우
* 오른쪽의 r번째 원소를 새 배열에 넣고 r과 idx를 1 증가시킨다.
*/
else {
sorted[idx] = a[r];
idx++;
r++;
}
}
/*
* 왼쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (l > mid)
* = 오른쪽 부분리스트 원소가 아직 남아있을 경우
* 오른쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다.
*/
if(l > mid) {
while(r <= right) {
sorted[idx] = a[r];
idx++;
r++;
}
}
/*
* 오른쪽 부분리스트가 먼저 모두 새 배열에 채워졌을 경우 (r > right)
* = 왼쪽 부분리스트 원소가 아직 남아있을 경우
* 왼쪽 부분리스트의 나머지 원소들을 새 배열에 채워준다.
*/
else {
while(l <= mid) {
sorted[idx] = a[l];
idx++;
l++;
}
}
/*
* 정렬된 새 배열을 기존의 배열에 복사하여 옮겨준다.
*/
for(int i = left; i <= right; i++) {
a[i] = sorted[i];
}
}
}에서
출처 : https://st-lab.tistory.com/233
Map과 HashMap
Map : 중복되는 값은 담지 않는 자료구조
HashMap : Map 인터페이스를 구현한 것으로 해싱을 사용해서 많은 양의 데이터를 검색하는 데 있어서 뛰어난 성능을 보임
key와 value로 이루어져 있어서 key로 값을 찾는다
- 선언
HashMap<Integer, Integer> rankingMap = new HashMap<Integer, Integer>();-
메서드
- put(key, value) : 값 추가
- containskey(key) : 해당 키를 가진 값이 있는지 여부를 알려줌
- get(key) : key값에 해당하는 value 값을 가져옴
출처 :
https://coding-factory.tistory.com/556
https://st-lab.tistory.com/279
기록하자