[20121008] 8일차(정렬, 석차알고리즘, 배열의 배열, 마방진, 만년달력(요일구하기))

정렬(Sort)

1. 배열 요소에 일정한 순서를 부여하는 것.

임의의 숫자가 여러개 존재하는 경우 크기순으로 다시 배열한다.
원본 배열 int[] arr = {4, 2, 7, 9, 1, 3, 5, 6, 8, 0};
정렬후 결과 int[] arr = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};

2. 정렬 알고리즘 - 버블, 선택, 삽입, 쉘, 퀵

1회전 ------------------------------------------------

- 항목1과 항목2를 비교 -> 4, 2
- 작은 값에 항목1에 배치. 큰 값을 항목2에 배치 -> 2, 4
- 항목2와 항목3을 비교 -> 4, 7
- 작은 값에 항목2에 배치. 큰 값을 항목3에 배치 -> 4, 7
- 위와 같은 방법으로 항목 두 개씩 비교 및 바꿔치기를 반복 실행.- 가장 큰 값이 가장 끝에 배치된다. -> 9

2회전 ------------------------------------------------

- 가장 끝에 있는 값을 제외하고 나머지에 대해서 1회전과 같은 방법 사용.
- 끝에서 두 번째에 두번째로 큰 값이 배치된다. -> 8

3회전 ------------------------------------------------

- 2회전 상황을 반복한다.
- 끝에서 세 번째에 세번째로 큰 값이 배치된다. -> 7

....

9회전 ------------------------------------------------

- 마지막 숫자 2개를 정렬. -> 0, 1

=> 정렬 완료.(회전수는 (n - 1)회)

//오름차순
package com.test;
public class Sample24 {

public static void main(String[] args) {
int[] arr = {4, 2, 7, 9, 1, 3, 5, 6, 8, 0};

//원본 배열 출력
for (int a= 0; a<arr.length; a++) {
System.out.printf("%d ", arr[a]);
}
System.out.println();

//정렬 알고리즘을 구현(오름차순 asc)
for (int n=1; n<(arr.length) ; n++) { // 1회전에서 9회전
for (int i=0; i < (arr.length-n); i++) { // 1회전
if (arr[i]>arr[(i+1)]) {    // 항목1과 항목2
int temp = arr[i];  // 4 -> temp
arr[i] = arr[(i+1)];    // 2
arr[(i+1)] = temp;      // 4
//4, 2 -> 2, 4
}
}
}

//정렬된 이후의 배열 출력
for (int a= 0; a<arr.length; a++) {
System.out.printf("%d ", arr[a]);
}
System.out.println();
}
}

//내림차순
package com.test;
public class Sample25 {

public static void main(String[] args) {
int[] arr = {4, 2, 7, 9, 1, 3, 5, 6, 8, 0};

//원본 배열 출력
for (int a= 0; a<arr.length; a++) {
System.out.printf("%d ", arr[a]);
}
System.out.println();

//정렬 알고리즘을 구현(내림차순 Desc)
for (int n=1; n<(arr.length) ; n++) { // 1회전에서 9회전
for (int i=0; i < (arr.length-n); i++) { // 1회전
if (arr[i]<arr[(i+1)]) {    // 항목1과 항목2
int temp = arr[i];  // 4 -> temp
arr[i] = arr[(i+1)];    // 4
arr[(i+1)] = temp;      // 2
//2, 4 -> 4, 2
}
}
}

//정렬된 이후의 배열 출력
for (int a= 0; a<arr.length; a++) {
System.out.printf("%d ", arr[a]);
}
System.out.println();
}
}

---

문제) 외부에서 임의의 여러개의 숫자를 입력받고 정렬해서 출력.
실행 예)
갯수지정(2~10)?5
숫자 입력(1)?
숫자 입력(2)?
숫자 입력(3)?
숫자 입력(4)?
숫자 입력(5)?
원본:
정렬:

package com.test;
import java.util.Scanner;

