하노이의 탑
문1) 하노이 탑(Tower of Hanoi)은 퍼즐의 일종입니다. 세 개의 기둥과 이 기동에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있습니다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것입니다.
- 한 번에 하나의 원판만 옮길 수 있습니다.
- 큰 원판이 작은 원판 위에 있어서는 안됩니다.
하노이 탑의 세 개의 기둥을 왼쪽 부터 1번, 2번, 3번이라고 하겠습니다. 1번에는 n개의 원판이 있고 이 n개의 원판을 3번 원판으로 최소 횟수로 옮기려고 합니다.
1번 기둥에 있는 원판의 개수 n이 매개변수로 주어질 때, n개의 원판을 3번 원판으로 최소로 옮기는 방법을 return하는 solution를 완성해주세요.
제한사항
- n은 15이하의 자연수 입니다.
입출력 예
| n | result |
|---|---|
| 2 | [[1,2],[1,3],[2,3]] |
입출력 예 설명
입출력 에 #1
다음과 같이 옮길 수 있습니다.
나의 풀이
package programmers;
import java.util.ArrayList;
public class HanoiTop {
static ArrayList<int[]> hanoiList = new ArrayList<>();
public static ArrayList<int[]> move(int n, int from, int to) {
if(n > 1) {
move(n - 1, from, 6 - from - to);
}
hanoiList.add(new int[] {from,to});
if(n > 1) {
move(n - 1, 6 - from - to, to);
}
return hanoiList;
}
public static int[][] solution(int n) {
hanoiList.clear();
move(n,1,3);
int[][] answer = new int[hanoiList.size()][2];
for(int i = 0; i < hanoiList.size(); i++) {
answer[i] = hanoiList.get(i);
}
return answer;
}
public static void main(String[] args) {
solution(2);
}
}
두 원 사이의 정수 쌍
문2) x축과 y축으로 이루어진 2차원 직교 좌표계에 중심이 원점인 서로 다른 크기의 원이 두 개 주어집니다. 반지름을 나타내는 두 정수 r1, r2가 매개변수로 주어질 때, 두 원 사이의 공간에 x좌표와 y좌표가 모두 정수인 점의 개수를 return하도록 solution 함수를 완성해주세요.
※ 각 원 위의 점도 포함하여 셉니다.
제한사항
1 ≤ r1 < r2 ≤ 1,000,000
입출력 예
| r1 | r2 | result |
|---|---|---|
| 2 | 3 | 20 |
입출력 예 설명
그림과 같이 정수 쌍으로 이루어진 점은 총 20개 입니다.
나의 풀이
package programmers;
public class PairOfIntegersBetweenTwoCircles {
public static long solution(int r1, int r2) {
long answer = 0;
for (int i = 1; i <= r2; i++) {
int start = (int) Math.ceil(Math.sqrt((long) r1 * r1 - (long) i * i));
int end = (int) Math.floor(Math.sqrt((long) r2 * r2 - (long) i * i));
System.out.printf("start: %d, end: %d\n" , start, end);
answer += end - start + 1;
}
return answer * 4;
}
public static void main(String[] args) {
solution(2, 3);
}
}
package programmers;
public class PairOfIntegersBetweenTwoCircles {
public static long solution(int r1, int r2) {
long count = 0;
for(long x = -r2; x <= r2; x++) {
long yUpper = (long)Math.sqrt((long)r2*r2 - x*x);
long yLower = (long)Math.ceil(Math.sqrt((long)r1*r1 - x*x));
if(yLower <= yUpper) {
count += (yUpper - yLower + 1);
}
if (x == 0) {
count -= (yUpper - yLower + 1);
}
}
return count * 2;
}
public static void main(String[] args) {
solution(2, 3);
}
}
숫자 카드 나누기
문3) 철수와 영희는 선생님으로부터 숫자가 하나씩 적힌 카드들을 절반씩 나눠서 가진 후, 다음 두 조건 중 하나를 만족하는 가장 큰 양의 정수 a의 값을 구하려고 합니다.
- 철수가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고 영희가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
- 영희가 가진 카드들에 적힌 모든 숫자를 나눌 수 있고, 철수가 가진 카드들에 적힌 모든 숫자들 중 하나도 나눌 수 없는 양의 정수 a
예를 들어, 카드들에 10, 5, 20, 17이 적혀 있는 경우에 대해 생각해 봅시다. 만약, 철수가 [10, 17]이 적힌 카드를 갖고, 영희가 [5, 20]이 적힌 카드를 갖는다면 두 조건 중 하나를 만족하는 양의 정수 a는 존재하지 않습니다. 하지만, 철수가 [10, 20]이 적힌 카드를 갖고, 영희가 [5, 17]이 적힌 카드를 갖는다면, 철수가 가진 카드들의 숫자는 모두 10으로 나눌 수 있고, 영희가 가진 카드들의 숫자는 모두 10으로 나눌 수 없습니다. 따라서 철수와 영희는 각각 [10, 20]이 적힌 카드, [5, 17]이 적힌 카드로 나눠 가졌다면 조건에 해당하는 양의 정수 a는 10이 됩니다.
철수가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayA와 영희가 가진 카드에 적힌 숫자들을 나타내는 정수 배열 arrayB가 주어졌을 때, 주어진 조건을 만족하는 가장 큰 양의 정수 a를 return하도록 solution 함수를 완성해 주세요. 만약, 조건을 만족하는 a가 없다면, 0을 return 해 주세요.
제한사항
- 1 ≤ arrayA의 길이 = arrayB의 길이 ≤ 500,000
- 1 ≤ arrayA의 원소, arrayB의 원소 ≤ 100,000,000
- arrayA와 arrayB에는 중복된 원소가 있을 수 있습니다.
입출력 예
| arrayA | arrayB | result |
|---|---|---|
| [10,17] | [5,20] | 0 |
| [10,20] | [5,17] | 10 |
| [14,35,119] | [18,30,102] | 7 |
입출력 예 설명
입출력 예 #3
- 철수가 가진 카드에 적힌 숫자들은 모두 3으로 나눌 수 없고, 영희가 가진 카드에 적힌 숫자는 모두 3으로 나눌 수 있습니다. 따라서 3은 조건에 해당하는 양의 정수입니다. 하지만, 철수가 가진 카드들에 적힌 숫자들은 모두 7로 나눌 수 있고, 영희가 가진 카드들에 적힌 숫자는 모두 7로 나눌 수 없습니다. 따라서 최대값인 7을 return 합니다.
나의 풀이
package programmers;
public class NumberCardDivision {
public static boolean notDivisible(int[] arr, int num){
for(int n : arr)
if(n % num == 0)
return false;
return true;
}
public static int gcd(int a, int b){
if(a % b == 0)return b;
return gcd(b, a % b);
}
public static int solution(int[] arrayA, int[] arrayB) {
int answer = 0;
int gcdA = arrayA[0];
int gcdB = arrayB[0];
for(int i =1; i< arrayA.length;i++){
gcdA = gcd(gcdA, arrayA[i]);
gcdB = gcd(gcdB, arrayB[i]);
}
if(notDivisible(arrayB, gcdA))
if(answer < gcdA)
answer = gcdA;
if(notDivisible(arrayA, gcdB))
if(answer < gcdB)
answer = gcdB;
return answer;
}
public static void main(String[] args) {
int[] arrayA = {10,17};
int[] arrayB = {5,20};
solution(arrayA, arrayB);
}
}
조이스틱
문4) 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다.
ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA
조이스틱을 각 방향으로 움직이면 아래와 같습니다.
▲ - 다음 알파벳
▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로)
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)예를 들어 아래의 방법으로 "JAZ"를 만들 수 있습니다.
- 첫 번째 위치에서 조이스틱을 위로 9번 조작하여 J를 완성합니다.
- 조이스틱을 왼쪽으로 1번 조작하여 커서를 마지막 문자 위치로 이동시킵니다.
- 마지막 위치에서 조이스틱을 아래로 1번 조작하여 Z를 완성합니다.
따라서 11번 이동시켜 "JAZ"를 만들 수 있고, 이때가 최소 이동입니다.만들고자 하는 이름 name이 매개변수로 주어질 때, 이름에 대해 조이스틱 조작 횟수의 최솟값을 return 하도록 solution 함수를 만드세요.
제한사항
name은 알파벳 대문자로만 이루어져 있습니다.
name의 길이는 1 이상 20 이하입니다.
입출력 예
| name | return |
|---|---|
| "JEROEN" | 56 |
| "JAN" | 23 |
나의 풀이
package programmers;
public class Joystick {
public static int solution(String name) {
int answer = 0;
int nameLength = name.length();
int move = nameLength - 1;
for(int i = 0; i < nameLength; i++) {
int upDown = Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);
answer += upDown;
int next = i + 1;
while(next < nameLength && name.charAt(next) == 'A') {
next++;
}
int leftMove = i + i + nameLength - next;
int rightMove = (nameLength - next) * 2 + i;
move = Math.min(move, Math.min(leftMove, rightMove));
}
answer += move;
return answer;
}
public static void main(String[] args) {
solution("BBBBAAAABA");
}
}
나의 생각
문제를 한참봐도 이게 무슨말인가... 두번, 세번 문제를 보았던거 같다.
이 문제의 핵심은, 알파벳을 담당하는 상,하 키보드, 커서의 위치를 담당하는 좌,우 키보드 그리고 조이스틱의 조작을 최소한으로 하면서 이름을 만드는 것이다.
▲▼ 키보드
알파벳을 보면 A ~ Z 까지 26개의 알파벳이 존재한다.
▲ A(0) ▼
B(1) Z(1)
C(2) Y(2)
D(3) X(3)
E(4) W(4)
F(5) V(5)
G(6) U(6)
H(7) T(7)
I(8) S(8)
J(9) R(9)
K(10) Q(10)
L(11) P(11)
M(12) O(12)
N(13)구현 로직
for(int i = 0; i < nameLength; i++) {
int upDown = Math.min(name.charAt(i) - 'A', 'Z' - name.charAt(i) + 1);
answer += upDown;
}위 로직은 name.charAt(i)에서 A 를 뺀것과, Z - name.charAt(i) 값을 비교하여 더 작은 값을 answer에 추가함으로서 비교적 쉽게 구할 수 있다.
◀︎ ▶︎ 키보드
◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서)
▶ - 커서를 오른쪽으로 이동 (마지막 위치에서 오른쪽으로 이동하면 첫 번째 문자에 커서)를 예를 들어보자.
1.BAAAAABBB ( → ) : 오른쪽 방향으로 커서를 이동
2. 오른쪽 방향으로 이동하다 A를 만나면 다시 시작점으로 와서 왼쪽방향으로 움직일 때
(시작지점에서 ◀︎ 커서를 누르면 마지막 문자에 커서가 표시)
3. 시작과 동시(시작점)에 왼쪽방향으로 움직이다 A를 만나면 다시 오른쪽 방향으로 움직일 때
( 마지막 문자에 커서를 두고 ▶︎ 커서를 누르면 첫 번째 문자에 커서가 표시)나는 1, 2번까지는 생각했는데 3번을 생각하지 못했다. (이해하는데 상당한 시간을 소요했다)
를 세 가지 방법으로 조이스틱을 최소로 움직일 수 있는지 확인해보자.
1. 최악의 경우 전체 name - 1 만큼 우 (▶︎) 로 이동
2. 오른쪽 방향에서 왼쪽 방향으로 움직일 때
B (다음 A를 만나기때문에 ) ← B ← B ← B
3. 시작과 동시에 왼쪽 방향으로 움직일 때
← B ← B ← B → → → B- 1번의 경우
B글자 (4번) 을 만드는데 움직인 조이스틱 횟수 : 4회
▶︎를 전체 길이 - 1 만큼 움직인 조이스틱 횟수 : 8 회
총 12회
- 2번의 경우
B글자 (4번) 을 만드는데 움직인 조이스틱 횟수 : 4회
화살표 횟수 : 3회
총 7회
- 3번의 경우
B글자 (4번) 을 만드는데 움직인 조이스틱 횟수 : 4회
화살표 횟수 : 6번
총 10회
따라서, 1,2,3번의 모든 경우의 수 중 최소값 7을 반환
구현 로직
int move = nameLength - 1;
for(int i = 0; i < nameLength; i++) {
int next = i + 1;
while(next < nameLength && name.charAt(next) == 'A') {
next++;
}
int leftMove = i + i + nameLength - next;
int rightMove = (nameLength - next) * 2 + i;
move = Math.min(move, Math.min(leftMove, rightMove));
}
answer += move;
int leftMove = i + i + nameLength - next
이 변수는 오른쪽으로 이동한 후, 다시 왼쪽으로 이동하는 전체 이동거리를 계산
i: 현재 위치에서 오른쪽으로 이동한 거리, 이 거리를 왕복해야하므로i+i또는i * 2nameLength - next: A가 아닌 문자를 찾아 이동한 거리int rightMove = (nameLength - next) * 2 + i
이 변수는 왼쪽으로 이동한 후, 다시 오른쪽으로 이동하는 전체 거리를 계산
(nameLength - next) * 2: 왼쪽으로 이동하여 A가 아닌 문자를 찾고, 그 위치에서 다시 오른쪽으로 이동하는 거리, 이 거리는 왕복해야하므로* 2i: 왼쪽으로 이동한 후, 다시 오른쪽으로 이동하는 거리
leftMove와rightMove는 각각 오른쪽과 왼쪽으로 이동한 후, 반대 방향으로 이동하는 전체 이동 거리를 계산함. 이 두 변수를 이용하여 각 경우의 수에 대한 최소 이동 거리를 찾음. 그리고 이 중 최소값을 찾아서 최종적으로 필요한 최소 조이스틱 이동 횟수를 계산
쿼드압축 후 개수 세기
문5) 0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.
- 당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
2 .만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다. - 그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.
arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.
제한사항
- arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
- arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
- arr의 각 행에 있는 모든 값은 0 또는 1 입니다.
입출력 예
| arr | result |
|---|---|
[[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] | [4,9] |
[[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] | [10,15] |
입출력 예 설명
입출력 예 #1
다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.
최종 압축 결과에 0이 4개, 1이 9개 있으므로, [4,9]를 return 해야 합니다.
입출력 예 #2
다음 그림은 주어진 arr을 압축하는 과정을 나타낸 것입니다.
최종 압축 결과에 0이 10개, 1이 15개 있으므로, [10,15]를 return 해야 합니다.
나의 풀이
package programmers;
public class QuadCompression {
static int zeroCnt = 0;
static int oneCnt = 0;
public static void compress(int[][] arr, int x, int y, int length) {
int value = arr[x][y];
boolean compressible = true;
for(int i = x; i < x + length; i++) {
for(int j = y; j < y + length; j++) {
if(arr[i][j] != value) {
compressible = false;
break;
}
}
if(!compressible) break;
}
if(compressible) {
if(value == 0) zeroCnt++;
else oneCnt++;
}else {
int half = length / 2;
compress(arr, x, y, half);
compress(arr, x, y + half, half);
compress(arr, x + half, y, half);
compress(arr, x + half, y + half, half);
}
}
public static int[] solution(int[][] arr) {
compress(arr,0,0, arr.length);
return new int[] {zeroCnt, oneCnt};
}
public static void main(String[] args) {
int[][] arr = {{1,1,0,0},{1,0,0,0},{1,0,0,1},{1,1,1,1}};
solution(arr);
}
}
나의 생각
재귀적 접근 : 주어진 영역이 압축 가능한지 확인하는 것은 재귀적으로 수행
만약, 압축이 가능하다면 해당 영역을 압축하고, 그렇지 않다면
다시 4개의 작은 영역으로 분할하여 각 영역에 대해 동일한 판별
과정을 수행할 것
기저 조건 설정 : 분할의 최소 단위는 n = 1의 영역. 해당 칸의 값이 0이면 0으로, 1이면 1로 압축
정리 :
1. 주어진 n x n 크기의 2차원ㅂ 배열을 확인하여 해당 영역의 모든 값이 0 또는 1인지 판별
2. 모든 값이 0 또는 1로 같다면 해당 영역은 압축 가능
3. 압축이 불가능한 경우, 해당 영역을 4개의 작은 영역으로 분할
4. 분할된 각 영역에 대해 동일한 판별 및 압축 과정을 재귀적으로 수행
5. 최종적으로 각 영역을 최대한 압축하여 결과를 반환compress(재귀함수) 호출
int value = arr[x][y];
boolean compressible = true;
for(int i = x; i < x + length; i++) {
for(int j = y; j < y + length; j++) {
if(arr[i][j] != value) {
compressible = false;
break;
}
}
if(!compressible) break;
}처음 compress(재귀함수)가 호출되면
int value = arr[0][0] 으로 1이된다.
4x4 맵을 이중for문으로 돌면서 1이랑 다른 값이 있는지 검출하고, 다른값이 존재한다면
더이상 for문을 순회할 필요가 없기때문에 빠져나온다.
즉, 압축이 불가능한 상태를 의미한다.if(compressible) {
if(value == 0) zeroCnt++;
else oneCnt++;
}else {
int half = length / 2;
compress(arr, x, y, half);
compress(arr, x, y + half, half);
compress(arr, x + half, y, half);
compress(arr, x + half, y + half, half);
}
4 x 4 map을 압축할 수 없기때문에, 2 x 2 크기 네개로 분할을 한다
예를들어, length = 4면, half = 2가 되고,
compress(arr, 0, 0, 2);
compress(arr, 0, 2, 2);
compress(arr, 2, 0, 2);
compress(arr, 2, 2, 2);
를 재귀호출하고
int value = arr[x][y]; 에서
1사분면 value : arr[0][0] = 1
2사분면 value : arr[0][2] = 0
3사분면 value : arr[2][0] = 1
4사분면 value : arr[2][2] = 0
1,2,3,4 분면을 다시 압축시도하여 압축이 되면 0 또는 1로 압축을 하고 (여기서는 2사분면만 압축)
length 2에서 half = 1이 되고,
1사분면은
시작 좌표 : (x = 0 , y = 0)
compress(arr, 0, 0, 1)
compress(arr, 0, 1, 1)
compress(arr, 1, 0, 1)
compress(arr, 1, 1, 1)
3사분면은
시작 좌표 : (x = 2 , y = 0)
compress(arr, 2, 0, 1)
compress(arr, 2, 1, 1)
compress(arr, 3, 0, 1)
compress(arr, 3, 1, 1)
4사분면은
시작 좌표 : (x = 2 , y = 2)
compress(arr, 2, 2, 1)
compress(arr, 2, 3, 1)
compress(arr, 3, 2, 1)
compress(arr, 3, 3, 1)
최종적으로, half = 1 이 되면 모든 compressible값이 true가 되기때문에
if(compressible) {
if(value == 0) zeroCnt++;
else oneCnt++;
}로직에 의해 클래스의 멤버 변수로 선언된 zeroCnt, oneCnt 결과가 solution() 메서드에서 return new int[] {zeroCnt, oneCnt} 로 호출됨
