Java 코딩테스트 공부/Java 알고리즘 공부

Java 배열 파트 알고리즘1

daramG 2022. 8. 4. 16:08

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard

 

자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비 - 인프런 | 강의

자바(Java)로 코딩테스트를 준비하시는 분을 위한 강좌입니다. 코딩테스트에서 가장 많이 출제되는 Top 10 Topic을 다루고 있습니다. 주제와 연동하여 기초문제부터 중급문제까지 단계적으로 구성

www.inflearn.com

 

 

문제1 :

n개의 정수 입력받아 바로 앞 수보다 큰 수만 출력하기

 

입력 예제

4

5 3 4 7

출력 예제

5 4 7

 

소스코드 :

import java.util.*;
class Main {
	public ArrayList<Integer> solution(int n, int[] arr) {
		ArrayList<Integer> answer = new ArrayList<>();
		answer.add(arr[0]);
		for(int i=1; i<n; i++) {
			if(arr[i-1] < arr[i]) answer.add(arr[i]);
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = sc.nextInt();
		}
		for(int x : T.solution(n, arr)) {
			System.out.print(x + " ");
		}
	}
}

 

풀이 :

새로운 int배열 만들고 입력받았던 int배열에서 앞보다 클 경우 추가해서 출력하면 된다.

 

 

 

문제2

: 선생이 N명의 학생을 일렬로 세웠을 때 보이는 학생의 수를 구하시오

학생이 자기 앞에 보이는 학생보다 작거나 같으면 안 보인다.

정수 N(5<=N<=100000)

 

import java.util.*;
class Main {
	public int solution(int n, int[] arr) {
		int answer = 1;
		int max = arr[0];
		for(int i=1; i<n; i++) {
			if(max < arr[i]) {
				answer++;
				max = arr[i];
			}
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = sc.nextInt();
		}
		System.out.print(T.solution(n, arr));
	}
}

 

풀이 :

앞에 있는 학생 중 가장 큰 학생의 키를 저장할 max를 만들어

for문을 통해 max값과 학생들과 비교해 선생이 볼 수 있는 학생 수를 출력한다.

 

 

 

문제3 :

A, B가 가위바위보해서 각 회를 누가 이겼는지 출력

(1 : 가위 , 2 : 바위, 3: 보)

 

입력예제 :

5

2 3 3 1 3

1 1 2 2 3

출력예제 :

A

B

A

B

D

 

소스코드 :

import java.util.*;
class Main {
	public ArrayList<Character> solution(int n, int[] arr1, int[] arr2) {
		ArrayList<Character> answer = new ArrayList<>();
		for(int i=0; i<n; i++) {
			// draw
			if (arr1[i] == arr2[i]) answer.add('D');
			// A win
			else if (arr1[i] == 1 && arr2[i] == 3) answer.add('A');
			else if (arr1[i] == 2 && arr2[i] == 1) answer.add('A');
			else if (arr1[i] == 3 && arr2[i] == 2) answer.add('A');
			// B win
			else answer.add('B');
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr1 = new int[n];
		int[] arr2 = new int[n];
		for(int i=0; i<n; i++) {
			arr1[i] = sc.nextInt();
		}
		for(int i=0; i<n; i++) {
			arr2[i] = sc.nextInt();
		}
		for(char x : T.solution(n, arr1, arr2)) {
			System.out.println(x);
		}
	}
}

 

 

문제4 :

입력한 n만큼 피보나치 수열 출력하기 (n은 3이상 45이하)

 

import java.util.*;
class Main {
	public int[] solution(int n) {
		int[] arr = new int[n];
		arr[0] = 1;
		arr[1] = 1;
		for(int i=2; i<n; i++) {
			arr[i] = arr[i-2] + arr[i-1];
		}
		return arr;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		for(int x : T.solution(n)) {
			System.out.print(x + " ");
		}
	}
}

 

 

문제5 :

소수(에라토스테네스 체)

자연수 N 입력되면 1부터 N까지의 소수 개수 출력하기

 

소스코드 :

import java.util.*;
class Main {
	public int solution(int n) {
		int answer = 0;
		boolean prime[] = new boolean[n+1];
		Arrays.fill(prime, true);
		prime[0] = false;
		prime[1] = false;
		for(int i=2; i*i<=n; i++) {
			if(prime[i] == true) {
				for(int j=i*i; j<=n; j+=i) {
					prime[j] = false;
				}
			}
		}
		for(boolean x : prime) {
			if (x == true) answer++;
		}
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		System.out.println(T.solution(n));
	}
}

 

풀이 :

gif 출처 https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 

 

문제6 :

자연수의 개수 n (3이상 100이하) 가 주어지고

그 다음 줄에 n개의 자연수가 주어진다. (각 자연수 크기 100000이하)

각 숫자를 뒤집었을 때 소수일 경우에 해당하는 숫자들을 출력하여라(뒤집은 채로)

 

입력예제

4

24 59 250 370

출력예제

73

 

import java.util.*;
class Main {
	public boolean isPrime(int n) {
		if (n == 1) return false;
		for(int i=2; i<n; i++) {
			if (n % i == 0) return false;
		}
		return true;
	}
	public ArrayList<Integer> solution(int n, int[] arr) {
		ArrayList<Integer> answer = new ArrayList<>();
		// reverse
		for(int x : arr) {
			int tmp = x;
			int result = 0;
			while (tmp > 0) {
				int right = tmp % 10;
				result = result*10 + right;
				tmp = tmp / 10;
			}
			if (isPrime(result) == true) answer.add(result);
		}
		
		return answer;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] arr = new int[n];
		for(int i=0; i<n; i++) {
			arr[i] = sc.nextInt();
		}
		for(int x : T.solution(n, arr)) {
			System.out.print(x+" ");
		}
	}
}