1번 문제
파스칼의 삼각형은 수학에서 이항계수를 삼각형 모양의 기하학적 형태로 배열한 것
파스칼의 삼각형은 다음과 같이 만들수 있음
- 첫번째 줄에는 숫자 1을 쓴다
- 그 다음 줄은 바로 위의 왼쪽 숫자와 오른쪽 숫자를 더한다
삼각형의 행의 수가 입력으로 주어졌을 때, 파스칼의 삼각형을 출력하기
public class Practice1 {
public static ArrayList<ArrayList<Integer>> solution(int numRows){
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
for(int i = 0; i < numRows; i++){
ArrayList<Integer> list = new ArrayList<>();
for(int j = 0; j < i+1; j++){
if(j == 0 || j == i){
list.add(1);
}else{
int x = result.get(i-1).get(j-1);
int y = result.get(i-1).get(j);
list.add(x+y);
}
}
result.add(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));
}
}2번 문제
양의 정수로 이루어진 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
5,7,3,4,5 -> 5,5,3,4,7
5,7,3,6,6 -> 5,6,3,7,6
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;
}
}
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};
solution(arr);
arr = new int[]{5,7,3,6,6};
solution(arr);
}
}3번 문제
문자열 s1과 s2가 주어졌을 때 s1을 permutation 한 문자열이 s2의 부분 문자열에 해당하면 true를 반환하고 그렇지 않으면 false를 반환하는 프로그램 작성
예시
"ab" , "adbak" , true
"ac" , "car" , true
"ak" , "aabbkk" , false
재귀를 통한 풀이
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);
for (String s: list) {
if (s2.contains(s)) {
return true;
}
}
return false;
}
// 기존 permutation 코드 문제에 맞춰 변형
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)); // 여기에 Arrays.toString(out)하면 오류 {'a','b','c'} -> "[a,b,c]"
return;
}
for(int i = 0; i < n; i++){
if(!visited[i]){
visited[i] = true;
out[depth] = arr[i];
permutation(arr, depth+1, n, r, visited, out, list);
visited[i] = false;
}
}
}규칙을 찾아서 풀기(counting 하는 배열)
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()){
cnt[s2.charAt(i-s1.length()) - 'a']++;
}
boolean isZero = true;
for(int j = 0; j < ALPHABET; j++){
if(cnt[j] != 0){
isZero = false;
break;
}
}
if(isZero){
return true;
}
}
return false;
}4번 문제
주어진 양의 정수가 행복한 수인지를 판별하는 프로그램 작성
행복한 수란
-> 각 자리수를 제곱한 것을 더하는 과정을 반복했을때 1로 끝나는 수. 행복한 수가 아니라면 1에 도달하지 못하고 같은 수열이 반복하게 됨
19가 행복한 수인지를 확인하는 과정
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1public class Practice4 {
// 수열 반복 특성을 이용해 해결하는 문제
public static boolean solution(int n) {
HashSet<Integer> set = new HashSet<>();
while(set.add(n)){
int squareSum = 0;
while(n > 0){
int remain = n % 10;
squareSum += remain * remain;
n /= 10;
}
if(squareSum == 1){
return true;
}else{
n = squareSum;
}
}
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));
}
}5번 문제
영토에 대한 지도 정보가 row x col grid 맵 형태로 다음과 같이 주어짐
이때 grid[i][j]가 1이면 땅 영역 , 0이면 물영역을 의미
위와 같이 영토에 대한 지도 정보가 주어질시 땅의 둘레를 구하는 프로그램 작성
- grid 한 cell 변의 길이는 1
- 지도에는 하나의 독립된 영토만 있음(분리된 땅 X)
- 땅 내부에 물이 존재하지 않음
public static int solution(int[][] grid) {
// 이동 방향
int[][] directions = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
int cnt = 0;
int row = grid.length;
int col = grid[0].length;
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
if (grid[i][j] == 1) {
// 땅일 때 각 방향 탐색
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++;
}
}
}
}
}
return cnt;
}재귀로 푸는 경우
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); // 모든 1을 체크를 하게 됨
}
}
}
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;
}위 if 조건문에서 왜 grid[x][y] == 0이 맨 마지막에 위치해야하는지 인지하자!
Journey for Backend Developer