[SWEA] D2, D3 문제 풀이 (JAVA)

D2

1859. 백만 장자 프로젝트

백준의 11501: 주식 문제와 거의 동일한 문제
매매가가 제일 높을 때 팔아야 하므로, 뒤에서부터 탐색하기
- 1 1 3 1 2와 같이 "1일차, 2일차 - 구매, 3일차 - 판매" & "4일차 - 구매, 5일차 - 판매"일 때가 최대 이익인 경우를 고려해야 하기 때문
- 최대 매매가 < 현재 매매가 ⇒ 갱신하기
- 최대 매매가 > 현재 매매가 ⇒ 구매하기

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

class Solution
{
	public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int t = 1; t <= T; t++) {
            int n = Integer.parseInt(br.readLine());
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int[] prices = new int[n];
            for (int i = 0; i < n; i++) {
                prices[i] = Integer.parseInt(st.nextToken());
            }

            int max = prices[n - 1];
            long total = 0;
            for (int i = n - 2; i >= 0; i--) {
                if (max > prices[i]) { // 현재 가격이 미래의 매매가보다 낮다면
                    // 물건 구매하기
                    total += max - prices[i];
                } else { // 현재 가격이 미래의 매매가보다 높다면
                    // 새로운 가격으로 최대 매매가 변경하기
                    max = prices[i];
                }
            }
            sb.append("#").append(t).append(" ").append(total).append("\n");
        }
        System.out.println(sb.toString());
    }
}

1954. 달팽이 숫자

🔗 문제 링크

배열을 윗부분, 아랫부분으로 나누어서 우선순위를 결정 ⇒ DFS 탐색을 통해 우선순위에 맞게 탐색
- 윗부분 우선순위: ↑ → ↓ ←
- 아랫부분 우선순위: ↓ ← ↑ →

import java.io.*;

class Solution
{
    static int n;
    static boolean finish;
    static int[][] arr;
    static boolean[][] visited;
    static int[][] move = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int t = 1; t <= T; t++) {
            n = Integer.parseInt(br.readLine());
            arr = new int[n][n];
            visited = new boolean[n][n];
            finish = false;
            dfs(1, 0, 0);
            sb.append("#").append(t).append("\n");
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    sb.append(arr[i][j]).append(" ");
                }
                sb.append("\n");
            }
        }
        System.out.println(sb.toString());
    }

    public static void dfs(int value, int x, int y) {
        if (value > n * n) {
            finish = true;
            return;
        }

        arr[x][y] = value;
        visited[x][y] = true;
        int start = (x <= n / 2) ? 0 : 2;
        for (int i = start, cnt = 0; cnt < 4; cnt++, i = (i + 1) % 4) {
            if (finish) break;
            int nx = x + move[i][0];
            int ny = y + move[i][1];
            if (nx < 0 || ny < 0 || nx >= n || ny >= n || visited[nx][ny]) continue;
            dfs(value + 1, nx, ny);
        }
    }
}

1204. 최빈수 구하기

🔗 문제 링크

점수는 0에서 100까지 ⇒ 점수가 인덱스인 배열 생성하기(인덱스: 0 ~ 100)
학생들의 점수를 입력받고, 해당 인덱스(=점수)의 값을 1씩 증가하기 → 배열의 값이 가장 큰 인덱스(=점수) 출력하기

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

class Solution {
    static final int N = 100, M = 1000;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        for (int t = 1; t <= T; t++) {
            int testCase = Integer.parseInt(br.readLine());
            int[] scores = new int[N + 1];
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < M; i++) {
                int score = Integer.parseInt(st.nextToken());
                scores[score]++;
            }
            int max = scores[0], maxIdx = 0;
            for (int i = 1; i <= N; i++) {
                if (scores[i] >= max) {
                    max = scores[i];
                    maxIdx = i;
                }
            }
            sb.append("#").append(testCase).append(" ").append(maxIdx).append("\n");
        }
        System.out.println(sb.toString());
    }
}

2001. 파리 퇴치

🔗 문제 링크

N × N 배열을 M × M 크기로 탐색해서 해당 영역의 합(=죽인 파리의 수) 구하기
가장 큰 영역의 합을 구하기 위해 우선순위 큐 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Solution {
	static int N, M;
	static int[][] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(st.nextToken());
			M = Integer.parseInt(st.nextToken());

			arr = new int[N][N];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
			for (int i = 0; i <= N - M; i++) {
				for (int j = 0; j <= N - M; j++) {
					pq.offer(getSum(i, j));
				}
			}
			sb.append("#").append(t).append(" ").append(pq.poll()).append("\n");
		}
		System.out.println(sb.toString());
	}

	static int getSum(int x, int y) {
		int total = 0;
		for (int i = x; i < x + M; i++) {
			for (int j = y; j < y + M; j++) {
				total += arr[i][j];
			}
		}
		return total;
	}
}