public class Sample26 {
public static void main(String[] args) {

//입력
Scanner sc = new Scanner(System.in);
System.out.print("갯수지정(2~10)?");
int size = sc.nextInt();

int[] data = new int[size];

for(int i=0; i<size; i++){
System.out.printf("숫자 입력(%d)?", (i+1));
data[i] = sc.nextInt();
}

//처리 (원본도 출력해야 하므로 원본 처리)
StringBuilder sb = new StringBuilder();
sb.append("원본 : ");
for(int i=0; i<size; i++){
sb.append(String.format("%d ", data[i]));
}
sb.append(String.format("%n"));

//처리 (정렬)
for (int n=1; n<=size-1; n++){
for (int a=0; a<data.length-n; a++) {
if (data[a]>data[(a+1)]) {
int temp = data[a];
data[a] = data[(a+1)];
data[a+1] = temp;
}
}
}

// 처리 (정렬된 배열을 스트링으로 저장)
sb.append("정렬 : ");
for(int i=0; i<size; i++){
sb.append(String.format("%d ", data[i]));
}
sb.append(String.format("%n"));

//출력
System.out.println(sb.toString());
}
}

---

문제)여러명의 성적을 입력 받고, 점수가 높은 순으로 등수 부여해서 출력.
배열, 정렬 알고리즘 이용.
실행 예)
인원수(2~10)?5
이름 점수(1)?kim 80
이름 점수(2)?park 90
이름 점수(3)?choi 100
이름 점수(4)?hong 70
이름 점수(5)?kang 60
-----------------------
1등 choi 100
2등 park 90
3등 kim 80
4등 hong 70
5등 kang 60

package com.test;
import java.util.Scanner;

public class Sample27 {
public static void main(String[] args) {

//입력
Scanner sc = new Scanner(System.in);
System.out.print("인원수(2~10)?");
int size = sc.nextInt();

//배열(인원수) 생성
String[] name = new String[size];
int[] score = new int[size];

//배열 데이터 입력 및 스트링 변수(StringBuilder이용) 선언
StringBuilder tot = new StringBuilder(); //최종출력을 위한 tot 변수
for (int i=0; i<size ; i++){
System.out.printf("이름 점수(%d)", (i+1));
name[i] = sc.next();
score[i] = sc.nextInt();
}
System.out.println("---------------------");

//처리(등수정렬)
// name[i] 와 score[i]가 같은 조건으로 계속 비교해야함
for(int n=1; n<=size-1; n++){
for (int i=0; i<(score.length-n); i++) {
if (score[i] < score [(i+1)]) {
int temp_score = score[i];
score[i] = score [(i+1)];
score[(i+1)] = temp_score;
String temp_name = name[i];
name[i] = name[(i+1)];
name[(i+1)] = temp_name;
}
}
}

//tot 변수 처리(출력용)
for (int i=0; i<size ; i++){
tot.append(String.format("%d등 %s %d%n", (i+1), name[i], score[i]));
}

//최종출력
System.out.printf("%s", tot);
System.out.println("---------------------");
}
}

---

문제)여러명의 성적을 입력 받고, 점수가 높은 순으로 등수 부여해서 출력.
배열, 석차 알고리즘 이용.
실행 예)
인원수(2~10)?5
이름 점수(1)?kim 80
이름 점수(2)?park 90
이름 점수(3)?choi 100
이름 점수(4)?hong 70
이름 점수(5)?kang 60
-----------------------
kim 80 3등
park 90 2등
choi 100 1등
hong 70 4등
kang 60 5등
-----------------------

package com.test;
import java.util.Scanner;

