공부방
2차원 배열, 카운팅 정렬 본문
2차원 배열
package test01;
public class Test1_ArrayTest {
public static void main(String[] args) {
int[][] arr = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
int n = arr.length;
int m = arr[0].length;
// 1. 행 우선 순회
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.printf("%3d", arr[i][j]);
}
System.out.println();
}
System.out.println();
// 2. 행 역우선 순회
for (int i = 0; i < n; i++) {
for (int j = m - 1; j >= 0; j--) {
System.out.printf("%3d", arr[i][j]);
}
System.out.println();
}
System.out.println();
// 3. 열 우선 순회
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
System.out.printf("%3d", arr[i][j]);
}
System.out.println();
}
System.out.println();
// 4. 열 역우선 순회
for (int j = 0; j < m; j++) {
for (int i = n - 1; i >= 0; i--) {
System.out.printf("%3d", arr[i][j]);
}
System.out.println();
}
System.out.println();
// 5-1. 지그재그 순회
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
for (int j = 0; j < m; j++) {
System.out.printf("%3d", arr[i][j]);
}
System.out.println();
} else {
for (int j = m - 1; j >= 0; j--) {
System.out.printf("%3d", arr[i][j]);
}
System.out.println();
}
}
System.out.println();
// 5-2. 지그재그 순회
for (int i = 0; i < n; i++) {
if (i % 2 == 0) {
for (int j = 0; j < m; j++) {
System.out.printf("%3d", arr[i][j]);
}
System.out.println();
} else {
for (int j = 0; j < m; j++) {
System.out.printf("%3d", arr[i][m - 1 - j]);
}
System.out.println();
}
}
System.out.println();
// 5-3. 지그재그 순회
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.printf("%3d", arr[i][j + (m - 1 - 2 * j) * (i % 2)]);
}
System.out.println();
}
System.out.println();
}
}
//
1 2 3
4 5 6
7 8 9
3 2 1
6 5 4
9 8 7
1 4 7
2 5 8
3 6 9
7 4 1
8 5 2
9 6 3
1 2 3
6 5 4
7 8 9
1 2 3
6 5 4
7 8 9
1 2 3
6 5 4
7 8 9델타 배열
package test01;
public class Test2_Delta {
public static void main(String[] args) {
int[][] arr = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
int N = 3;
int r = 1;
int c = 1;
int[] dr = { -1, 1, 0, 0 };
int[] dc = { 0, 0, -1, 1 };
//상하좌우
//인덱스
//0-상
//1-하
//2-좌
//3-우
int[][] drc = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
for (int d = 0; d < 4; d++) {//0~3까지 반복을 하며 dr,dc 배열을 더하고 빼며
//원래의 좌표값에서 새로운 옮겨진 좌표들을 찾아줌.
int nr = r + dr[d];
int nc = c + dc[d];
// 경계조건-밖으로 넘어가는 걸 방지
if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
System.out.println(arr[nr][nc]);
}
//경계조건-밖으로 넘어가면 그냥 패스
// if (nr < 0 || nr >= N || nc < 0 || nc >= N)
// continue;
// System.out.println(arr[nr][nc]);
}
//대각선
int[] dr2= {-1,-1,1,1};
int[] dc2= {-1,1,-1,1};
for (int d = 0; d < 4; d++) {//0~3까지 반복을 하며 dr,dc 배열을 더하고 빼며
//원래의 좌표값에서 새로운 옮겨진 좌표들을 찾아줌.
int nr = r + dr2[d];
int nc = c + dc2[d];
//경계조건-밖으로 넘어가는 걸 방지
// if (nr >= 0 && nr < N && nc >= 0 && nc < N) {
// System.out.println(arr[nr][nc]);
// }
//경계조건-밖으로 넘어가면 그냥 패스
if (nr < 0 || nr >= N || nc < 0 || nc >= N)
continue;
System.out.println(arr[nr][nc]);
}
//8방향
//크기가 8인 델타 배열을 만들고
//반복을 8번 돌기
}
}
//
2
8
4
6
1
3
7
9전치 행렬
package test01;
import java.util.Arrays;
public class Test3_TransposedMatrix {
public static void main(String[] args) {
// 전치행렬
int[][] arr = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
int N = 3;
for (int[] a : arr) {
System.out.println(Arrays.toString(a));
}
// 전치행렬
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (i < j) {
int tmp = arr[i][j];
arr[i][j] = arr[j][i];
arr[j][i] = tmp;
}
}
}
System.out.println("----------------------");
for (int[] a : arr) {
System.out.println(Arrays.toString(a));
}
//윗삼각형 영역
// for (int i = 0; i < N; i++) {
// for (int j = i + 1; j < N; j++) {
// int tmp = arr[i][j];
// arr[i][j] = arr[j][i];
// arr[j][i] = tmp;
// }
// }
// System.out.println("----------------------");
// for (int[] a : arr) {
// System.out.println(Arrays.toString(a));
// }
}
}
//
[1, 2, 3]
[4, 5, 6]
[7, 8, 9]
----------------------
[1, 4, 7]
[2, 5, 8]
[3, 6, 9]카운팅 정렬
항목들의 순서를 결정하기 위해 집합에 각 항목이 몇 개씩 있는지 세는 작업을 하여, 선형 시간에 정렬하는 효율적인 알고리즘
- 정수나 정수로 표현할 수 있는 자료에 대해서만 적용 가능
- 각 항목의 발생 회수를 기록하기 위해, 정수 항목으로 인덱스 되는 카운트들의 배열을 사용하기 때문이다.
- 카운트들을 위한 충분한 공간을 할당하려면 집합 내의 가장 큰 정수를 알아야 한다.
- 시간 복잡도: O(n+k)-n은 배열의 길이, k는 정수의 최대값
package test02;
import java.util.Arrays;
public class test5 {
public static void main(String[] args) {
int[] arr = { 5, 2, 4, 1, 2, 3, 3 };
// 1단계
// 주어진 배열 arr에서 최대값을 찾는다.
// 그 수를 이용해서 카운팅 배열을 만든다.
int max = -1;
for (int i = 0; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
System.out.println(max);// 최대값이 뭔지 확인해보자.
// 2단계
// 카운팅 배열
// count[i]:i의 개수
int[] count = new int[max + 1];// 최대값을 찾으면 그 최대값까지 카운팅해줄 수 있는 배열을 만든다.
for (int i = 0; i < arr.length; i++) {
count[arr[i]]++;
}
System.out.println(Arrays.toString(count));// 최대 값까지 몇 번 나왔는지 확인해준다.
// 누적합 배열
// =prefix sum
// prefix[i]=count[0]+count[1]+count[2]+...+count[i];
// suffix[i]=count[i]+count[i+1]+...+count[n-2]+count[n-1];
// 굳이 배열을 하나 더 만들 필요 없긴 함
// int[] prefix=new int[6];
// prefix[0]=count[0];
// for (int i = 1; i <= 5; i++) {
// prefix[i]=prefix[i-1]+count[i];
// }
// 3단계
// count배열을 prefix 배열로
// for (int i = 1; i <= 5; i++) {
// count[i] += count[i - 1];
// }
int[] countSum=new int[count.length];
for (int i = 1; i < count.length; i++) {
countSum[i]+=countSum[i-1]+count[i];
}
System.out.println(Arrays.toString(countSum));
// 4단계
// arr배열을 다시 돌면서
// 새로운 배열의 새로운 좌표에 옮긴다.
//{ 5, 2, 4, 1, 2, 3, 3 }
int[] arr2 = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
arr2[countSum[arr[i]] - 1] = arr[i];
countSum[arr[i]]--;
}
System.out.println(Arrays.toString(countSum));//남은 누적카운팅배열 수
System.out.println(Arrays.toString(arr2));//최종 정렬
}
}
//
5
[0, 1, 2, 2, 1, 1]
[0, 1, 3, 5, 6, 7]
[0, 0, 1, 3, 5, 6]
[1, 2, 2, 3, 3, 4, 5]
'알고리즘/List' Related Articles
more