1928. Base64 Decoder

🔗 문제 링크

인코딩된 문자열을 디코딩하는 것 ⇒ 자바의 Base64 라이브러리를 사용하면 쉽게 풀 수 있음 (import java.util.Base64)
- 그러나 다른 방법으로도 풀어볼 것..!

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Base64;

class Solution {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			String encodeStr = br.readLine();
			String decodeStr = new String(Base64.getDecoder().decode(encodeStr));

			sb.append("#").append(t).append(" ").append(decodeStr).append("\n");
		}
		System.out.println(sb.toString());
	}
}

1926. 간단한 369게임

🔗 문제 링크

숫자를 문자열로 변경 ⇒ 3, 6, 9가 들어가는지 확인
- 3, 6, 9가 들어간다면 한 글자씩 확인 ⇒ 출력할 -의 개수 구하기
- 그렇지 않다면 숫자 그대로 출력

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Solution {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int n = Integer.parseInt(br.readLine());
		for (int i = 1; i <= n; i++) {
			String num = String.valueOf(i);
			if (num.contains("3") || num.contains("6") || num.contains("9")) {
				for (int j = 0; j < num.length(); j++) {
					if (num.charAt(j) == '3' || num.charAt(j) == '6' || num.charAt(j) == '9') {
						sb.append("-");
					}
				}
			} else {
				sb.append(num);
			}
			sb.append(" ");
		}
		System.out.println(sb.toString());
	}
}

1979. 어디에 단어가 들어갈 수 있을까

🔗 문제 링크

가로와 세로 각각 연속된 1이 K개 나오는지 확인하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Solution {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int N = Integer.parseInt(st.nextToken());
			int K = Integer.parseInt(st.nextToken());
			int[][] arr = new int[N][N];
			for (int i = 0; i < N; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			int total = 0;
			for (int i = 0; i < N; i++) {
				// 가로 확인
				for (int j = 0; j < N; j++) {
					int cnt = 0; // 연속된 1의 개수
					while (j < N && arr[i][j] == 1) {
						cnt++;
						j++;
					}
					if (cnt == K)
						total++;
				}
				// 세로 확인
				for (int j = 0; j < N; j++) {
					int cnt = 0; // 연속된 1의 개수
					while (j < N && arr[j][i] == 1) {
						cnt++;
						j++;
					}
					if (cnt == K)
						total++;
				}
			}
			sb.append("#").append(t).append(" ").append(total).append("\n");
		}
		System.out.print(sb.toString());
	}
}

1974. 스도쿠 검증

🔗 문제 링크

가로 / 세로 / 사각형 각각 확인하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Solution {
	static final int N = 9;
	static int[][] sudoku;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			sudoku = new int[N][N];
			for (int i = 0; i < N; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					sudoku[i][j] = Integer.parseInt(st.nextToken());
				}
			}
			boolean result = checkRow() && checkCol() && checkSquare();
			sb.append("#").append(t).append(" ").append(result ? 1 : 0).append("\n");
		}
		System.out.print(sb.toString());
	}

	// 가로 확인
	public static boolean checkRow() {
		for (int i = 0; i < N; i++) {
			boolean[] used = new boolean[N + 1];
			for (int j = 0; j < N; j++) {
				int num = sudoku[i][j];
				if (used[num])
					return false;
				used[num] = true;
			}
		}
		return true;
	}

	// 세로 확인
	public static boolean checkCol() {
		for (int j = 0; j < N; j++) {
			boolean[] used = new boolean[N + 1];
			for (int i = 0; i < N; i++) {
				int num = sudoku[i][j];
				if (used[num])
					return false;
				used[num] = true;
			}
		}
		return true;
	}

	// 사각형 확인
	public static boolean checkSquare() {
		for (int i = 0; i < N; i += 3) {
			for (int j = 0; j < N; j += 3) {
				boolean[] used = new boolean[N + 1];
				for (int x = i; x < i + 3; x++) {
					for (int y = j; y < j + 3; y++) {
						int num = sudoku[x][y];
						if (used[num])
							return false;
						used[num] = true;
					}
				}
			}
		}
		return true;
	}
}

