자바 기초 예제 문제 풀이

초심으로 돌아가 Java 왕기초 예제 복습/정리하기

최대/최소값 - 습관적으로 0으로 초기화하지 않을 것.

import java.util.Scanner;

public class Max {
  public static void main(String[] args) {
    Scanner kb = new Scanner(System.in);
    int n = kb.nextInt();
    int [] data = new int [n];
    for (int i=0; i < n; i++) {
      data[i] = kb.nextInt();
    }
    kb.close();
 	int max = data[0]; // 0으로 초기화하면 음수 최대값 못 구하는 논리적 결함 생긴다. 밑 i는 0 아닌 1부터 시작해도 됨.
  	for (int i=0; i < n; i++) {
      if (data[i] > max) {
      	max = data[i];
      }
  	}
  }
}

Shift (한 칸씩 오른쪽으로 이동) - 역순으로 생각하라.

소수 - 2, 3, …, sqrt(n) 까지 체크 해보면 됨.

약수가 n/2보다 클 순 없다.

약수란 쌍으로 존재하는 것. 루트n보다 큰 게 있더라도 그 짝꿍은 루트n보다 작을 것. (둘다 루트n보다 클 순 없음.)

public class Prime {
	public static void main(String[] args) {
		int n;
		for (n=2; n < 100000; n++) {
			boolean isPrime = true; // 무죄추정의원칙처럼
			for (int i=2; i*i <= n && isPrime; i++) {
				if (n%i == 0 ) {
					isPrime = false;
					//break; //더이상돌필요없음
				}
			}
			if (isPrime)
				System.out.println(n);
		}
	}
}

쌍을 검사 - 반복문 안에 반복문

 for (int i=0; i<n; i++) { // [0,n)
   for (int j=i; j<n; j++) { // [i,n)
     // (0,0) (0,1) (0,2) ... (n-2, n-1) (n-1, n-1)
   }
 }
 for (int i=0; i<n; i++) { // [0,n]
   for (int j=0; j<=i; j++) { // [0,i]
     // (0,0) (1,0) (1,1) ... (n-1, n-2) (n-1, n-1)
   }
 }

구간의 합 - 0개 이상의 연속된 정수들을 더하여 얻을 수 있는 최대값. 구간시작점 루프와 구간 끝점 루프 - 반복문 안에 반복문

import java.util.Scanner;

public class Sequence {

	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int [] data = new int [n];
		for (int i=0; i < n; i++) {
			data[i] = kb.nextInt();
		}
		kb.close();
  		
		int maxSum = 0; //0개이상이므로
		for (int i=0; i < n; i++) { //구간시작점
          int sum = 0;
			for (int j=i; j<n; j++) { //구간끝점
              sum += data[j];
              if (maxSum < sum)
                maxSum = sum;
			}
		}
		System.out.println(maxSum);
	}

}

응용 - n개의 음이 아닌 한 자리 정수를 입력받아 배열에 저장한다. 이들 중에서 1개 이상의 연속된 정수들을 붙여(digit으로) 얻을 수 있는 소수들 중에서 최대값을 구하여 출력하는 프로그램을 구현하라

문제점 => n이 커지면 overflow(int는 2의 31승 정도가 한계) 발생 가능

import java.util.Scanner;

public class Complex {
	public static void main(String[] args) {
      Scanner kb = new Scanner(System.in);
      int n = kb.nextInt();
      int [] data = new int [n];
      for (int i=0; i < n; i++) {
        data[i] = kb.nextInt();
      }
      kb.close();

      int maxPrime = 0; // 음이 아닌 정수이므로 
      for (int i=0; i < n; i++) { // 구간의 시작점 
        for (int j=i; j < n; j++) { // 구간의 끝점 

          // convert digit data into an integer
          int val = 0;
          for (int k=i; k<=j; k++) // 하나의 정수로 환산 
            val = val*10 + data[k];

          // test if it is a prime
          boolean isPrime = true;
          for (int p=2; p*p <= val; p++) {
            if (val%p == 0) {
              isPrime = false;
              break;
            }
          }

          // if yes, compare to the max
          if (isPrime && val > 1 && val > maxPrime)
            maxPrime = val;
        }
      }
      if (maxPrime > 0)
      	System.out.println(maxPrime);
      else
        System.out.println("No Prime");
  }
}

스왑(Swap) - 자리를 바꿀 때에는 tmp 만들기

int tmp = data[j];
data[j] = data[j+1];
data[j+1] = tmp;

정렬(Sort) - 데이터를 크기 순으로 재배치. 오름차순(작=>큰)/내림차순(큰=>작) 어떤 순간에 컴퓨터가 실제로 하고 있는 일을 조사해보면 정렬을 하고 있을 확률이 가장 높다. 많은 정렬 알고리즘 존재.

버블정렬(BubbleSort)

가장 단순한 형태의 정렬 알고리즘 중 하나. n개의 수 중 제일 큰 값을 찾아 어떻게든 맨 마지막 자리로 가져옴. 그러고나면 이 값은 잊어버리고 데이터가 n-1개였던 것으로 생각하고 다시 이 과정을 반복한다. 가장 큰 값의 입장만 생각했을 때 맨 마지막으로 갈 수밖에 없도록.
```
for (int i=n-1; i>0; i--) {
  for (int j=0; j<i; j++) {
    if (data[j] > data[j+1]) { // 더 큰 걸 뒤로 이동
      int tmp = data[j];
      data[j] = data[j+1];
      data[j+1] = tmp; 
    }
  }
  for (int i=0; i<n; i++)
 	 System.out.println(data[i]);
}
```
끼워넣기(Insert)

이미 정렬된 배열(ordered list)에 x를 끼워넣을 때, 어디에 끼워넣을지를 찾는 방법은 크게 두 가지이다. 앞에서부터 하나씩 비교하여 x보다 크거나 같은 수를 찾거나, 뒤에서부터 하나씩 비교하여 x보다 작거나 같은 수를 찾는 방법이다. 대칭적이라 유사하다고 볼 수 있지만, 결국 x를 끼워넣고나서 x보다 큰 값들을 한 칸씩 오른쪽으로 이동해야 한다는 것을 고려했을 때, 전자는 x 앞뒤의 모든 수를 건드리는 데 비하여, 후자는 x 뒤의 수만 조사/이동시킨다는 장점이 있다. 따라서 뒤에서부터 검사를 수행한다.
```
for (int i=0; i<n; i++) {
  int tmp = kb.nextInt();
  int j;
  for (j= i-1; j>=0 && data[j]>tmp; j--) {
    // 새 수보다 크면 한 칸씩 뒤로 이동한다.
    data[j+1] = data[j];
  }
  // j는 유지된다.
  data[j+1] = tmp;
}
```

Ref

인프런 권오흠 강사님 https://www.inflearn.com

자바 기초 예제 문제 풀이

글 정보

태그

공유하기