Practice1 (파스칼의 삼각형)
파스칼의 삼각형(Pascal's triangle)은 수학에서 이항계수를 삼각형 모양의 기하학적 형태로 배열한 것이다.
파스칼의 삼각형은 다음과 같이 만들 수 있다.
1. 첫 번째 줄에는 숫자 1을 쓴다.
2. 그 다음 줄은 바로 위의 왼쪽 숫자와 오른쪽 숫자를 더한다.
삼각형의 행의 수가 입력으로 주어졌을 때,
파스칼의 삼각형을 출력하시오.
입출력 예시
| 입력 | 출력 |
|---|---|
| 1 | [[1]] |
| 3 | [[1], [1, 1], [1, 2, 1]] |
| 5 | [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]] |
import java.util.ArrayList;
public class Practice1 {
public static ArrayList<ArrayList<Integer>> solution(int numRows) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
for (int i = 0; i < numRows; i++) {
//각 행의 삼각형의 수를 list에 담을것
ArrayList<Integer> list = new ArrayList<>();
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) { //가장 외곽
list.add(1);
} else { //안쪽에 있을때
int x = result.get(i - 1).get(j - 1); //왼쪽
//get(i - 1):위에칸 중에 get(j - 1)좌측
int y = result.get(i - 1).get(j); //우측
list.add(x+y);
}
}
result.add(list); // list에다가는 한 줄을 넣기.
}
return result;
}
public static void main(String[] args) {
// Test code
System.out.println(solution(1));
System.out.println(solution(2));
System.out.println(solution(3));
System.out.println(solution(4));
System.out.println(solution(5));
}
}
Practice2
양의 정수로 이루어진 arr 배열이 주어졌을 때
해당 데이터로 만들 수 있는 permutation 중에서 다음과 같은 데이터를 출력하는 프로그램을 작성하세요.
- 현재 데이터보다 이전의 큰 수를 출력
- 한 번의 swap 으로 출력 가능한 큰 수를 출력
입출력 예시
| 입력 | 출력 |
|---|---|
| 3, 2, 1 | 3, 1, 2 |
| 1, 9, 4, 7, 6 | 1, 9, 4, 6, 7 |
| 1, 1, 2, 3 | 1, 1, 2, 3 |
import java.util.ArrayList;
import java.util.Arrays;
public class Practice2 {
public static void solution(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int idx = -1;
for (int i = arr.length - 1; i >= 1; i--) {
if (arr[i] < arr[i - 1]) {
idx = i - 1;
break; //바꿔줄 대상 고름
}
}
if (idx == -1) { //이미 정렬된 상태인것임.
System.out.println(Arrays.toString(arr));
return;
}
for (int i = arr.length - 1; i > idx; i--) {
if (arr[i] < arr[idx] && arr[i] != arr[i - 1]) { //같으면 왼쪽꺼랑 바꿔야되니까
int tmp = arr[i];
arr[i] = arr[idx];
arr[idx] = tmp;
break;
}
}
System.out.println(Arrays.toString(arr));
}
public static void main(String[] args) {
// Test code
int[] arr = {3, 2, 1};
solution(arr);
arr = new int[]{1, 9, 4, 7, 6};
solution(arr);
arr = new int[]{1, 1, 2, 3};
solution(arr);
arr = new int[]{5, 7, 3, 4, 5}; // [5, 5, 3, 4, 7]
solution(arr);
arr = new int[]{5, 7, 3, 6, 6}; // [5, 6, 3, 7, 6]
solution(arr);
}
}
Practice3
문자열 s1 과 s2 가 주어졌을 때,
s1 을 permutation 한 문자열이 s2 의 부분 문자열에 해당하면 true 를 반환하고
그렇지 않으면 false 를 반환하는 프로그램을 작성하세요.
입출력 예시
| s1 | s2 | 출력 |
|---|---|---|
| "ab" | "adbak" | true |
| "ac" | "car" | true |
| "ak" | "aabbkk" | false |
import java.util.ArrayList;
public class Practice3 {
// # 1 기본 permutation 방법
public static boolean solution(String s1, String s2) {
boolean[] visited = new boolean[s1.length()];
char[] out = new char[s1.length()];
ArrayList<String> list = new ArrayList<>();
permutation(s1.toCharArray(), 0, s1.length(), s1.length(), visited, out, list);
//permutation된 결과가 list에 들어옴
for (String s : list) {
if (s2.contains(s)) {
return true;
}
}
return false;
}
public static void permutation(char[] arr, int depth, int n, int r, boolean[] visited, char[] out, ArrayList<String> list) {
if (depth == r) {
list.add(new String(out));
}
for (int i = 0; i < n; i++) {
if (visited[i] != true) {
visited[i] = true;
out[depth] = arr[i];
permutation(arr, depth + 1, n, r, visited, out, list);
visited[i] = false;
}
}
}
// # 2 문제 규칙 찾아 해결 (permutation없이 푸는 법)
public static boolean solution2(String s1, String s2) {
final int ALPHABET = 26;
if (s1.length() > s2.length()) {
return false;
}
int[] cnt = new int[ALPHABET];
for (int i = 0; i < s1.length(); i++) {
cnt[s1.charAt(i) - 'a']++;
}
for (int i = 0; i < s2.length(); i++) {
cnt[s2.charAt(i) - 'a']--;
if (i - s1.length() >= 0) {
cnt[s2.charAt(i - s1.length()) - 'a']++; //다시 복원
}
boolean isZero = true;
for (int j = 0; j < cnt.length; j++) {
if (cnt[j] != 0) {
isZero = false;
break;
}
}
if (isZero) {
return true;
}
}
return false;
}
public static void main(String[] args) {
// Test code
String s1 = "ab";
String s2 = "adbak";
System.out.println(solution(s1, s2));
System.out.println(solution2(s1, s2));
System.out.println();
s1 = "ac";
s2 = "car";
System.out.println(solution(s1, s2));
System.out.println(solution2(s1, s2));
System.out.println();
s1 = "ak";
s2 = "aabbkk";
System.out.println(solution(s1, s2));
System.out.println(solution2(s1, s2));
}
}
두번째 방법에 대한 설명
Practice4
주어진 양의 정수가 행복한 수 인지를 판별하는 프로그램을 작성하세요.
행복한 수란,
각 자리수를 제곱한 것을 더하는 과정을 반복했을 때 1로 끝나는 수 이다.
행복한 수가 아니라면 1에 도달하지 못하고 같은 수열이 반복하게 된다.
'행복한 수'를 찾는 과정 예시
19 가 행복한 수인지 확인하는 과정
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1입출력 예시
| 입력 | 출력 |
|---|---|
| 19 | true |
| 2 | false |
| 61 | false |
import java.util.HashSet;
public class Practice4 {
public static boolean solution(int n) {
HashSet<Integer> set = new HashSet<>();
while (true) {
int result = 0;
while (n > 0) {
int remain = n % 10;
result += (int)Math.pow(remain,2);
n /= 10;
}
if (result == 1) {
return true;
} else {
n = result;
if(!set.add(result)){
return false;
}
}
}
}
public static void main(String[] args) {
// Test code
System.out.println(solution(19));
System.out.println(solution(2));
System.out.println(solution(61));
}
}
Practice5
영토에 대한 지도 정보가 row x col grid 맵 형태로 다음과 같이 주어졌다.
이 때, grid[i][j] 가 1이 면 땅 영역을 의미하고
grid[i][j] 가 0 이면 물 영역을 의미한다.
이와 같이 영토에 대한 지도 정보가 주어졌을 때 땅의 둘레를 구하는 프로그램을 작성하세요.
- grid 한 cell 의 변의 길이는 1 이다.
- 지도에는 하나의 독립된 영토만 있다. (분리된 땅 없음)
- 땅 내부에 물이 존재하지 않는다.
입출력 예시
| 입력 | 출력 |
|---|---|
| {{1}} | 4 |
| {{0, 1, 0, 0}, {1, 1, 1, 0}, {0, 1, 0, 0}, {1, 1, 0, 0}} | 16 |
public class Practice5 {
// 반복문 풀이
public static int solution(int[][] grid) {
int sum = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
if (i == 0 || grid[i - 1][j] == 0) { // 위
sum++;
}
if (i == grid.length - 1 || grid[i + 1][j] == 0) { // 아래
sum++;
}
if (j == 0 || grid[i][j - 1] == 0) { // 왼
sum++;
}
if (j == grid.length - 1 || grid[i][j + 1] == 0) { //오
sum++;
}
}
}
}
return sum;
}
// 재귀 풀이
public static int solution2(int[][] grid) {
int[][] directions = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == 1) {
return recursion(grid, directions, i, j);
}
}
}
return 0;
}
public static int recursion(int[][] grid, int[][] directions, int i, int j) {
int row = grid.length;
int col = grid[0].length;
grid[i][j] = -1; //지나온데는 다시가면 안되니까 -1로 체크
int cnt = 0;
for (int[] d : directions) {
int x = i + d[0];
int y = j + d[1];
if (x < 0 || y < 0 || x >= row || y >= col || grid[x][y] == 0) {
cnt++;
} else {
if (grid[x][y] == 1) {
cnt += recursion(grid, directions, x, y);
}
}
}
return cnt;
}
public static void main(String[] args) {
// Test code
int[][] grid = {{1}};
System.out.println(solution(grid));
System.out.println(solution2(grid));
System.out.println();
grid = new int[][]{{0, 1, 0, 0}, {1, 1, 1, 0}, {0, 1, 0, 0}, {1, 1, 0, 0}};
System.out.println(solution(grid));
System.out.println(solution2(grid));
}
}
Practice1
카탈랑 수는 0번, 1번, 2번, ... 순으로 아래와 같이 구성되는 수열을 의미한다.
- 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, …
이를 점화식으로 나타내면 아래와 같다.
카탈랑 수의 n 번째 값을 구하는 프로그램을 작성하세요.
입력 예시
| 입력 | 출력 |
|---|---|
| 0 | 1 |
| 2 | 2 |
| 5 | 42 |
| 7 | 429 |
public class Practice1 {
public static int solution(int n) {
int result = 0;
if (n <= 1) {
return 1;
}
for (int i = 0; i < n; i++) {
result += solution(i) * solution(n - i - 1);
}
return result;
}
public static void main(String[] args) {
// Test code
System.out.println(solution(0));
System.out.println(solution(2));
System.out.println(solution(5));
System.out.println(solution(7));
}
}Practice2
회문 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 같은 순서의 문자로 구성된 문자열을 말한다.
- 예시) ‘abba’ ‘kayak’, ‘madam’
유사회문은 문자열 그 자체는 회문이 아니지만 한 문자를 삭제하면 회문이 되는 문자열을 말한다.
- 예시) ‘summuus’의 5번째 또는 6번째 문자 ‘u’를 제거하면 ‘summus’인 회문을 만들 수 있다.
주어진 문자열을 확인한 후 문자열 종류에 따라 다음과 같이 출력하는 프로그램을 작성하세요.
- 회문: 0
- 유사회문: 1
- 기타: 2
입력 예시
| 입력 | 출력 |
|---|---|
| abba | 0 |
| summuus | 1 |
| xabba | 1 |
| xabbay | 2 |
| comcom | 2 |
| comwwmoc | 0 |
| comwwtmoc | 1 |
public class Practice2 {
public static int solution(String str) {
return isPalindrome(0, str.length() - 1, str.toCharArray(), 0);
}
public static int isPalindrome(int left, int right, char[] arr, int delCnt) {
while (left < right) {
if (arr[left] != arr[right]) {
if (delCnt == 0) {
if (isPalindrome(left + 1, right, arr, 1) == 0 ||
isPalindrome(left, right - 1, arr, 1) == 0) { // 이 둘중 하나가 회문이면
return 1; // 유사회문이다.
} else {
return 2;
}
} else {
return 2;
}
} else {
left++;
right--;
}
}
return 0;
}
public static void main(String[] args) {
// Test code
String[] str = {"abba", "summuus", "xabba", "xabbay", "comcom", "comwwmoc", "comwwtmoc"};
System.out.println(solution("abba"));
System.out.println(solution("summuus"));
System.out.println(solution("xabba"));
System.out.println(solution("xabbay"));
System.out.println(solution("comcom"));
System.out.println(solution("comwwmoc"));
System.out.println(solution("comwwtmoc"));
}
}
Practice3 (+정규표현식 사용)
주어진 1차 방정식에 대해 풀이를 하는 프로그램을 작성하세요.
- 해당 방정식은 '+', '-', 'x' 와 '상수'로만 이루어져 있다.
- 해가 없으면 "No solution" 을 출력,
해가 무한대인 경우 "Infinite solutions" 를 출력,
해가 있는 경우 x의 값을 "x=" 형태로 출력 하세요.
입력 예시
| 입력 | 출력 |
|---|---|
| "x+5-3+x=6+x-2" | "x=2" |
| "x=x" | "Infinite solutions" |
| "2x=x" | "x=0" |
public class Practice3 {
public static String solution(String equation) {
String[] parts = equation.split("=");
int[] leftSide = evaluate2(parts[0]);
int[] rightSide = evaluate2(parts[1]);
if (leftSide[0] == rightSide[0] && leftSide[1] == rightSide[1]) {
return "Infinite solution";
} else if (leftSide[0] == rightSide[0]) {
return "No solution";
} else {
return "x=" + (rightSide[1] - leftSide[1]) / (leftSide[0] - rightSide[0]);
}
}
public static int[] evaluate(String str) {
int[] result = new int[2]; // 0: x의 계수, 1: 상수항들
boolean isMinus = false;
int idx = 0;
while (idx != str.length()) {
char c = str.charAt(idx++);
if (c == '+') {
continue;
}
if (c == '-') {
isMinus = true;
continue;
}
if (c == 'x') {
result[0] += isMinus ? -1:1;
} else { // 상수
if (idx < str.length() && str.charAt(idx) == 'x') { // 다음항 체크
result[0] += isMinus ? -(c - '0'):(c - '0');
} else {
result[1] += isMinus ? -(c - '0'):(c - '0');
}
}
isMinus = false;
}
return result;
}
// # 2 정규표현식 사용
public static int[] evaluate2(String str) {
int[] result = new int[2];
for (String s : str.split("(?=[+-])")) { //+,-는 포함해서 스플릿해줘
if (s.equals("+x") || s.equals("x")) { //여기서 s는 char가 아니라 String이니까 eqauls로 비교해야됨
// +나 -가 딸려서 파싱되기땜에 비교할때 저렇게 비교하기
result[0]++;
} else if (s.equals("-x")) {
result[0]--;
} else if (s.contains("x")) { //위에서 안걸린경우(앞에 상수항이 있는경우)
result[0] += Integer.parseInt(s.substring(0,s.length()-1));
} else {
result[1] += Integer.parseInt(s); // +,-도 같이 떨어지니까 자연스럽게 연산됨
}
}
return result;
}
public static void main(String[] args) {
// Test code
String equation = "x+5-3+x=6+x-2";
System.out.println(solution(equation));
equation = "x=x";
System.out.println(solution(equation));
equation = "2x=x";
System.out.println(solution(equation));
}
}
Practice4
아래와 같이 구성되는 좋은 수라고 한다.
- 짝수 인덱스 위치에는 짝수
- 홀수 인덱스 위치에는 소수 (2, 3, 5, 7)
- 인덱스는 0 부터 시작
예를 들면,
2582 는 좋은 수다.
- 짝수 인덱스 위치에는 짝수인 2와 8로, 홀수 위치에는 소수인 5와 2로 구성된다.
반면,
3245 는 좋은 수가 아니다.
- 짝수 인덱스 위치에 홀수인 3이 위치하고 있다.1 이상의 정수 n이 주어졌을 때, n 자리로 구성될 수 있는 좋은 수의 개수를 출력하는 프로그램을 작성하세요.
단, n 의 값에 따라 값이 클 수 있으니 결과는 10^9 + 7로 나머지 연산을 한 결과로 출력하시오.
입력 예시
| 입력 | 출력 |
|---|---|
| 1 | 5 |
| 2 | 20 |
| 3 | 100 |
| 4 | 400 |
| 50 | 564908303 |
public class Practice4 {
final static int mod = (int) 1e9 + 7;
public static int solution(long n) {
return (int) recursion(1, n);
}
public static long recursion(long x, long y) {
if (y == 0) {
return x;
}
if (y % 2 == 1) { //홀수
return recursion((x * 4) % mod, y - 1);
} else {
return recursion((x * 5) % mod, y - 1);
}
}
public static void main(String[] args) {
// Test code
System.out.println(solution(1));
System.out.println(solution(2));
System.out.println(solution(3));
System.out.println(solution(4));
System.out.println(solution(50));
}
}
Practice5
하노이의 탑은 퍼즐의 일종이다.
하노이의 탑 퍼즐 게임 규칙은 다음과 같다.
- 한 번에 한 개의 원판 만 옮길 수 있다.
- 큰 원판이 작은 원판 위에 있어서는 안된다.
원판의 개수 n 이 주어졌을 때
가장 왼쪽 기둥으로부터 끝 기둥으로 이동하는 과정에 대해 출력하는 프로그램을 구현하세요.
입력 예시
| 입력 | 출력 |
|---|---|
| 2 | 1 2 1 3 2 3 |
| 3 | 1 3 1 2 3 2 1 3 2 1 2 3 1 3 |
public class Practice5 {
static StringBuffer sb;
public static void solution(int n) {
sb = new StringBuffer();
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);
}
public static void main(String[] args) {
// Test code
solution(2);
System.out.println();
solution(3);
System.out.println();
-
solution(4);
}
}