2005. 파스칼의 삼각형

🔗 문제 링크

DP를 사용해서 풀면 되는 문제
점화식
- i == j이거나 j가 0인 경우: dp[i][j] = 1
- 그 외의 경우: dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Solution {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			int n = Integer.parseInt(br.readLine());
			int[][] dp = new int[n][n];
			dp[0][0] = 1;
			for (int i = 1; i < n; i++) {
				for (int j = 0; j <= i; j++) {
					if (j == 0 || i == j)
						dp[i][j] = 1;
					else
						dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
				}
			}

			sb.append("#").append(t).append("\n");
			for (int i = 0; i < n; i++) {
				for (int j = 0; j <= i; j++) {
					sb.append(dp[i][j]).append(" ");
				}
				sb.append("\n");
			}
		}
		System.out.println(sb.toString());
	}
}

1983. 조교의 성적 매기기

🔗 문제 링크

"N / 10명에게 동일한 평점을 부여함" 이라는 문장을 흘려 읽어서 삽질한..
우선순위 큐를 사용해서 성적을 기준으로 내림차순 정렬하고, k번째 학생이 나올 때까지 poll()

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Solution {

	static String[] scores = { "A+", "A0", "A-", "B+", "B0", "B-", "C+", "C0", "C-", "D0" };

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int n = Integer.parseInt(st.nextToken());
			int k = Integer.parseInt(st.nextToken());
			PriorityQueue<Student> pq = new PriorityQueue<>();
			for (int i = 1; i <= n; i++) {
				st = new StringTokenizer(br.readLine(), " ");
				int mScore = Integer.parseInt(st.nextToken());
				int fScore = Integer.parseInt(st.nextToken());
				int hScore = Integer.parseInt(st.nextToken());
				double total = mScore * 0.35 + fScore * 0.45 + hScore * 0.2;
				pq.offer(new Student(i, total));
			}

			int cnt = 0, div = n / 10;
			while (!pq.isEmpty()) {
				Student student = pq.poll();
				if (student.idx == k) {
					sb.append("#").append(t).append(" ").append(scores[cnt / div]).append("\n");
					break;
				}
				cnt++;
			}
		}
		System.out.println(sb.toString());
	}

	static class Student implements Comparable<Student> {
		int idx; // 입력 순서
		double total;

		public Student(int idx, double total) {
			this.idx = idx;
			this.total = total;
		}

		@Override
		public int compareTo(Student s) {
			// 점수를 기준으로 내림차순 정렬
			if (this.total > s.total)
				return -1;
			return 1;
		}
	}
}

1961. 숫자 배열 회전

🔗 문제 링크

90도씩 회전할 때마다 변경되는 좌표 위치를 통해 규칙을 찾으면 됨
- arr[j][n - i - 1] = arr[i][j]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Solution {
	static int n;
	static int[][] arr, arr90, arr180, arr270;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			n = Integer.parseInt(br.readLine());
			arr = new int[n][n];
			arr90 = new int[n][n];
			arr180 = new int[n][n];
			arr270 = new int[n][n];

			for (int i = 0; i < n; i++) {
				StringTokenizer st = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < n; j++) {
					arr[i][j] = Integer.parseInt(st.nextToken());
				}
			}

			rotation(arr, arr90);
			rotation(arr90, arr180);
			rotation(arr180, arr270);
			sb.append("#").append(t).append("\n");
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					sb.append(arr90[i][j]);
				}
				sb.append(" ");
				for (int j = 0; j < n; j++) {
					sb.append(arr180[i][j]);
				}
				sb.append(" ");
				for (int j = 0; j < n; j++) {
					sb.append(arr270[i][j]);
				}
				sb.append("\n");
			}
		}
		System.out.println(sb.toString());
	}

	public static void rotation(int[][] arr1, int[][] arr2) {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				arr2[j][n - i - 1] = arr1[i][j];
			}
		}
	}
}

1959. 두 개의 숫자열

🔗 문제 링크

