자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 2. Array(2)

 

4. 피보나치 수열

 

<나의 풀이>

- fibo 배열에 피보나치수열 값을 저장

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	static int[] fibo;
	
	static int fibonacci(int num) {
		
		if(num==0||num==1) 
			fibo[num]=1;
		else
			fibo[num]=fibo[num-2]+fibo[num-1];
		
		return fibo[num];
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		fibo = new int[n];
		
		StringBuilder sb = new StringBuilder();
		
		for(int i=0;i<n;i++) {
			sb.append(fibonacci(i)+" ");
		}
		
		System.out.println(sb.toString().trim());
	}

}

 

<해설>

- 배열을 반환해서 출력

import java.util.*;

public class Main {
	public int[] solution(int n){
		int[] answer=new int[n];
		answer[0]=1;
		answer[1]=1;
		for(int i=2; i<n; i++){
			answer[i]=answer[i-2]+answer[i-1];
		}
		return answer;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		for(int x :T.solution(n)) System.out.print(x+" ");
	}
}

---

 

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

 

<나의 풀이>

- isSoSu(num): num이 소수인지 확인 후, 소수이면 true, 아니면 false 반환

간단히 2부터 num까지 돌면서 하나라도 나눠지는지 확인

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	
	static boolean isSosu(int num) {
		boolean answer=true;
		
		if(num==1) return false;
		else if(num==2) return true;
		
		for(int i=2;i<=Math.sqrt(num);i++) {
			if(num%i==0) {
				answer=false;
				break;
			}
		}
		
		return answer;
	}

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		
		int cnt=0;
		for(int i=1;i<n+1;i++) {
			if(isSosu(i)) cnt++;
		}
		
		System.out.println(cnt);
	}

}

 

<해설>

- ch[i] 배열: i가 소수이면  1, 아니면 0으로 표시

- 2부터 i 를 소수인지 체크 한 후, i가 소수이면 i의 배수들도 모두 소수로 표시

import java.util.*;

public class Main {
	public int solution(int n){
		int cnt=0;
		int[] ch = new int[n+1];
		for(int i=2; i<=n; i++){
			if(ch[i]==0){
				cnt++;
				for(int j=i; j<=n; j=j+i) ch[j]=1;
			}
		}
		return cnt;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		System.out.println(T.solution(n));
	}
}

 

 

---

 

6. 뒤집은 소수

 

<나의 풀이>

- StringBuilder 활용하여 간단히 문자열 reverse

- Integer.parseInt(문자열) 로 간단히 문자열을 숫자(정수)로 변환

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	static boolean isSosu(int num) {
		boolean answer=true;
		
		if(num==1) return false;
		else if(num==2) return true;
		
		for(int i=2;i<=Math.sqrt(num);i++) {
			if(num%i==0) {
				answer=false;
				break;
			}
		}
		
		return answer;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		String s = br.readLine();
		StringTokenizer st = new StringTokenizer(s);
		
		StringBuilder sb= new StringBuilder();
		StringBuilder answer= new StringBuilder();
		
		for(int i=0;i<n;i++) {
			sb.append(st.nextToken()).reverse();
			int num=Integer.parseInt(sb.toString());
			
			answer.append(isSosu(num)?num+" ":"");
			sb= new StringBuilder();
		}
		
		System.out.println(answer.toString().trim());
	}

}

 

<해설>

- isPrime(num): num이 소수인지 확인 후, 소수이면 true 아니면 false 반환

- solution(int n, int[] arr): arr배열에 있는 수들을 하나씩 reverse한 후 int배열로 반환

 

ex) int tmp=3210

res=0

while(tmp가 0보다 클 동안){

    int t= tmp%10 //t=0 -> t=1 -> t=2 -> t=3

    res=res*10+t  //res=0 -> res=1 -> res=12 -> res=123

    tmp=tmp/10   //tmp=321 -> tmp=32 -> tmp=3 -> tmp=0 

}

 

if(isFrime(123)) //123이 소수이면

answer에 123추가 

 

import java.util.*;

public class Main {
	public boolean isPrime(int num){
		if(num==1) return false;
		for(int i=2; i<num; i++){
			if(num%i==0) return false;
		}
		return true;
	}

	public ArrayList<Integer> solution(int n, int[] arr){
		ArrayList<Integer> answer = new ArrayList<>();
		for(int i=0; i<n; i++){
			int tmp=arr[i];
			int res=0;
			while(tmp>0){
				int t=tmp%10;
				res=res*10+t;
				tmp=tmp/10;
			}
			if(isPrime(res)) answer.add(res);
		}
		return answer;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int[] arr=new int[n];
		for(int i=0; i<n; i++){
			arr[i]=kb.nextInt();
		}
		for(int x : T.solution(n, arr)){
			System.out.print(x+" ");
		}
	}
}