public class Sample28 {
public static void main(String[] args) {

//입력
Scanner sc = new Scanner(System.in);
System.out.print("인원수(2~10)?");
int size = sc.nextInt();

//배열(인원수) 생성
String[] name = new String[size];
int[] score = new int[size];

//배열 데이터 입력 및 스트링 변수(StringBuilder이용) 선언
StringBuilder tot = new StringBuilder(); //최종출력을 위한 tot 변수
for (int i=0; i<size ; i++){
System.out.printf("이름 점수(%d)", (i+1));
name[i] = sc.next();
score[i] = sc.nextInt();
}
System.out.println("---------------------");

//처리(석차 알고리즘)
//ranks 배열의 초기값을 0에서 1로 변경한뒤 score배열을 하나씩 비교해서 높은게 있으면 ranks 배열값을 +1 하는 식으로 해결
int[] ranks = new int[size];
for(int i=0; i<ranks.length; i++){ // 초기값변경
ranks[i] = 1;
}

for(int n=0; n<ranks.length; n++){ // 1~최종회전
for (int m=0; m<ranks.length; m++){ // 1회전
if (n == m) { // score[0]은 score[0]과 비교하지 않음
continue;
}
if (score[n] < score[m]) {
ranks[n]++;
}
}
}

//tot 변수 처리(출력용)
for (int i=0; i<size ; i++){
tot.append(String.format("%s %d %d등%n", name[i], score[i], ranks[i]));
}

//최종출력
System.out.printf("%s", tot);
System.out.println("---------------------");
}
}

---

배열의 배열 (다차원 배열)

1. 1차원 배열 여러개를 조합시켜서 사용하는 배열.
2. 선언
자료형[][] 변수 = new 자료형[크기1][크기2]; 
자료형[인덱스1][인덱스2] = 값;
자료형[][] 변수 = {{값1, 값2, ...}, {값, 값, ...}, {값, 값, ...} ,...};

예를 들어,
int[][] arr = new int[2][3];
arr[0][0] = 0;
arr[0][1] = 0;
arr[0][2] = 0;
arr[1][0] = 0;
arr[1][1] = 0;
arr[1][2] = 0;

for (int a=0; a<arr.length; a++) {  //arr.length는 2
for (int b=0; b<arr[a].length; b++){ //arr[a].length는 3
arr[a][b] = 0;
}
}

for (int a=0; a<arr.length; a++) {  //arr.length는 2
for (int b=0; b<arr[a].length; b++){ //arr[a].length는 3
System.out.printf("%d ", arr[a][b]); // 배열의 배열
}
System.out.println();
}

문제) 아래와 같은 형태의 숫자 출력이 되도록 배열의 배열 지정.
 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

package com.test;
public class Sample29 {
public static void main(String[] args) {

//배열 선언
int[][] arr = new int[5][5];

//초기값 지정
for (int a=0, c=0; a<arr.length; a++) {  //arr.length는 5
for (int b=0; b<arr[a].length; b++){ //arr[a].length는 5
arr[a][b] = ++c;
}
}

//배열 출력
for (int a=0; a<arr.length; a++) {  //arr.length는 5
for (int b=0; b<arr[a].length; b++){ //arr[a].length는 5
System.out.printf("%2d ", arr[a][b]);
}
System.out.println(); //행바꾸기 코딩. 배열의 배열처럼 출력하기 위해 5번째마다 행을 바꿔야함
}
}
}

---

문제) 아래와 같은 형태의 숫자 출력이 되도록 배열의 배열 지정.
25 24 23 22 21
20 19 18 17 16
15 14 13 12 11
10  9  8  7  6
 5  4  3  2  1

package com.test;
public class Sample30 {
public static void main(String[] args) {

//배열 선언
int[][] arr = new int[5][5];

//초기값 지정
for (int a=0, c=25; a < arr.length; a++) {  //arr.length는 5
for (int b=0; b < arr[a].length; b++){ //arr[a].length는 5
arr[a][b] = c--;
}
}

//배열 출력
for (int a=0; a<arr.length; a++) {  //arr.length는 5
for (int b=0; b<arr[a].length; b++){ //arr[a].length는 5
System.out.printf("%2d ", arr[a][b]);
}
System.out.println(); //행바꾸기 코딩. 배열의 배열처럼 출력하기 위해 5번째마다 행을 바꿔야함
}
}
}

---

문제) 아래와 같은 형태의 숫자 출력이 되도록 배열의 배열 지정.
 1  6 11 16 21
 2  7 12 17 22
 3  8 13 18 23
 4  9 14 19 24
 5 10 15 20 25