배열 A가 배열 B보다 긴 경우, 배열 B가 배열 A보다 긴 경우의 두 가지로 나누어서 풀기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Solution {
	static int n, m;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			int[] A = new int[n];
			int[] B = new int[m];
			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < n; i++) {
				A[i] = Integer.parseInt(st.nextToken());
			}
			st = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < m; i++) {
				B[i] = Integer.parseInt(st.nextToken());
			}
			

			int max = Integer.MIN_VALUE;
			if (n < m) {
				for (int i = 0; i <= m - n; i++) { // 배열 B에서 곱하는 시작 위치
					int idx = 0, total = 0;
					for (int j = i; j < i + n; j++) {
						total += A[idx++] * B[j];
					}
					max = Math.max(max, total);
				}
			} else {
				for (int i = 0; i <= n - m; i++) { // 배열 A에서 곱하는 시작 위치
					int idx = 0, total = 0;
					for (int j = i; j < i + m; j++) {
						total += A[j] * B[idx++];
					}
					max = Math.max(max, total);
				}
			}
			sb.append("#").append(t).append(" ").append(max).append("\n");
		}
		System.out.println(sb.toString());
	}
}

2007. 패턴 마디의 길이

🔗 문제 링크

마디의 길이가 최대 10 ⇒ 마디의 길이를 1씩 늘려서 확인하기
- 즉, 범위가 크지 않으니 완전탐색으로 하나씩 확인하면 됨

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Solution {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			String str = br.readLine();
			int len = 0;
			for (int i = 1; i <= 10; i++) { // 마디의 길이를 1부터 10까지로 설정한 뒤 확인하기
				String s1 = str.substring(0, i);
				String s2 = str.substring(i, 2 * i);
				if (s1.equals(s2)) { // 두 문자열이 같다면 마디의 길이를 찾은 것
					len = i;
					break;
				}
			}
			sb.append("#").append(t).append(" ").append(len).append("\n");
		}
		System.out.println(sb.toString());
	}
}

1989. 초심자의 회문 검사

🔗 문제 링크

원본 문자열과 뒤집은 문자열이 같으면 1, 다르면 0을 출력하면 되는 문제
StringBuilder를 사용하면 뒤집은 문자열을 쉽게 구할 수 있음
- new StringBuilder(str).reverse().toString()

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Solution {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			String str = br.readLine(); // 원본 문자열
			String reverse = new StringBuilder(str).reverse().toString(); // 뒤집은 문자열
			boolean isEqual = str.equals(reverse); // 두 문자열이 같은지 확인
			sb.append("#").append(t).append(" ").append(isEqual ? 1 : 0).append("\n");
		}
		System.out.println(sb.toString());
	}
}

D3

1206. View

🔗 문제 링크

4 ≤ N ≤ 1000 ⇒ 시간 복잡도는 O(N) = O(1,000)이므로 빌딩을 하나씩 확인해도 됨
조망권이 확보된 세대의 수 = 현재 높이 - Max(왼쪽 건물 1의 높이, 왼쪽 건물 2의 높이, 오른쪽 건물 1의 높이, 오른쪽 건물 2의 높이)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Base64;
import java.util.StringTokenizer;

class Solution {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		for (int t = 1; t <= 10; t++) {
			int n = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int[] height = new int[n];
			for (int i = 0; i < n; i++) {
				height[i] = Integer.parseInt(st.nextToken());
			}

			int total = 0;
			for (int i = 2; i < n - 2; i++) {
				int h = height[i];
				if (h > height[i - 1] && h > height[i - 2] && h > height[i + 1] && h > height[i + 2]) {
					// 조망권이 확보된 세대의 수 구하기
					int max = Math.max(Math.max(height[i - 1], height[i - 2]), Math.max(height[i + 1], height[i + 2]));
					total += h - max;
				}
			}

			sb.append('#').append(t).append(' ').append(total).append('\n');
		}
		System.out.println(sb.toString());
	}
}

1244. 최대 상금

🔗 문제 링크

🔗 참고 링크 1, 참고 링크 2

어려웠던 문제.. 그리디로 풀려고 했으나 점점 조건이 늘어나므로 완전 탐색을 사용해야 함
- 이때, 그냥 완탐을 수행하면 시간 초과가 발생하므로 꼭 가지치기를 해야 함
방법 1
- 카드의 개수만큼 교환할 수 있다면 어떤 순서의 배열이든 만들 수 있음
- 따라서 교환 횟수 > 카드의 개수라면 교환 횟수를 카드의 개수로 변경하기
방법 2
- 같은 교환 횟수일 때 이미 나온 수(= 획득할 수 있는 상금)라면 넘어가기
- 따라서 교환 횟수를 하나의 문자열로 만들고 HashSet을 사용해서 중복 여부 확인하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Base64;
import java.util.HashSet;
import java.util.StringTokenizer;

import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;

class Solution {
	static int[] numbers;
	static int moveCnt, result;
	static HashSet<String> hashSet;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			String str = st.nextToken();
			moveCnt = Integer.parseInt(st.nextToken()); // 교환 횟수
			numbers = new int[str.length()];
			for (int i = 0; i < str.length(); i++) {
				numbers[i] = str.charAt(i) - '0';
			}

