자바 기초 예제 문제 풀이
초심으로 돌아가 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