package com.test;
public class Sample31 {
public static void main(String[] args) {

//배열 선언

int[][] arr = new int[5][5];

//초기값 지정

for (int a=0, c=0; a < arr.length; a++) {  //arr.length는 5

for (int b=0; b < arr[a].length; b++){ //arr[a].length는 5

arr[b][a] = ++c;

}

}

//배열 출력

for (int a=0; a<arr.length; a++) {  //arr.length는 5

for (int b=0; b<arr[a].length; b++){ //arr[a].length는 5

System.out.printf("%2d ", arr[a][b]);

}

System.out.println(); //행바꾸기 코딩. 배열의 배열처럼 출력하기 위해 5번째마다 행을 바꿔야함

}

}

}

---

문제) 아래와 같은 형태의 숫자 출력이 되도록 배열의 배열 지정.
 1  2  3  4  5 
 2  3  4  5  6
 3  4  5  6  7
 4  5  6  7  8
 5  6  7  8  9

package com.test;

public class Sample32 {

public static void main(String[] args) {

//배열 선언

int[][] arr = new int[5][5];

//초기값 지정

for (int a=0, c=1; a < arr.length; a++) {  //arr.length는 5

for (int b=0; b < arr[a].length; b++){ //arr[a].length는 5

arr[a][b] = c++;

}

c-=4;

}

//배열 출력

for (int a=0; a<arr.length; a++) {  //arr.length는 5

for (int b=0; b<arr[a].length; b++){ //arr[a].length는 5

System.out.printf("%2d ", arr[a][b]);

}

System.out.println(); //행바꾸기 코딩. 배열의 배열처럼 출력하기 위해 5번째마다 행을 바꿔야함

}

}

}

---

문제) 아래와 같은 형태의 숫자 출력이 되도록 배열의 배열 지정.
 1  2  3  4  5
 5  1  2  3  4
 4  5  1  2  3
 3  4  5  1  2
 2  3  4  5  1

package com.test;

public class Sample33 {

public static void main(String[] args) {

//배열 선언

int[][] arr = new int[5][5];

//초기값 지정

for (int a=0, c=2; a < arr.length; a++) {  //arr.length는 5

c--;

for (int b=0; b < arr[a].length; b++){ //arr[a].length는 5

if(a==b){

c=1;

}

arr[a][b] = c++;

}

}

//배열 출력

for (int a=0; a<arr.length; a++) {  //arr.length는 5

for (int b=0; b<arr[a].length; b++){ //arr[a].length는 5

System.out.printf("%2d ", arr[a][b]);

}

System.out.println(); //행바꾸기 코딩. 배열의 배열처럼 출력하기 위해 5번째마다 행을 바꿔야함

}

}

}

---

문제) 아래와 같은 형태의 숫자 출력이 되도록 배열의 배열 지정.
 1  2  3  4  5
10  9  8  7  6
11 12 13 14 15
20 19 18 17 16
21 22 23 24 25

package com.test;

public class Sample34 {

public static void main(String[] args) {

//배열 선언

int[][] arr = new int[5][5];

//초기값 지정

for (int a=0, c=1; a < arr.length; a++) {  //arr.length는 5

for (int b=0, d=4; b < arr[a].length; b++){ //arr[a].length는 5

if (a%2 == 0){//a%2가 짝수인것만 내림차순입력

arr[a][b] = c++;

} else {

arr[a][d] = c++;

d-=1;

}

}

}

//배열 출력

for (int a=0; a<arr.length; a++) {  //arr.length는 5

for (int b=0; b<arr[a].length; b++){ //arr[a].length는 5

System.out.printf("%2d ", arr[a][b]);

}

System.out.println(); //행바꾸기 코딩. 배열의 배열처럼 출력하기 위해 5번째마다 행을 바꿔야함

}

}

}

---

문제) 마방진(가로 세로 및 대각선에 있는 숫자들의 합이 같도록 배열한 것)

마방진 알고리즘

1. 첫 번째 수(1)를 첫 번째 행 중간 열에 배정.