			// 카드의 개수만큼 교환할 수 있다면, 모든 조합을 만들 수 있음
//			if (moveCnt > str.length()) moveCnt = str.length();
			hashSet = new HashSet<>();
			result = 0;
			dfs(0);
			sb.append('#').append(t).append(' ').append(result).append('\n');
		}
		System.out.println(sb.toString());
	}

	public static void dfs(int move) {
		if (move == moveCnt) {
			result = Math.max(result, getTotal());
			return;
		}

		for (int i = 0; i < numbers.length - 1; i++) {
			for (int j = i + 1; j < numbers.length; j++) {
				swap(i, j);
				String check = getTotal() + ":" + move; // 획득할 수 있는 상금 : 교환 횟수
				if (!hashSet.contains(check)) { // "상금 : 교환 횟수"를 확인하지 않은 경우에만 계속 dfs 탐색
					hashSet.add(check);
					dfs(move + 1);
				}
				swap(i, j);
			}
		}
	}

	public static int getTotal() {
		int total = 0;
		for (int number : numbers) {
			total = total * 10 + number;
		}
		return total;
	}

	public static void swap(int a, int b) {
		int tmp = numbers[a];
		numbers[a] = numbers[b];
		numbers[b] = tmp;
	}
}

1208. Flatten

🔗 문제 링크

배열에 상자의 높이를 배열에 저장한 후, 최고점과 최저점을 구해서 평탄화 작업을 수행하면 됨
- 최고점 = 최고점 - 1
- 최저점 = 최저점 + 1

방법 1) Arrays.sort() 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

class Solution {
	static final int N = 100;
	static int[] heights;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		for (int t = 1; t <= 10; t++) {
			int dump = Integer.parseInt(br.readLine()); // 덤프 횟수
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			heights = new int[N]; // 상자의 높이
			for (int i = 0; i < N; i++) {
				heights[i] = Integer.parseInt(st.nextToken());
			}

			// 덤프하기
			for (int d = 0; d < dump; d++) {
				Arrays.sort(heights);
				heights[0]++;
				heights[N - 1]--;
				int diff = heights[N - 1] - heights[0];
				if (diff == 0 || diff == 1) { // 주어진 덤프 횟수 이내에 평탄화가 완료된 경우
					break;
				}
			}
			Arrays.sort(heights);
			sb.append('#').append(t).append(' ').append(heights[N - 1] - heights[0]).append('\n');
		}
		System.out.println(sb.toString());
	}
}

방법 2) 직접 minIdx, maxIdx 구하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Solution {
	static final int N = 100;
	static int[] heights;
	static int min, minIdx, max, maxIdx;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		for (int t = 1; t <= 10; t++) {
			int dump = Integer.parseInt(br.readLine()); // 덤프 횟수
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			heights = new int[N]; // 상자의 높이
			for (int i = 0; i < N; i++) {
				heights[i] = Integer.parseInt(st.nextToken());
			}

			// 덤프하기
			int diff = -1;
			for (int d = 0; d < dump; d++) {
				findMinMax();
				heights[minIdx]++;
				heights[maxIdx]--;
				diff = heights[maxIdx] - heights[minIdx];
				if (diff == 0 || diff == 1) { // 주어진 덤프 횟수 이내에 평탄화가 완료된 경우
					break;
				}
			}
			findMinMax();
			sb.append('#').append(t).append(' ').append(max - min).append('\n');
		}
		System.out.println(sb.toString());
	}

	static void findMinMax() { // 최고점, 최저점 찾기
		min = heights[0]; minIdx = 0; 
		max = heights[0]; maxIdx = 0;
		for (int i = 1; i < N; i++) {
			if (heights[i] < min) {
				min = heights[i];
				minIdx = i;
			} else if (heights[i] > max) {
				max = heights[i];
				maxIdx = i;
			}
		}
	}
}

2805. 농작물 수확하기

🔗 문제 링크

