백준 닷컴 단계 별로 풀어보기 21단계

1단계 팩토리얼 2 (백준 27433)

• 첫째 줄에 정수 N(0 ≤ N ≤ 20)이 주어진다.
• 첫째 줄에 N!을 출력한다.

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

public class Step_1 {
	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 n = Integer.parseInt(br.readLine());

		bw.write(factorial(1, n) + "\\n");

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

	public static long factorial(long base, int num) {
		if (num > 0) {
			base *= num;
			return factorial(base, num - 1);
		} else {
			return base;
		}
	}
}

A.

• 재귀함수 메소드를 이용해 팩토리얼을 구한다.

2단계 피모나치 수 5 (백준 10870)

• 첫째 줄에 n이 주어진다. n은 20보다 작거나 같은 자연수 또는 0이다.
• 첫째 줄에 n번째 피보나치 수를 출력한다.

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

public class Step_2 {
	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 n = Integer.parseInt(br.readLine());

		bw.write(method(0, 1, n) + "\\n");

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

	public static int method(int a, int b, int n) {
		if(n==0) {
			return a;
		} else if(n==1) {
			return b;
		} else {
			return method(b, a+b, n-1);
		}
	}
}

A.

• 이전 숫자와 현재 숫자, 반복 회수를 받아주는 메소드를 만든다.
• 0번, 1번은 고정이기 때문에 고정 값을 반환한다.
• 반복 회수가 1이 될 때 까지 반복하는 재귀함수를 만든다.
• 다음 함수에는 b, a+b, n-1을 받아서 가도록 한다.

3단계 재귀의 귀재 (백준 25501)

• 첫째 줄에 테스트케이스의 개수 T가 주어진다.
• 둘째 줄부터 T개의 줄에 알파벳 대문자로 구성된 문자열 S가 주어진다.

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

public class Step_3 {
	static int recursion;

	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 n = Integer.parseInt(br.readLine());
		for (int i = 0; i < n; i++) {
			recursion = 0;
			bw.write(palindrom(br.readLine()) + " " + recursion + "\\n");

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

	public static int palindrom(String str) {
		if (str.length() <= 1) {
			recursion++;
			return 1;
		} else {
			if (str.charAt(0) == str.charAt(str.length() - 1)) {
				recursion++;
				return palindrom(str.substring(1, str.length() - 1));
			} else {
				recursion++;
				return 0;
			}
		}
	}
}

A.

• 팰린드롬 메소드를 만들고 문자열을 받도록 한다.
• 전역변수 recursion을 선언하고 static으로 한다.
• 팰린드롬 메소드는 받은 문자열의 길이가 1 이하일 경우 팰린드롬으로 판단하여 1을 리턴하고, 연산횟수(recursion)을 1 높이도록 한다.
• 문자열 길이가 1보다 큰 경우 맨 앞의 글자와 맨 뒤의 글자를 비교하여 같을 경우 연산횟수를 1 늘리고 문자열의 앞 뒤를 자른 후 재귀하도록 한다.
• 맨 앞의 글자와 맨 뒤의 글자가 다른 경우 0을 리턴하고 연산횟수를 1 늘린다.
• 반복문으로 각 문자에 대해 팰린드롬 여부와 연산 횟수를 출력한다.

4단계 알고리즘 수업 - 병합 정렬 1 (백준 24060)

• 첫째 줄에 배열 A의 크기 N(5 ≤ N ≤ 500,000), 저장 횟수 K(1 ≤ K ≤ 108)가 주어진다.
• 다음 줄에 서로 다른 배열 A의 원소 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 109)
• 배열 A에 K 번째 저장 되는 수를 출력한다. 저장 횟수가 K 보다 작으면 -1을 출력한다.

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

public class Step_4 {
	static int[] temp;
	static int count = 0;
	static int test;
	static int show = -1;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		test = Integer.parseInt(st.nextToken());

		int[] arr = new int[n];
		temp = new int[n];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		br.close();
		
		merge_sort(arr, 0, n - 1);
		bw.write(show + "\\n");

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

	public static void merge_sort(int[] arr, int left, int right) {
		if (count == test) {
			return;
		}
		if (left < right) {
			int middle = (left + right) / 2;
			merge_sort(arr, left, middle);
			merge_sort(arr, middle + 1, right);
			merge(arr, left, middle, right);
		}
	}

	public static void merge(int[] arr, int left, int middle, int right) {
		int i = left, j = middle + 1, k = left;
		while (i <= middle && j <= right) {
			if (arr[i] <= arr[j]) {
				temp[k++] = arr[i++];
			} else {
				temp[k++] = arr[j++];
			}
		} // temp[k]부터 마지막까지 값을 넣는다. 넣는 값은 arr[i]와 arr[j]의 값을 비교해 작은 쪽을 넣는다.
		while (i <= middle) {
			temp[k++] = arr[i++];
		}
		while (j <= right) {
			temp[k++] = arr[j++];
		} // 두 파츠 중 한 쪽이 완료 된 경우 나머지 한 쪽의 결과를 배열에 담음
		for (i = left; i <= right; i++) {
			count++;
			if (count == test) {
				show = temp[i];
				return;
			}

			arr[i] = temp[i];
		}
	}
}

A.

• 병합정렬의 공식 메소드를 작성한다.
• 병합정렬의 임시 배열의 값을 대입할 때 전역변수 count를 1 늘리고 count가 k가 될 때 결과를 show에 저장하도록 수정한다.
• 임시 배열을 반복해서 생성하는 경우 시간을 많이 잡아먹게 되니 전역변수에 임시배열을 만들어주어야 시간이 단축된다.