2. 두 번째 수부터는 오른쪽 대각선 위로 올라가면서 숫자를 배정.

배열 범위를 넘는 경우 가상의 인접한 배열 위치에 배정.

3. 다음 수를 둘 곳이 이미 다른 숫자가 채워진 경우는 현재 위치에서 

한 행 내려간 다음 다시 대각선 위로 진행.

1단계 ---------

 0  1  0

 0  0  0

 0  0  0

2단계 ---------

 0  1  0

 0  0  0

 0  0  2

3단계 ---------

 0  1  0

 3  0  0

 0  0  2

4단계 ---------

 0  1  0

 3  0  0

 4  0  2

5단계 ---------

 0  1  0

 3  5  0

 4  0  2

6단계 ---------

 0  1  6

 3  5  0

 4  0  2

7단계 ---------

 0  1  6

 3  5  7

 4  0  2

8단계 ---------

 8  1  6

 3  5  7

 4  0  2

9단계 ---------

 8  1  6

 3  5  7

 4  9  2

package com.test;

public class Sample35 {

public static void main(String[] args) {

int size = 3; //크기는 홀수로만 지정할 것.

int[][] matrix = new int[size][size];

int a = 0;

int b = size/2;

for (int c=1; c<=size*size; c++) {

matrix[a][b] = c;

a--;

b++;

if (c%size==0){

a+=2;

b--;

} else {

if (b==size) {

b-=size; 

} else if (a<0) {

a+=size;

}

}

}

//배열 출력

for (int n=0; n<matrix.length; n++) {

for (int m=0; m<matrix[n].length; m++) {

System.out.printf("%2d ", matrix[n][m]);

}

System.out.println();

}

}

}

---

만년달력

1. 1년 1월 1일부터 전년도 12월 31일까지의 총 날짜수 구함.
int total = (year-1)*365 + ((year-1)/4 - (year-1)/100 + (year-1)/400));

2. 해당년도 1월 1일부터 해당년도 해당월 1일까지의 총 날짜수 구함.
int[] m = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
for (int a=0; a<month-1; a++) {
total += m[a];
}
//해당월 1일 때문에 +1
total++;
//올해가 윤년이면서 2월 이상인 경우 +1
if (month>=3 && (year%4==0 && year%100!=0 || year%400==0)){
total++;
}

3. 해당년도 해당월의 첫 날(1일)의 요일(일, 월, 화, 수, 목, 금, 토) 구함. //7로 나눈 나머지 연산 구함. 0:일~6:토
String[] d = {"일", "월", "화", "수", "목", "금", "토"};
int days = total % 7;
System.out.printf("%s요일 %n", d[days]);

4. 해당년도 해당월의 마지막 날짜 구함.

5. 해당년도 해당월 달력 출력. -> 인터페이스의 영향을 받음.

---

문제) 특정 년, 월, 일 입력시 요일 구하기.
실행 예)
년도?
월?
일?
결과 : 월요일

package com.test;

import java.util.Scanner;

public class Sample36 {

public static void main(String[] args) {

//입력

Scanner sc = new Scanner(System.in);

System.out.print("년도?");

int year = sc.nextInt();

System.out.print("월?");

int month = sc.nextInt();

System.out.print("일?");

int day = sc.nextInt();

//처리

int total = (year-1)*365 + ((year-1)/4 - (year-1)/100 + (year-1)/400);   //전년도까지의 총 날짜수

int[] m = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

for (int a=0; a<month-1; a++) {

total += m[a];

}

if (month>=3 && (year%4==0 && year%100!=0 || year%400==0)){  //올해가 윤년이면서 2월 이상인 경우 +1

total++;

}

total += day;

String[] d = {"일", "월", "화", "수", "목", "금", "토"};

int days = total % 7;

//출력

System.out.printf("%s요일 %n", d[days]);

}

}

---

문제) 아래와 같은 형태의 숫자 출력이 되도록 배열의 배열 지정.
 1  2  3  4  5
16 17 18 19  6
15 24 25 20  7
14 23 22 21  8
13 12 11 10  9

해답은 없음 알아서 풀어보기