상단부와 하단부를 나눠서 탐색하면 됨
두 개의 인덱스를 사용하기
- 상단부: l--, r++
- 하단부: l++, r--

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Solution {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			int n = Integer.parseInt(br.readLine());
			int[][] map = new int[n][n];
			for (int i = 0; i < n; i++) {
				String[] strings = br.readLine().split(""); 
				for (int j = 0; j < n; j++) {
					map[i][j] = Integer.parseInt(strings[j]);
				}
			}

			int l = n / 2, r = n / 2, i = 0;
			int total = 0;
			// 상단부
			while (l > 0 && r < n - 1) {
				for (int j = l; j <= r; j++) {
					total += map[i][j];
				}
				i++;
				l--;
				r++;
			}
			
			// 하단부
			while (l <= r) {
				for (int j = l; j <= r; j++) {
					total += map[i][j];
				}
				i++;
				l++;
				r--;
			}
			sb.append('#').append(t).append(' ').append(total).append('\n');
		}
		System.out.println(sb.toString());
	}
}

5215. 햄버거 다이어트

🔗 문제 링크

재료를 고를 수 있는 경우를 모두 탐색해서 최대 맛 점수를 구하면 됨
- 즉, 완전 탐색으로 풀 수 있는 문제 (~~그치만 헤맸죠..?~~)
풀이 로직
- 현재까지의 칼로리가 L보다 큰 경우 ⇒ 탐색 종료
- 모든 재료를 다 탐색한 경우 ⇒ 현재 맛 점수가 최대 맛 점수보다 크다면 갱신 & 탐색 종료
- 해당 재료를 선택하는 경우와 선택하지 않는 경우로 나누어서 탐색

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Solution {
	static int N, L, maxTaste;
	static int[] tastes, kcals;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());
			N = Integer.parseInt(stringTokenizer.nextToken());
			L = Integer.parseInt(stringTokenizer.nextToken());
			tastes = new int[N];
			kcals = new int[N];
			for (int i = 0; i < N; i++) {
				stringTokenizer = new StringTokenizer(br.readLine(), " ");
				tastes[i] = Integer.parseInt(stringTokenizer.nextToken());
				kcals[i] = Integer.parseInt(stringTokenizer.nextToken());
			}

			maxTaste = 0;
			dfs(0, 0, 0);
			sb.append('#').append(t).append(' ').append(maxTaste).append('\n');
		}
		System.out.println(sb.toString());
	}

	static void dfs(int idx, int totalKcal, int totalTaste) {
		if (totalKcal > L)
			return;
		if (idx == N) {
			maxTaste = Math.max(maxTaste, totalTaste);
			return;
		}

		dfs(idx + 1, totalKcal, totalTaste); // 현재 재료를 선택하지 않는 경우
		dfs(idx + 1, totalKcal + kcals[idx], totalTaste + tastes[idx]); // 현재 재료를 선택하는 경우
	}
}

1289. 원재의 메모리 복구하기

🔗 문제 링크

초기화 상태의 값과 원래 상태의 값을 하나씩 비교해서 값이 다르면 메모리 값을 변경하면 됨
- 시작 위치부터 메모리의 끝까지 덮어씌우는 것 ⇒ Arrays.fill() 메소드를 사용하면 쉽게 변경할 수 있음

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

class Solution {
	static int n;
	static int[] original, reset;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			String[] strings = br.readLine().split("");
			n = strings.length;
			original = new int[n]; // 원래 상태
			reset = new int[n]; // 초기화 상태
			for (int i = 0; i < n; i++) {
				original[i] = Integer.parseInt(strings[i]);
			}

			int modifyCnt = 0;
			for (int i = 0; i < n; i++) { // 하나씩 비교하기
				if (original[i] != reset[i]) {
					modifyCnt++;
					Arrays.fill(reset, i, n, original[i]); // i ~ n-1을 original[i] 값으로 변경하기
				}
			}
			sb.append("#").append(t).append(" ").append(modifyCnt).append("\n");
		}
		System.out.println(sb.toString());
	}

}

1215. 회문1

🔗 문제 링크

8×8 크기의 글자판 ⇒ 회문이 존재하는지 완전 탐색으로 확인하면 됨
- 원본 문자열이랑 뒤집은 문자열이 같으면 회문이 존재하는 것
StringBuilder의 reverse() 메소드를 사용하면 문자열을 쉽게 뒤집을 수 있음