5단계 칸토어 집합 (백준 4779)

• 입력을 여러 줄로 이루어져 있다. 각 줄에 N이 주어진다. 파일의 끝에서 입력을 멈춘다. N은 0보다 크거나 같고, 12보다 작거나 같은 정수이다.
• 입력으로 주어진 N에 대해서, 해당하는 칸토어 집합의 근사를 출력한다.

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

public class Step_5 {
	static StringBuilder cant = new StringBuilder();

	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int length = (int) Math.pow(3, 12);
		cantMaker(0, length - 1);
		while (sc.hasNext()) {
			System.out.println(cant.subSequence(0, (int) Math.pow(3, sc.nextLong())));
		}
	}

	public static void cantMaker(int left, int right) {
		int temp = (right - left + 1) / 3;
		if (right - left > 3) {
			cantMaker(left, left + temp - 1);
			blackMaker(left+temp, left+temp*2-1);
			cantMaker(left + temp * 2, right);
		} else {
			draw();
		}
	}
	public static void blackMaker(int left, int right) {
		for(int i = left; i<=right; i++) {
			cant.append(" ");
		}
	}
	public static void draw() {
		cant.append("- -");
	}
}

A.

• 칸토어 집합은 프랙탈 구조를 가져서 가장 큰 칸토어 집합을 구한 경우 하위의 칸토어 집합도 생성된다는 특징을 이용한다.
• 전역변수로 stringbuilder를 만들어준다. 0~3의 12승 까지의 칸토어 집합을 만들기 위한 메소드를 만든다.
• 칸토어 메이커는 범위를 받고 3등분 하여 각 범위에 대해 다시 칸토어 메이커와 블랙크 메이커를 실시하는 메소드이다.
• 칸토어 메이커는 크기가 3보다 작은 경우 최소단위로 인식하여 draw 메소드를 실행한다.
• draw 메소드 실행시 “- -”를 추가하고, 블랙크메이커는 범위 전부를 black로 처리하도록 하는 메소드이다.
• 스캐너를 이용하여 hasnext를 이용해 정지를 인식하고, substring을 이용해 stringbuilder의 일부를 잘라서 출력해주도록 한다.

6단계 별찍기 - 10 (백준 2447)

• 첫째 줄에 N이 주어진다. N은 3의 거듭제곱이다. 즉 어떤 정수 k에 대해 N=3k이며, 이때 1 ≤ k < 8이다.
• 첫째 줄부터 N번째 줄까지 별을 출력한다.

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

public class Step_6 {
	static boolean[][] star;
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int max = sc.nextInt();
		star = new boolean[max][max];
		starMaker(0, max-1, 0, max-1);
		StringBuilder sb = new StringBuilder();
		for(int i=0; i<max; i++) {
			for(int j=0; j<max; j++) {
				if(star[i][j]) {
					sb.append("*");
				} else {
					sb.append(" ");
				}
			}
			sb.append("\\n");
		}
		System.out.println(sb.toString());
		
	}
	public static void starMaker(int left, int right, int top, int bottom) {
		int temp = (right - left +1)/3;
		if(temp!=1) {
			starMaker(left, left+temp-1, top, top+temp-1);
			starMaker(left, left+temp-1, top+temp, top+temp*2-1);
			starMaker(left, left+temp-1, top+temp*2, bottom);
			starMaker(left+temp, left+temp*2-1, top, top+temp-1);
			starMaker(left+temp, left+temp*2-1, top+temp*2, bottom);
			starMaker(left+temp*2, right, top, top+temp-1);
			starMaker(left+temp*2, right, top+temp, top+temp*2-1);
			starMaker(left+temp*2, right, top+temp*2, bottom);
		} else {
			draw(left, top);
		}
	}
	public static void draw(int left, int top) {
		star[left][top]=true;
		star[left][top+1]=true;
		star[left][top+2]=true;
		star[left+1][top]=true;
		star[left+1][top+2]=true;
		star[left+2][top]=true;
		star[left+2][top+1]=true;
		star[left+2][top+2]=true;
	}
}

A.

• 칸토어 집합처럼 프랙탈 형태임을 이용한다.
• 2차원의 속성에 맞춰 메소드를 작성한다.

7단계 하노이 탑 이동 순서 (백준 11729)

• 첫째 줄에 옮긴 횟수 K를 출력한다.
• 두 번째 줄부터 수행 과정을 출력한다. 두 번째 줄부터 K개의 줄에 걸쳐 두 정수 A B를 빈칸을 사이에 두고 출력하는데, 이는 A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻이다.

import java.util.Scanner;

public class Step_7 {
 
	public static StringBuilder sb = new StringBuilder();
 
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		sb.append((int) (Math.pow(2, n) - 1)).append('\\n');
 
		Hanoi(n, 1, 2, 3);
		System.out.println(sb);
 
	}
 
	public static void Hanoi(int N, int start, int mid, int to) {
		if (N == 1) {
			sb.append(start + " " + to + "\\n");
			return;
		}
		Hanoi(N - 1, start, to, mid);
    
		sb.append(start + " " + to + "\\n");
		Hanoi(N - 1, mid, start, to);
 
	}
}

A.

• 다음 층을 옮길 때 이전 층의 이동이 1번 더 발생하게 되는 것을 이용한다.
• 첫 이동은 2, 3중 목적지가 아닌 곳으로, 큰 블록을 옮긴 후는 시작 지점을 거쳐 목적지로 보내도록 한다.