99클럽 코테 스터디 29일차 TIL

비기너

문제

2231. Largest Number After Digit Swaps by Parity

#정렬

https://leetcode.com/problems/largest-number-after-digit-swaps-by-parity/description/

풀이

주어진 정수에서 짝수는 짝수끼리 홀수는 홀수끼리 자리를 바꿔서 최대가 되도록 하는 문제이다.

수를 자리수별로 나누어 배열에 저장한 뒤 짝 홀을 구분하여 정렬하면 된다.

수의 자릿수가 10이하이므로 어떤 정렬 알고리즘을 사용해도 상관없으므로 선택 정렬을 사용하였다.

코드

import java.util.*;

class Solution {
    public int largestInteger(int num) {
        int[] a = new int[(num + "").length()]; 
        for (int i = 0; i < a.length; i++) {
            a[a.length - i - 1] = num % 10;
            num /= 10;
        }

        for(int i = 0; i < a.length; i++) {
            int m = a[i] % 2;
            for (int j = i + 1; j < a.length; j++) {
                if (m == a[j] % 2 && a[j] > a[i]) {
                    int tmp = a[i];
                    a[i] = a[j];
                    a[j] = tmp;
                }
            }
        }

        int ans = 0;
        for (int i : a)
            ans = ans * 10 + i;  
        return ans;
    }
}

미들러

문제

9451번: 파도반 수열

#동적계획법

https://www.acmicpc.net/problem/9461

풀이

파도반 수열의 n번째 값을 구하는 문제이다

수열의 규칙을 살펴보면 d[n] = d[n - 1] + d[n - 5]임을 알 수 있다.

점화식에 따라 bottom up 방식으로 배열을 채운다.

해당 값이 int 범위를 벗어날 수 있으므로 long을 사용해야 한다.

코드

import java.util.*;
import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int t = Integer.parseInt(br.readLine());

		long[] d = new long[101];
		d[1] = 1;
		d[2] = 1;
		d[3] = 1;
		d[4] = 2;
		d[5] = 2;
		for (int i = 6; i <= 100; i++)
			d[i] = d[i - 1] + d[i - 5];

		while (t-- > 0) {
			int n = Integer.parseInt(br.readLine());
			bw.write(d[n] + "\n");
		}

		bw.flush();
		bw.close();
	}
}