StringBuilder를 초기화하는 가장 빠른 방법은 길이를 0으로 만드는 것이다! (builder.setLength(0))
new StringBuilder()나 builder.delete() 메소드를 사용할 수도 있지만, 객체를 생성하거나 지우는 작업을 위한 시간이 소모되므로, 길이를 0으로 만드는 것이 가장 빠르다고 한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Solution {
	static int len, palindromeCnt;
	static final int N = 8;
	static char[][] board;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		for (int t = 1; t <= 10; t++) {
			len = Integer.parseInt(br.readLine()); // 찾아야 하는 회문의 길이
			board = new char[N][N];
			for (int i = 0; i < N; i++) {
				String line = br.readLine();
				for (int j = 0; j < N; j++) {
					board[i][j] = line.charAt(j);
				}
			}

			palindromeCnt = 0; // 회문의 개수
			findPalindrome();
			sb.append("#").append(t).append(" ").append(palindromeCnt).append("\n");
		}
		System.out.println(sb.toString());
	}

	static void findPalindrome() {
		for (int i = 0; i < N; i++) {
			for (int j = 0; j <= N - len; j++) {
				// Row 확인
				StringBuilder builder = new StringBuilder();
				for (int k = j; k < j + len; k++) {
					builder.append(board[i][k]);
				}
				String origin = builder.toString();
				String reverse = builder.reverse().toString();
				if (origin.equals(reverse))
					palindromeCnt++;

				// Col 확인
				builder.setLength(0);
				for (int k = j; k < j + len; k++) {
					builder.append(board[k][i]);
				}
				origin = builder.toString();
				reverse = builder.reverse().toString();
				if (origin.equals(reverse))
					palindromeCnt++;

			}
		}
	}
}

1220. Magnetic

🔗 문제 링크

붉은 자성체 또는 푸른 자성체 중 하나를 선택해서, 그 자성체를 기준으로 교착 상태가 발생하는지 확인하면 됨
- 붉은 자성체를 선택했다면 아래로 탐색, 푸른 자성체를 선택했다면 위로 탐색하면 됨
선택한 자성체가 위치한 열을 탐색하기
- 자신과 같은 자성체를 만난다면 탐색 종료 (= 다음 자성체에 교착 상태 확인을 맡기는 것)
- 자신과 다른 자성체를 만난다면 교착 상태가 발생한 것이므로 교착 상태의 개수를 증가시키고 탐색 종료

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Solution {
	static int n, deadLockCnt;
	static int[][] board;
	static Queue<int[]> queue = new LinkedList<>();

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		for (int t = 1; t <= 10; t++) {
			n = Integer.parseInt(br.readLine());
			board = new int[n][n];
			for (int i = 0; i < n; i++) {
				StringTokenizer stringTokenizer = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < n; j++) {
					board[i][j] = Integer.parseInt(stringTokenizer.nextToken());
					if (board[i][j] == 1)
						queue.offer(new int[] { i, j });
				}
			}
			deadLockCnt = 0;
			findDeadLock();

			sb.append("#").append(t).append(" ").append(deadLockCnt).append("\n");
		}
		System.out.println(sb.toString());
	}

	static void findDeadLock() {
		while (!queue.isEmpty()) {
			int[] pos = queue.poll();
			int x = pos[0], y = pos[1];
			for (int i = x + 1; i < n; i++) {
				// 같은 자성체를 만나면 다음 자성체에 교착상태 확인을 맡기고 탐색 종료
				if (board[i][y] == 1) { 
					break; 
				}
				// 다른 자성체를 만나면 교착상태가 발생하므로 탐색 종료
				if (board[i][y] == 2) { 
					deadLockCnt++;
					break;
				}
			}
		}
	}
}

1209. Sum

🔗 문제 링크

각 행, 열, 좌대각선, 우대각선의 합을 구하고, 그 중에서 최댓값을 구하면 되는 단순한 문제

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Solution {
	static final int N = 100;
	static int[][] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		for (int t = 1; t <= 10; t++) {
			int testCase = Integer.parseInt(br.readLine());
			arr = new int[N][N];
			for (int i = 0; i < N; i++) {
				StringTokenizer stringTokenizer = new StringTokenizer(br.readLine(), " ");
				for (int j = 0; j < N; j++) {
					arr[i][j] = Integer.parseInt(stringTokenizer.nextToken());
				}
			}
			int max = Math.max(Math.max(sumRow(), sumCol()), Math.max(sumCrossLeft(), sumCrossRight()));
			sb.append('#').append(testCase).append(' ').append(max).append('\n');
		}
		System.out.println(sb.toString());
	}

	static int sumRow() { // 가로
		int max = 0;
		for (int i = 0; i < N; i++) {
			int total = 0;
			for (int j = 0; j < N; j++) {
				total += arr[i][j];
			}
			max = Math.max(max, total);
		}

		return max;
	}

	static int sumCol() { // 세로
		int max = 0;
		for (int j = 0; j < N; j++) {
			int total = 0;
			for (int i = 0; i < N; i++) {
				total += arr[i][j];
			}
			max = Math.max(max, total);
		}
		return max;
	}

	static int sumCrossLeft() { // 좌대각선
		int max = 0;
		for (int i = 0; i < N; i++) {
			max += arr[i][i];
		}
		return max;
	}

	static int sumCrossRight() { // 우대각선
		int max = 0;
		for (int i = 0; i < N; i++) {
			max += arr[i][N - i - 1];
		}
		return max;
	}
}

