행렬 테두리 회전하기
문1) rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.
- x1 행 y1 열부터 x2 행 y2 열까지의 영역에 해당하는 직사각형에서 테두리에 있는 숫자들을 한 칸씩 시계방향으로 회전합니다.
다음은 6 x 6 크기 행렬의 예시입니다.
이 행렬에 (2, 2, 5, 4) 회전을 적용하면, 아래 그림과 같이 2행 2열부터 5행 4열까지 영역의 테두리가 시계방향으로 회전합니다. 이때, 중앙의 15와 21이 있는 영역은 회전하지 않는 것을 주의하세요.
행렬의 세로 길이(행 개수) rows, 가로 길이(열 개수) columns, 그리고 회전들의 목록 queries가 주어질 때, 각 회전들을 배열에 적용한 뒤, 그 회전에 의해 위치가 바뀐 숫자들 중 가장 작은 숫자들을 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.
제한사항
- rows는 2 이상 100 이하인 자연수입니다.
- columns는 2 이상 100 이하인 자연수입니다.
- 처음에 행렬에는 가로 방향으로 숫자가 1부터 하나씩 증가하면서 적혀있습니다.
- 즉, 아무 회전도 하지 않았을 때, i 행 j 열에 있는 숫자는 ((i-1) x columns + j)입니다.
- queries의 행의 개수(회전의 개수)는 1 이상 10,000 이하입니다.
- queries의 각 행은 4개의 정수 [x1, y1, x2, y2]입니다.
- x1 행 y1 열부터 x2 행 y2 열까지 영역의 테두리를 시계방향으로 회전한다는 뜻입니다.
- 1 ≤ x1 < x2 ≤ rows, 1 ≤ y1 < y2 ≤ columns입니다.
- 모든 회전은 순서대로 이루어집니다.
- 예를 들어, 두 번째 회전에 대한 답은 첫 번째 회전을 실행한 다음, 그 상태에서 두 번째 회전을 실행했을 때 이동한 숫자 중 최솟값을 구하면 됩니다.
입출력 예
| rows | columns | queries | result |
|---|---|---|---|
| 6 | 6 | [[2,2,5,4],[3,3,6,6],[5,1,6,3]] | [8, 10, 25][8, 10, 25] |
| 3 | 3 | [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] | [1, 1, 5, 3] |
| 100 | 97 | [[1,1,100,97]] | [1] |
입출력 예 설명
입출력 예 #1
- 회전을 수행하는 과정을 그림으로 표현하면 다음과 같습니다.
입출력 예 #2
- 회전을 수행하는 과정을 그림으로 표현하면 다음과 같습니다.
입출력 예 #3
- 이 예시에서는 행렬의 테두리에 위치한 모든 칸들이 움직입니다. 따라서, 행렬의 테두리에 있는 수 중 가장 작은 숫자인 1이 바로 답이 됩니다.
나의 풀이
package programmers;
import java.util.ArrayList;
import java.util.Arrays;
public class MatrixBorderRotation {
static int[][] map;
static ArrayList<Integer> minList ;
public static void rotation(int y1, int x1, int y2, int x2) {
int temp = map[y1][x1];
int min = temp;
for (int i = y1; i < y2; i++) {
map[i][x1] = map[i + 1][x1];
min = Math.min(min, map[i][x1]);
}
for (int i = x1; i < x2; i++) {
map[y2][i] = map[y2][i + 1];
min = Math.min(min, map[y2][i]);
}
for (int i = y2; i > y1; i--) {
map[i][x2] = map[i - 1][x2];
min = Math.min(min, map[i][x2]);
}
for (int i = x2; i > x1 + 1; i--) {
map[y1][i] = map[y1][i - 1];
min = Math.min(min, map[y1][i]);
}
map[y1][x1 + 1] = temp;
for(int[] a : map) {
System.out.println(Arrays.toString(a));
}
minList.add(min);
}
public static int[] solution(int rows, int columns, int[][] queries) {
int N = rows;
int M = columns;
map = new int[N+1][M+1];
minList = new ArrayList<>();
int num = 1;
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
map[i][j] = num++;
}
}
for(int[] query : queries) {
int y1 = query[0];
int x1 = query[1];
int y2 = query[2];
int x2 = query[3];
rotation(y1, x1, y2, x2);
}
System.out.println(minList);
int[] answer = new int[minList.size()];
for (int i = 0; i < minList.size(); i++) {
answer[i] = minList.get(i);
}
return answer;
}
public static void main(String[] args) {
int[][] queries = {{2,2,5,4},{3,3,6,6},{5,1,6,3}};
solution(6, 6, queries);
}
}
나의 생각
이번 문제의 핵심을 몇 가지 짚고 넘어가보자
- 2차원 배열에 숫자 1부터 시작하여 순차적으로 증가시키며 채우기
- N : 행렬의 행(row) 수
- M : 행렬의 열(col) 수
int num = 1;
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
map[i][j] = num++;
}
}map의 모습
행(row), 열(col)의 첫 번째 인덱스를 비워둔 이유는?
- rotation() 메서드 동작에서 index는 1부터 시작하기 때문에, 이를 맞추기 위해서 2가지 방법이 존재한다.
1. solution 메서드 내에 map = new int[N][M];
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
map[i][j] = num++;
}
}
ratation 메서드에서 y1--, x1--, y2--, x2--;
이 방법은 rotation 메서드 내에서 매개변수 각 값에서 1을 빼는 것으로
문제의 1 기반 인덱스를 자바의 0 기반 인덱스로 변환
(이 방법은 행렬의 실제 크기를 그대로 사용하고 매개변수 값을 조정하는 방식)
2. solution 메서드 내에 map = new int[N+1][M+1];
for(int i = 1; i <= N; i++) {
for(int j = 1; j <= M; j++) {
map[i][j] = num++;
}
}
solution 메서드에서 index를 1부터 강제시켰기때문에 ratation 메서드에서 인덱스를 바로 활용할 수 있음
(ratation 메서드에서 매개변수 값을 조정할 필요 없이 문제에서 주어진 매개변수를 직접 사용할 수 있음)
- 매개 변수로 주어진
query를 재귀함수(rotation 메서드)에 어떻게 전달할 것인가?
- 우리가 필요한 것은
int[][] queries = {{2,2,5,4},{3,3,6,6},{5,1,6,3}}이렇게 2차원 배열값으로 전달 받은 값들을 3개의 반복으로 나누고
1. 첫번째 반복
(2,2), (5,4)
2. 두번째 반복
(3,3), (6,6)
3. 세번째 반복
(5,1), (6,3)rotation 메서드에 이 값을 전달하여 시계방향으로 회전할 시작점(y1, x1),끝점(y2,x2)으로 테두리를 정함
(2,2), (5,4)
(3,3), (6,6)
(5,1), (6,3)
여기서 내가 막혔던 부분이 회전 방향이다.
처음 내가 시도 했던 회전 방향은 시계방향 순으로 (→,↓,←,↑) 방향을 결정하였다. 여기서 중요한 점은 회전을 시작하기 전에 테두리의 한 점의 값을 저장해두고, 이동 과정을 거쳐 마지막에 이 값을 올바른 위치에 넣어주어야한다는 것이다.
첫번째로 시도했던 방법
public static void rotation(int y1, int x1, int y2, int x2) {
int temp = map[y1][x1];
int min = temp;
for (int i = x1; i < x2; i++) {
map[y1][i] = map[y1][i + 1];
min = Math.min(min, map[y1][i]);
}
for (int i = y1; i < y2; i++) {
map[i][x2] = map[i + 1][x2];
min = Math.min(min, map[i][x2]);
}
for (int i = x2; i > x1; i--) {
map[y2][i] = map[y2][i - 1];
min = Math.min(min, map[y2][i]);
}
for (int i = y2; i > y1; i--) {
map[i][x1] = map[i - 1][x1];
min = Math.min(min, map[i][x1]);
}
map[y1 + 1][x1] = temp;
for(int[] a : map) {
System.out.println(Arrays.toString(a));
}
minList.add(min);
}
위 두 그림을 비교해서 보면 첫번째 순회의 결과 로테이션이 잘못됐음을 알 수 있다.
위 방향(→,↓,←,↑)으로 원소를 이동시킬 경우, 이동 중에 이미 옮겨진 값들이 새로운 값으로 덮어쓰여진다. 이로 인해 회전이 제대로 수행되지 않고, 일부 원소들이 잘못된 위치로 이동하거나 사라질 수 있다. 완전한 회전을 수행하려면, 각 단계에서 옮겨진 원소가 다음 원소의 이동에 영향을 주지 않도록 설계해야한다.
두번째 방법
public static void rotation(int y1, int x1, int y2, int x2) {
int temp = map[y1][x1];
int min = temp;
for (int i = y1; i < y2; i++) {
map[i][x1] = map[i + 1][x1];
min = Math.min(min, map[i][x1]);
}
for (int i = x1; i < x2; i++) {
map[y2][i] = map[y2][i + 1];
min = Math.min(min, map[y2][i]);
}
for (int i = y2; i > y1; i--) {
map[i][x2] = map[i - 1][x2];
min = Math.min(min, map[i][x2]);
}
for (int i = x2; i > x1 + 1; i--) {
map[y1][i] = map[y1][i - 1];
min = Math.min(min, map[y1][i]);
}
map[y1][x1 + 1] = temp;
for(int[] a : map) {
System.out.println(Arrays.toString(a));
}
minList.add(min);
}
주어진 순서로 행렬의 바깥 테두리를 시계 방향으로 한 칸 회전할 때, 아래쪽 행의 원소들을 왼쪽으로 이동시키는 과정은 다음과 같다.
int temp = 8
8 9 10
14 16
20 22
26 27 28
1. 왼쪽 열을 위로 이동
- 14를 8의 위치로 이동
- 20를 14의 위치로 이동
- 26를 20의 위치로 이동
14 9 10
20 16
26 22
26 27 28
2. 아래쪽 행을 왼쪽으로 이동
- 27를 26의 위치로 이동
- 28를 27의 위치로 이동
14 9 10
20 16
26 22
27 28 28
3. 오른쪽 열을 아래로 이동
- 10을 16의 위치로 이동
- 16을 22의 위치로 이동
- 22를 아래쪽 행의 마지막 원소 28의 위치로 이동
14 9 10
20 10
26 16
27 28 22
4. 윗쪽 행을 오른쪽으로 이동
- 9를 10의 위치로 이동.
- 맨 왼쪽 열의 최상단 값을 9의 위치로 이동.
14 8 9
20 10
26 16
27 28 22
거리두기 확인하기
문2) 발자를 희망하는 죠르디가 카카오에 면접을 보러 왔습니다.
코로나 바이러스 감염 예방을 위해 응시자들은 거리를 둬서 대기를 해야하는데 개발 직군 면접인 만큼
아래와 같은 규칙으로 대기실에 거리를 두고 앉도록 안내하고 있습니다.
- 대기실은 5개이며, 각 대기실은 5x5 크기입니다.
- 거리두기를 위하여 응시자들 끼리는 맨해튼 거리1가 2 이하로 앉지 말아 주세요.
- 단 응시자가 앉아있는 자리 사이가 파티션으로 막혀 있을 경우에는 허용합니다.
예를 들어,
 |  |  |
