[인프런] 알고리즘 Array , Two pointers

피보나치 수열

만약 7이 입력되면 1 1 2 3 5 8 13 이렇게 1 + 1 = 2 그리고 2 + 3 = 5 이런식으로 반복

 

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

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) throws IOException{
		Main T = new Main();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		for(int x : T.solution(n)) System.out.print(x + " ");
	}

}

처음은 1 그리고 두번째도 1이여서 answer[0] 과 [1]에 1을 대입해준다.

그리고 누적해서 더 해주는 answer을 만들어서 return 해주면 됨.

 

배열 안쓰고 풀려면?

 

	public void solution(int n) {
		int a = 1, b = 1, c;
		System.out.print(a+" "+b+" ");
		for(int i=2; i<n; i++) {
			c = a + b;
			System.out.print(c+" ");
			a = b;
			b = c;
		}
	}

전에 있던 값을 넣어주면 된다.

---

점수계산

OX 문제는 맞거나 틀린 두 경우의 답을 가지는 문제

연속으로 답이 맞으면 두 번째 문제 2점, 세 번째 문제 3점 이런식으로, 틀린 문제는 0으로 계산한다.

public class Main {
	public int solution(int n,int[] arr) {
		int answer = 0;
		int cnt = 0;
		for(int i=0; i<n; i++) {
			if(arr[i] == 1) {
				cnt++;
				answer+=cnt;
			}else {
				cnt = 0;
			}
		}
		
		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));
	}

}

---

두 배열 합치기

둘이 합쳐서 그냥 정렬하는거 말고 투포인터 알고리즘을 물어보는거다

 

3

1 3 5

5

2 3 6 7 9

 

이렇게 받으면

둘이 비교해서 작은 값을 넣어주고 그 값의 i를 ++ 해주고, 계속해서 비교 하면서 넣어준다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	public ArrayList<Integer> solution(int n,int m,int[] arr1, int[] arr2) {
		ArrayList<Integer> answer = new ArrayList<Integer>();
		// 두개의 포인터
		int p1 = 0, p2 = 0;
		
		while(p1 < n && p2 < m) {
			if(arr1[p1] < arr2[p2]) {
				answer.add(arr1[p1++]); // 따로 p1++안적고 후위 연산자를 이용해서 안에서 더해줄 수 있다.
			}else {
				answer.add(arr2[p2++]);
			}
		}
		
		while(p1 < n) answer.add(arr1[p1++]);
		while(p2 < m) answer.add(arr2[p2++]);
		
		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];
		for(int i=0; i<arr1.length; i++) {
			arr1[i] = sc.nextInt();
		}
		int m = sc.nextInt();
		int[] arr2 = new int[m];
		for(int i=0; i<arr2.length; i++) {
			arr2[i] = sc.nextInt();
		}
		
		for(int x : T.solution(n,m,arr1,arr2)) {
			System.out.print(x+" ");			
		} 
	}

}

while문 첫 부분을 보면 둘 중 하나의 배열이라도 값을 넘어가게 되면 반복문이 끝난다.

그러면 arr2의 데이터 값들을 add해서 다 넣어준다.