2817. 부분 수열의 합

🔗 문제 링크

모든 원소를 하나씩 탐색하면서 부분 수열의 합이 K가 되는 경우의 수를 구하면 됨
- 즉, 완전 탐색 문제로 햄버거 다이어트 문제와 풀이 방법이 비슷함
풀이 로직
- 모든 원소를 다 탐색한 경우 ⇒ 합이 K라면 경우의 수 1 증가하기
- 현재 원소를 선택하는 경우와 선택하지 않는 경우로 나누어서 탐색하기

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Solution {
	static int N, K, count;
	static int[] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			StringTokenizer stringTokenizer = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(stringTokenizer.nextToken());
			K = Integer.parseInt(stringTokenizer.nextToken());
			arr = new int[N];
			stringTokenizer = new StringTokenizer(br.readLine(), " ");
			for (int i = 0; i < N; i++) {
				arr[i] = Integer.parseInt(stringTokenizer.nextToken());
			}
			count = 0; // 합이 K가 되는 경우의 수
			dfs(0, 0);
			sb.append('#').append(t).append(' ').append(count).append('\n');
		}
		System.out.println(sb.toString());
	}

	static void dfs(int depth, int total) {
		if (depth == N) {
			if (total == K)
				count++;
			return;
		}

		dfs(depth + 1, total); // 현재 원소를 선택하지 않는 경우
		dfs(depth + 1, total + arr[depth]); // 현재 원소를 선택하는 경우
	}
}

2814. 최장 경로

🔗 문제 링크

각 노드에서 DFS 탐색 & 백트래킹을 통해 최장 경로를 찾으면 됨

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Solution {
	static int N, M, maxLen;
	static int[][] graph;
	static boolean[] visited;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		int T = Integer.parseInt(br.readLine());
		for (int t = 1; t <= T; t++) {
			StringTokenizer stringTokenizer = new StringTokenizer(br.readLine(), " ");
			N = Integer.parseInt(stringTokenizer.nextToken());
			M = Integer.parseInt(stringTokenizer.nextToken());

			graph = new int[N + 1][N + 1];

			for (int i = 0; i < M; i++) {
				stringTokenizer = new StringTokenizer(br.readLine(), " ");
				int u = Integer.parseInt(stringTokenizer.nextToken());
				int v = Integer.parseInt(stringTokenizer.nextToken());
				graph[u][v] = 1;
				graph[v][u] = 1;
			}
			maxLen = 0;
			for (int i = 1; i <= N; i++) { // 각 노드에서 DFS 탐색
				visited = new boolean[N + 1];
				dfs(i, 1);
			}
			sb.append("#").append(t).append(" ").append(maxLen).append("\n");
		}
		System.out.println(sb.toString());
	}

	static void dfs(int node, int len) {
		visited[node] = true;

		for (int i = 1; i <= N; i++) {
			if (!visited[i] && graph[node][i] == 1) {
				dfs(i, len + 1);
				visited[i] = false;
			}
		}
		maxLen = Math.max(maxLen, len);
	}
}

'Algorithm' 카테고리의 다른 글

[BOJ] 5525: IOIOI (JAVA) (0)	2024.12.16

D2

1859. 백만 장자 프로젝트

1954. 달팽이 숫자

1204. 최빈수 구하기

2001. 파리 퇴치

1928. Base64 Decoder

1926. 간단한 369게임

1979. 어디에 단어가 들어갈 수 있을까

1974. 스도쿠 검증

2005. 파스칼의 삼각형

1983. 조교의 성적 매기기

1961. 숫자 배열 회전

1959. 두 개의 숫자열

2007. 패턴 마디의 길이

1989. 초심자의 회문 검사

D3

1206. View

1244. 최대 상금

1208. Flatten

2805. 농작물 수확하기

5215. 햄버거 다이어트

1289. 원재의 메모리 복구하기

1215. 회문1

1220. Magnetic

1209. Sum

2817. 부분 수열의 합

2814. 최장 경로

'Algorithm' 카테고리의 다른 글

티스토리툴바