개발자는 기록이 답이다

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Array_피보나치 수열) 본문

알고리즘/인프런 - Java알고리즘 입문

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비(Array_피보나치 수열)

slow-walker 2023. 9. 4. 16:04

 

https://cote.inflearn.com/contest/10/problem/02-04

 

OnlineJudge

 

cote.inflearn.com

(위의 링크는 인프런 로그인 후, 해당 강의를 사지 않으면 접속이 되지 않습니다)

 

4. 피보나치 수열

예시 입력 1 

10

예시 출력 1

1 1 2 3 5 8 13 21 34 55

 

내가 푼 풀이(Time: 162ms Memory: 27MB)

1. 피보나치 수열이 될 수 있는 list를 만든다.

2. 맨 처음 1, 1은 고정으로 들어가있기도 하고, 다음 3번째 수 부터 앞에 있는 두수를 더 해야하기 때문에 추가한다

3. 그 다음 숫자부터 for문을 돌기 위해 2부터 n까지 순회한 뒤 해당하는 값들을 더해서 List에 저장한다.

4. 피보나치 수열이 저장된 list를 반복문으로 string으로 만들어준다.

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public String solution(int n) {
        String SPACE = " ";

        StringBuilder sb = new StringBuilder();
        int start = 1;
        List<Integer> list = new ArrayList<>();
        list.add(start);
        list.add(start);
        for (int i = 2; i < n; i++) {
            list.add(list.get(i - 1) + (list.get(i - 2)));
        }
        for (int x : list){
            sb.append(x).append(SPACE);
        }
        return sb.toString();
    }

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

 

 

강의 풀이1 (Time: 162ms Memory: 27MB)

배열 크기 n이 주어졌으니까 list안써도 되고 int[]로 처리할 수 있다.

answer을 배열로 반환해서 출력할때 for each로 순횐하면서 반환해서 바로 answer배열에 넣어주면 된다.

import java.util.Scanner;

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-1] + answer[i-2];
        }
        return answer;
    }

    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 + " ");
    }
}

 

강의 풀이 2(Time: 168ms Memory: 27MB)

손코딩 하라고 했을때 아래처럼 문제를 풀면 더 간단하다

1 1 2 []
a b c
   a b c
import java.util.Scanner;

public class Main {

    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;
        }
    }

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