|---|---|---|
| 위 그림처럼 자리 사이에 파티션이 존재한다면 맨해튼 거리가 2여도 거리두기를 지킨 것입니다. | 위 그림처럼 파티션을 사이에 두고 앉은 경우도 거리두기를 지킨 것입니다. | 위 그림처럼 자리 사이가 맨해튼 거리 2이고 사이에 빈 테이블이 있는 경우는 거리두기를 지키지 않은 것입니다. |
 |  |  |
| 응시자가 앉아있는 자리(P)를 의미합니다. | 빈 테이블(O)을 의미합니다. | 파티션(X)을 의미합니다. |
5개의 대기실을 본 죠르디는 각 대기실에서 응시자들이 거리두기를 잘 기키고 있는지 알고 싶어졌습니다. 자리에 앉아있는 응시자들의 정보와 대기실 구조를 대기실별로 담은 2차원 문자열 배열 places가 매개변수로 주어집니다. 각 대기실별로 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
제한사항
- places의 행 길이(대기실 개수) = 5
- places의 각 행은 하나의 대기실 구조를 나타냅니다.
- places의 열 길이(대기실 세로 길이) = 5
- places의 원소는 P,O,X로 이루어진 문자열입니다.
- places 원소의 길이(대기실 가로 길이) = 5
- P는 응시자가 앉아있는 자리를 의미합니다.
- O는 빈 테이블을 의미합니다.
- X는 파티션을 의미합니다.
- 입력으로 주어지는 5개 대기실의 크기는 모두 5x5 입니다.
- return 값 형식
- 1차원 정수 배열에 5개의 원소를 담아서 return 합니다.
- places에 담겨 있는 5개 대기실의 순서대로, 거리두기 준수 여부를 차례대로 배열에 담습니다.
- 각 대기실 별로 모든 응시자가 거리두기를 지키고 있으면 1을, 한 명이라도 지키지 않고 있으면 0을 담습니다.
입출력 예
| places | result |
|---|---|
| [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] | [1, 0, 1, 1, 1] |
입출력 예 설명
입출력 예 #1
첫 번째 대기실
- 모든 응시자가 거리두기를 지키고 있습니다.
두 번째 대기실
- (0, 0) 자리의 응시자와 (2, 0) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
- (1, 2) 자리의 응시자와 (0, 3) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
- (4, 3) 자리의 응시자와 (4, 4) 자리의 응시자가 거리두기를 지키고 있지 않습니다.
세 번째 대기실
- 모든 응시자가 거리두기를 지키고 있습니다.
네 번째 대기실
- 대기실에 응시자가 없으므로 거리두기를 지키고 있습니다.
다섯 번째 대기실
- 모든 응시자가 거리두기를 지키고 있습니다.
두 번째 대기실을 제외한 모든 대기실에서 거리두기가 지켜지고 있으므로, 배열 [1, 0, 1, 1, 1]을 return 합니다.
두 테이블 T1, T2가 행렬 (r1, c1), (r2, c2)에 각각 위치하고 있다면, T1, T2 사이의 맨해튼 거리는 |r1 - r2| + |c1 - c2| 입니다
나의 풀이
dfs 접근법
package programmers;
import java.util.Arrays;
public class KeepYourDistance {
static final int MAX = 5;
static char[][] map;
static boolean[][] visited;
static int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
public static int[] solution(String[][] places) {
int[] answer = new int[places.length];
for (int i = 0; i < places.length; i++) {
map = new char[MAX][MAX];
visited = new boolean[MAX][MAX];
for (int j = 0; j < MAX; j++) {
map[j] = places[i][j].toCharArray();
}
answer[i] = checkRoom() ? 1 : 0;
}
System.out.println(Arrays.toString(answer));
return answer;
}
public static boolean checkRoom() {
for (int i = 0; i < MAX; i++) {
for (int j = 0; j < MAX; j++) {
if (map[i][j] == 'P') {
if (!dfs(i, j, i, j ,0)) {
return false;
}
}
}
}
return true;
}
public static boolean dfs(int y, int x, int ay, int ax, int depth) {
if (Math.abs(ay - y) + Math.abs(ax - x) > 2) return true;
if(map[y][x] == 'P' && depth > 0) {
return false;
}
visited[y][x] = true;
for(int[] dir : DIRS) {
int ny = y + dir[0];
int nx = x + dir[1];
if (ny >= 0 && nx >= 0 && ny < MAX && nx < MAX && !visited[ny][nx] && map[ny][nx] != 'X') {
if (!dfs(ny, nx, ay, ax, depth + 1)) {
return false;
}
}
}
visited[y][x] = false;
return true;
}
public static void main(String[] args) {
String[][] places = {
{"POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"},
{"POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"},
{"PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"},
{"OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"},
{"PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"}
};
solution(places);
}
}
P 주변을 직접 접근하는 방법
package programmers;
import java.util.Arrays;
public class KeepYourDistance {
static final int SIZE = 5;
static char[][] room;
public static int[] solution(String[][] places) {
int[] answer = new int[places.length];
for (int i = 0; i < places.length; i++) {
room = new char[SIZE][SIZE];
for (int j = 0; j < SIZE; j++) {
room[j] = places[i][j].toCharArray();
}
answer[i] = checkRoom() ? 1 : 0;
}
System.out.println(Arrays.toString(answer));
return answer;
}
public static boolean checkRoom() {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (room[i][j] == 'P') {
if (!isKeepYourDistance(i, j)) {
return false;
}
}
}
}
return true;
}
public static boolean isKeepYourDistance(int y, int x) {
// 상하좌우 확인
int[] dy = {-1, 1, 0, 0};
int[] dx = {0, 0, -1, 1};
for (int d = 0; d < 4; d++) {
int nextY = y + dy[d];
int nextX = x + dx[d];
if (nextY >= 0 && nextY < SIZE && nextX >= 0 && nextX < SIZE) {
if (room[nextY][nextX] == 'P') return false;
}
}
// 상하좌우 맨해튼 거리 2 확인
int[] dy2 = {-2, 2, 0, 0};
int[] dx2 = {0, 0, -2, 2};
for (int d = 0; d < 4; d++) {
int nextY = y + dy2[d];
int nextX = x + dx2[d];
if (nextY >= 0 && nextY < SIZE && nextX >= 0 && nextX < SIZE) {
if (room[nextY][nextX] == 'P' && room[(y + nextY) / 2][(x + nextX) / 2] != 'X') {
return false;
}
}
}
// 대각선 확인
int[] dy3 = {-1, -1, 1, 1};
int[] dx3 = {-1, 1, -1, 1};
for (int d = 0; d < 4; d++) {
int nextY = y + dy3[d];
int nextX = x + dx3[d];
if (nextY >= 0 && nextY < SIZE && nextX >= 0 && nextX < SIZE) {
if (room[nextY][nextX] == 'P') {
if (!(room[y][nextX] == 'X' && room[nextY][x] == 'X')) {
return false;
}
}
}
}
return true;
}
public static void main(String[] args) {
String[][] places = {
{"PXOOP", "XPXOX", "OXXPX", "OOXOX", "POXXP"},
{"POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"},
{"PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"},
{"OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"},
{"PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"}
};
solution(places);
}
}
나의 생각
맨해튼 거리 2 이내에 있는 경우를 생각해보면, 다음과 같은 경우의 수를 가진다.
- 맨해튼 거리 1에 있는 경우 =
상하좌우(1칸) - 맨해튼 거리 2에 있는 경우 =
상하좌우(2칸) - 맨해튼 거리 2에 있는 경우 =
대각선 (1칸)
그렇다면, 1번 경우는 거리두기가 안지켜지는 것이고, 2번과 3번은 벽의 존재 유무에 따라 거리두기 여부가 결정된다.
- 2번은 둘 사이에 파티션 하나가 존재해야한다
- 3번은 둘 사이에 파티션이 양옆으로 2개 존재해야한다.
문자열 압축
문3) 데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.
예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.
다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.
압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.
제한사항
- s의 길이는 1 이상 1,000 이하입니다.
- s는 알파벳 소문자로만 이루어져 있습니다.
입출력 예
| s | result |
|---|---|
"aabbaccc" | 7 |
"ababcdcdababcdcd" | 9 |
"abcabcdede" | 8 |
"abcabcabcabcdededededede" | 14 |
"xababcdcdababcdcd" | 17 |
입출력 예 설명
입출력 예 #1
- 문자열을 1개 단위로 잘라 압축했을 때 가장 짧습니다.
입출력 예 #2
- 문자열을 8개 단위로 잘라 압축했을 때 가장 짧습니다.
입출력 예 #3
- 문자열을 3개 단위로 잘라 압축했을 때 가장 짧습니다.
입출력 예 #4
- 문자열을 2개 단위로 자르면 "abcabcabcabc6de" 가 됩니다.
- 문자열을 3개 단위로 자르면 "4abcdededededede" 가 됩니다.
- 문자열을 4개 단위로 자르면 "abcabcabcabc3dede" 가 됩니다.
- 문자열을 6개 단위로 자를 경우 "2abcabc2dedede"가 되며, 이때의 길이가 14로 가장 짧습니다.
입출력 예 #5
- 문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
- 따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.
나의 풀이
package programmers;
public class StringCompression {
public static String compressString(String s, int len) {
StringBuilder compressed = new StringBuilder();
String pattern = ""; // 현재 비교할 문자열 패턴
int count = 1; // 문자열 패턴이 반복될 횟수
// 문자열의 길이만큼 반복하면서 주어진 길이(len)만큼 문자열을 자름
for(int i = 0; i < s.length(); i += len) {
// 다음 비교할 부분 문자열을 추출
String next = s.substring(i, Math.min(i+len, s.length()));
System.out.println(next);
// 이전 패턴과 동일한 경우 count를 증가
if(next.equals(pattern)) {
count++;
}else {
// 다른 경우, count가 1보다 크면 반복된 횟수를 문자열에 추가
if(count > 1) {
compressed.append(count);
}
// 새로운 패턴을 문자열에 추가
compressed.append(pattern);
pattern = next; // 패턴을 업데이트함
count = 1; // 카운트를 초기화 함
}
}
// 마지막 패턴에 대한 처리를 함
if(count > 1) {
compressed.append(count);
}
compressed.append(pattern);
System.out.println(compressed);
return compressed.toString();
}
public static int solution(String s) {
if(s.length() == 1) return 1;
int answer = s.length();
for(int i = 1; i <= s.length() / 2 ; i++) {
int compressLength = compressString(s, i).length();
answer = Math.min(answer, compressLength);
}
System.out.println(answer);
return answer;
}
public static void main(String[] args) {
String s = "aabbccdd";
solution(s);
}
}
나의 생각
aabbccdd를 예를들어 보자.
1개 단위로 짜를 때
- a,a,b,b,c,c,d,d
2개 단위로 짜를 때
- aa,bb,cc,dd
3개 단위로 짜를 때
- aab,bcc,dd
4개 단위로 짜를 때
- aabb,ccdd
위 과정을 봤을 때, 총 길이 s.length / 2의 크기까지만 확인하면 모든 경우로 짜를수 있다.
int answer = s.length();
for(int i = 1; i <= s.length() / 2 ; i++) {
int compressLength = compressString(s, i).length();
answer = Math.min(answer, compressLength);
}- 위 예제에서 len은
1 ~ 4이므로 1개, 2개, 3개, 4개 단위로i값을 증가시킬 수 있다.
for(int i = 0; i < s.length(); i += len) {
// 다음 비교할 부분 문자열을 추출
String next = s.substring(i, Math.min(i+len, s.length()));
// 이전 패턴과 동일한 경우 count를 증가
if(next.equals(pattern)) {
count++;
}else {
// 다른 경우, count가 1보다 크면 반복된 횟수를 문자열에 추가
if(count > 1) {
compressed.append(count);
}
// 새로운 패턴을 문자열에 추가
compressed.append(pattern);
pattern = next; // 패턴을 업데이트함
count = 1; // 카운트를 초기화 함
}
}
// 마지막 패턴에 대한 처리를 함
if(count > 1) {
compressed.append(count);
}
compressed.append(pattern);
return compressed.toString();
}초기 상태:
compressed: (빈 문자열)
pattern: (빈 문자열)
next: 아직 설정되지 않음
1. 첫 번째 a 처리:
next = "a"
pattern은 비어 있으므로, pattern = next
compressed는 변화 없음
결과: compressed = "", pattern = "a", next = "a"
2. 두 번째 a 처리:
next = "a"
next가 pattern과 같으므로, count 증가 (2가 됨)
compressed는 변화 없음
결과: compressed = "", pattern = "a", next = "a"
3. 첫 번째 b 처리:
next = "b"
next가 pattern과 다르므로, compressed에 count와 pattern 추가 ("2a")
pattern을 next로 변경, count 초기화
결과: compressed = "2a", pattern = "b", next = "b"
4. 두 번째 b 처리:
next = "b"
next가 pattern과 같으므로, count 증가 (2가 됨)
compressed는 변화 없음
결과: compressed = "2a", pattern = "b", next = "b"
이와 같은 방식으로 c와 d도 동일하게 처리
마지막 처리:
마지막 for 루프 이후, 마지막 패턴 d에 대한 처리가 필요함
count가 2이므로, compressed에 count와 pattern을 추가
최종 결과:
compressed = "2a2b2c2d"후보키
문4) 프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.
그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.
후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.
- 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
유일성(uniqueness): 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.최소성(minimality): 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.
제이지를 위해, 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.
위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 "학번"을 가지고 있다. 따라서 "학번"은 릴레이션의 후보 키가 될 수 있다.
그다음 "이름"에 대해서는 같은 이름("apeach")을 사용하는 학생이 있기 때문에, "이름"은 후보 키가 될 수 없다. 그러나, 만약 ["이름", "전공"]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다.
물론 ["이름", "전공", "학년"]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다.
따라서, 위의 학생 인적사항의 후보키는 "학번", ["이름", "전공"] 두 개가 된다.
릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.
제한사항
relation은 2차원 문자열 배열이다.relation의컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은릴레이션의 속성을 나타낸다.relation의로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는릴레이션의 튜플을 나타낸다.relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)
입출력 예
| relation | result |
|---|---|
| [["100","ryan","music","2"],["200","apeach","math","2"],["300","tube","computer","3"],["400","con","computer","4"],["500","muzi","music","3"],["600","apeach","music","2"]] | 2 |
입출력 예 설명
입출력 예 #1
- 문제에 주어진 릴레이션과 같으며, 후보 키는 2개이다.
나의 풀이
package programmers;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class CandidateKey {
static int rowCnt, colCnt;
static List<Set<Integer>> candidateKeys = new ArrayList<>();
public static int solution(String[][] relation) {
rowCnt= relation.length;
colCnt = relation[0].length;
for(int i = 1; i <= colCnt; i++) {
combine(relation, new HashSet<>(), 0, i);
}
return candidateKeys.size();
}
public static void combine(String[][] relation, Set<Integer> selectedColumns, int start, int number) {
if(selectedColumns.size() == number) {
if(checkUniqueness(relation, selectedColumns) && checkMinimality(selectedColumns)) {
candidateKeys.add(new HashSet<>(selectedColumns));
}
return;
}
for(int i = start; i < colCnt; i++) {
if(!selectedColumns.contains(i)) {
selectedColumns.add(i);
combine(relation, selectedColumns, i + 1, number);
selectedColumns.remove(i);
}
}
}
public static boolean checkUniqueness(String[][] relation, Set<Integer> selectedColumns) {
Set<String> uniqueCombinations = new HashSet<>();
for (String[] tuple : relation) {
StringBuilder keyBuilder = new StringBuilder();
for (int column : selectedColumns) {
keyBuilder.append(tuple[column]).append(":");
}
uniqueCombinations.add(keyBuilder.toString());
}
return uniqueCombinations.size() == rowCnt;
}
public static boolean checkMinimality(Set<Integer> selectedColumns) {
for (Set<Integer> candidateKey : candidateKeys) {
if (selectedColumns.containsAll(candidateKey)) {
return false;
}
}
return true;
}
public static void main(String[] args) {
String[][] relation = {
{"100","ryan","music","2"},
{"200","apeach","math","2"},
{"300","tube","computer","3"},
{"400","con","computer","4"},
{"500","muzi","music","3"},
{"600","apeach","music","2"}
};
solution(relation);
}
}
나의 생각
1. 모든 속성 조합을 생성
2. 생성된 각 조합에 대해 유일성을 검사
3. 유일성을 만족하는 조합 중에서 최소성을 만족하는지 확인
- 이미 선택된 후보키의 조합을 포함하는지 체크하여 최소성을 보장
4. 최소성을 만족하는 모든 조합을 후보키로 카운트우박수열 정적분
문5) 콜라츠 추측이란 로타르 콜라츠(Lothar Collatz)가 1937년에 제기한 추측으로 모든 자연수 k에 대해 다음 작업을 반복하면 항상 1로 만들 수 있다는 추측입니다.
1-1. 입력된 수가 짝수라면 2로 나눕니다.
1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다.
2.결과로 나온 수가 1보다 크다면 1번 작업을 반복합니다.예를 들어 주어진 수가 5 라면 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒2 ⇒ 1 이되어 총 5번만에 1이 됩니다.
수가 커졌다 작아지기를 반복하는 모습이 비구름에서 빗방울이 오르락내리락하며 우박이 되는 모습과 비슷하다고 하여 우박수 또는 우박수열로 불리기도 합니다. 현재 이 추측이 참인지 거짓인지 증명되지 않았지만 약 1해까지의 수에서 반례가 없음이 밝혀져 있습니다.
은지는 우박수열을 좌표 평면 위에 꺾은선 그래프로 나타내보려고 합니다. 초항이 k인 우박수열이 있다면, x = 0일때 y = k이고 다음 우박수는 x = 1에 표시합니다. 이런 식으로 우박수가 1이 될 때까지 점들을 찍고 인접한 점들끼리 직선으로 연결하면 다음과 같이 꺾은선 그래프를 만들 수 있습니다.
은지는 이렇게 만든 꺾은선 그래프를 정적분 해보고 싶어졌습니다. x에 대한 어떤 범위 [a, b]가 주어진다면 이 범위에 대한 정적분 결과는 꺾은선 그래프와 x = a, x = b, y = 0 으로 둘러 쌓인 공간의 면적과 같습니다. 은지는 이것을 우박수열 정적분이라고 정의하였고 다양한 구간에 대해서 우박수열 정적분을 해보려고 합니다. 0 이상의 수 b에 대해 [a, -b]에 대한 정적분 결과는 x = a, x = n - b, y = 0 으로 둘러 쌓인 공간의 면적으로 정의하며, 이때 n은 k가 초항인 우박수열이 1이 될때 까지의 횟수를 의미합니다.
예를 들어, 5를 초항으로 하는 우박수열은 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1 입니다. 이를 좌표 평면으로 옮기면 (0, 5), (1, 16), (2, 8), (3, 4), (4, 2), (5, 1) 에 점이 찍히고 점들을 연결하면 꺾은선 그래프가 나옵니다. 이를 [0,0] 구간에 대해 정적분 한다면 전체 구간에 대한 정적분이며, [1,-2] 구간에 대해 정적분 한다면 1 ≤ x ≤ 3인 구간에 대한 정적분입니다.
우박수의 초항 k와, 정적분을 구하는 구간들의 목록 ranges가 주어졌을 때 정적분의 결과 목록을 return 하도록 solution을 완성해주세요. 단, 주어진 구간의 시작점이 끝점보다 커서 유효하지 않은 구간이 주어질 수 있으며 이때의 정적분 결과는 -1로 정의합니다.
제한사항
- 2 ≤ k ≤ 10,000
- 1 ≤ ranges의 길이 ≤ 10,000
- ranges의 원소는 [a, b] 형식이며 0 ≤ a < 200, -200 < b ≤ 0 입니다.
- 주어진 모든 입력에 대해 정적분의 결과는 2^27 을 넘지 않습니다.
- 본 문제는 정답에 실수형이 포함되는 문제입니다. 입출력 예의 소수 부분 .0이 코드 실행 버튼 클릭 후 나타나는 결괏값, 기댓값 표시와 다를 수 있습니다.
입출력 예
| k | ranges | result |
|---|---|---|
| 5 | [[0,0],[0,-1],[2,-3],[3,-3]] | [33.0,31.5,0.0,-1.0] |
| 3 | [[0,0], [1,-2], [3,-3]] | [47.0,36.0,12.0] |
입출력 예 설명
입출력 예 #1
- 5로 시작하는 우박수열은 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1 입니다. 그래프에서 꺾이는 지점을 경계로 5개의 구역 넓이를 구하면 각각 10.5, 12, 6, 3, 1.5 입니다.
입출력 예 #2
- 3으로 시작하는 우박수열은 3 ⇒ 10 ⇒ 5 ⇒ 16 ⇒ 8 ⇒ 4 ⇒ 2 ⇒ 1 입니다. 그래프에서 꺾이는 지점을 경계로 3개의 구역 넓이를 구하면 각각 47, 36, 12 입니다.
나의 풀이
package programmers;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class HailSequence {
static List<Double> areas;
static List<Double> rangeWidth;
public static void calculateArea(List<int[]> list) {
for(int i = 0; i < list.size() - 1; i++) {
double square = Math.min(list.get(i)[1], list.get(i+1)[1]);
double triangle = Math.abs(((double)list.get(i+1)[1] - (double)list.get(i)[1]) / 2);
areas.add(square+triangle);
}
}
public static void getRange(List<Double> range,int x1, int x2) {
double totalArea = 0;
if(x2 < x1) totalArea = -1.0;
else {
for(int i = x1; i < x2; i++) {
totalArea += range.get(i);
}
}
rangeWidth.add(totalArea);
}
public static double[] solution(int k, int[][] ranges) {
areas = new ArrayList<>();
rangeWidth = new ArrayList<>();
int hailNumber = k;
int n = 0;
ArrayList<int[]> list = new ArrayList<>();
list.add(new int[] {n, hailNumber});
while(hailNumber != 1) {
n++;
if(hailNumber % 2 == 0) {
hailNumber /= 2;
}else {
hailNumber = (hailNumber * 3) + 1;
}
list.add(new int[] {n,hailNumber});
}
calculateArea(list);
for(int[] range : ranges) {
int a = range[0];
int b = n + range[1];
getRange(areas,a,b);
}
double[] answer = new double[ranges.length];
for(int i = 0; i < rangeWidth.size(); i++) {
answer[i] = rangeWidth.get(i);
}
System.out.println(Arrays.toString(answer));
return answer;
}
public static void main(String[] args) {
int[][] ranges = {{0,0},{1,-2},{3,-3}};
solution(3, ranges);
}
}
나의 생각
먼저 주어진 수가 5라면 1이라는 수를 만들기 위해서는 다음과 같은 과정을 거친다.
5 -> (홀수) 5 * 3 + 1 = 16 (짝수) - > 16 / 2 = 8 (짝수)
-> 8 / 2 = 4 (짝수) -> 4 / 2 = 2 (짝수) -> 2 / 2 = 1 (끝)
즉, (5,16,8,4,2,1)을 구한 뒤, 리스트에 배열값으로 추가한다.
여기서 우리가 필요한 좌표값 (x , y) 을 리스트에 넣는다.
따라서, {{0,5},{1,16},{2,8},{3,4},{4,2},{5,1}} 값이 리스트에 들어있다. 나는 위 과정을 첫번째로 생각하고, 배열로 이루어진 리스트를 하나 생성하고 초기값으로 주어지는 n, hailNumber를 리스트에 넣은 뒤 while 반복문 (탈출 조건 : hailNumber == 1 일때 )으로 hailNumber가 1이 될때까지 무한반복을 한다. 여기서 n을 넣어주는 이유는 반복을 몇 번을 진행하였는가가 여기서는 x좌표값으로 들어가기때문이다.
int hailNumber = k;
int n = 0;
ArrayList<int[]> list = new ArrayList<>();
list.add(new int[] {n, hailNumber});
while(hailNumber != 1) {
n++;
if(hailNumber % 2 == 0) {
hailNumber /= 2;
}else {
hailNumber = (hailNumber * 3) + 1;
}
list.add(new int[] {n,hailNumber});
}
calculateArea(list);위 if - else 문은 다음과 같이 삼항조건문으로 수정할 수 있다.
hailNumber = (hailNumber % 2 == 0) ? (hailNumber / 2) : (hailNumber * 3 + 1);
위 로직 결과, {{0,5},{1,16},{2,8},{3,4},{4,2},{5,1}} 값이 리스트에 담기게 된다.
다음으로 생각해야할것이 좌표값이 들어 있는 리스트로 어떻게 넓이(정적분)값을 구할 것인가?
- 나는 그래프를 보고 하나의 정점을 기준으로
삼각형하나와사각형하나로 넓이를 구할 수 있겠다고 생각하고 좌표를 기준으로 삼각형넓이와 사각형넓이를 구하여 이를 더해주었다.
public static void calculateArea(List<int[]> list) {
for(int i = 0; i < list.size() - 1; i++) {
double square = Math.min(list.get(i)[1], list.get(i+1)[1]);
double triangle = Math.abs(((double)list.get(i+1)[1] - (double)list.get(i)[1]) / 2);
areas.add(square+triangle);
}
}- 문제를 풀고 알게되었는데 위 넓이는 사다리꼴 넓이를 이용하여 쉽게 구할 수 있었다.
public static void calculateArea(List<int[]> list) {
for(int i = 0; i < list.size() - 1; i++) {
//사다리꼴 넓이로 구하는 방법
double height1 = list.get(i)[1];
double height2 = list.get(i + 1)[1];
// 사다리꼴 면적을 계산: (높이1 + 높이2) / 2 * 밑변(여기서는 1)
double trapezoidArea = (height1 + height2) / 2;
areas.add(trapezoidArea);
}
}위 결과, List areas에는 좌표를 기준으로 5개 영역의 넓이가 저장되었다.
{10.5, 12.0, 6.0, 3.0, 1.5}
이제는 이 값을 매개변수로 주어지는 x축의 범위에 따라 구간별 넓이를 다시 구할 수 있다.
문제에서 알려준 식
0 이상의 수 b에 대해 [a, -b]에 대한 정적분 결과는 x = a, x = n - b, y = 0 으로 둘러 쌓인 공간의 면적으로 정의 으로 이를 식으로 구현하면
for(int[] range : ranges) {
int a = range[0];
int b = n + range[1];
getRange(areas,a,b);
}
위에서 부터 하나씩 보면
구간 [0, 5] : 즉, 전체 구간의 넓이를 의미
구간 [0, 4] : x축을 기준으로 0 ~ 4까지의 넓이를 의미
구간 [2, 2] : 구간이 일치 하기 때문에 넓이는 0.0
구간 [3, 2] : 앞의 좌표를 x1, 뒤의 좌표를 x2라 할때 x1 > x2 조건이 참일 때
-1.0을 추가할 것 (즉, 유효하지 않은 구간임을 뜻한다)areas 리스트와 범위 좌표 a,b 값을 getRange()의 매개변수로 넣으면 다음과 같다.
public static void getRange(List<Double> range,int x1, int x2) {
double totalArea = 0.0;
if(x1 > x2) totalArea = -1.0;
else {
for(int i = x1; i < x2; i++) {
totalArea += range.get(i);
}
}
rangeWidth.add(totalArea);
}위 결과 최종적으로 우리가 필요로 하는 아래와 같은 리스트의 값을 가진다.
느낌점
문제에서 주어진 조건을 단계별로 생각하며 순차적으로 이때는 어떤값이 필요로 하고, 어떻게 가공할 것인가를 중점으로 생각하며 메서드별로 기능을 나눌려고 시도 했던것 같다.
- 메인
solution()메서드에서는 우박수열을 먼저 구하고 calculateArea()메서드에서는 좌표값에 따라 넓이를 구한 뒤getRange()메서드에서는 구간 별 넓이를 구할 수 있도록 하였다.
알고리즘 문제 특성상 메모리 사용을 중점으로 생각해야하지만, 나의 경우 불필요한 리스트(?)의 무분별한 사용으로 메모리 사용 측면에서는 효율적인 로직이 아니였다고 생각한다. 하지만, 오랜만에 생각한대로 로직을 구현하였다라는 측면에서는 만족스러운 결과였던것 같다.
