124 나라의 숫자
문1) 124 나라가 있습니다. 124 나라에서는 10진법이 아닌 다음과 같은 자신들만의 규칙으로 수를 표현합니다.
- 124 나라에는 자연수만 존재합니다.
- 124 나라에는 모든 수를 표현할 때 1,2,4 만 사용합니다.
예를 들어서 124 나라에서 사용하는 숫자는 다음과 같이 변환됩니다.
| 10진법 | 124 나라 | 10진법 | 124 나라 |
|---|---|---|---|
| 1 | 1 | 6 | 14 |
| 2 | 2 | 7 | 21 |
| 3 | 4 | 8 | 22 |
| 4 | 11 | 9 | 24 |
| 5 | 12 | 10 | 41 |
자연수 n이 매개변수로 주어질 때, n을 124 나라에서 사용하는 숫자로 바꾼 값을 return 하도록 solution 함수를 완성해 주세요.
제한사항
- n은 50,000,000 이하의 자연수 입니다.
입출력 예
| n | result |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 4 |
| 4 | 11 |
나의 풀이
package programmers;
public class Country124 {
public static String solution(int n) {
String answer = "";
String[] numbers = {"4","1","2"};
while(n > 0) {
int remainder = n % 3;
n /= 3;
if(remainder == 0) n--;
answer = numbers[remainder] + answer;
}
return answer;
}
public static void main(String[] args) {
solution(500);
}
}
연속된 부분 수열의 합
문2) 비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.
- 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.
- 부분 수열의 합은 k입니다.
- 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.
- 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.
수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution 함수를 완성해주세요. 이때 수열의 인덱스는 0부터 시작합니다.
제한사항
- 5 ≤ sequence의 길이 ≤ 1,000,000
- 1 ≤ sequence의 원소 ≤ 1,000
- sequence는 비내림차순으로 정렬되어 있습니다.
- 5 ≤ k ≤ 1,000,000,000
- k는 항상 sequence의 부분 수열로 만들 수 있는 값입니다.
입출력 예
| sequence | k | result |
|---|---|---|
| [1,2,3,4,5] | 7 | [2,3] |
| [1,1,1,2,3,4,5] | 5 | [6,6] |
| [2,2,2,2,2] | 6 | [0,2] |
입출력 예 설명
입출력 예 #1
- [1, 2, 3, 4, 5]에서 합이 7인 연속된 부분 수열은 [3, 4]뿐이므로 해당 수열의 시작 인덱스인 2와 마지막 인덱스 3을 배열에 담아 [2, 3]을 반환합니다.
입출력 예 #2
- [1, 1, 1, 2, 3, 4, 5]에서 합이 5인 연속된 부분 수열은 [1, 1, 1, 2], [2, 3], [5]가 있습니다. 이 중 [5]의 길이가 제일 짧으므로 해당 수열의 시작 인덱스와 마지막 인덱스를 담은 [6, 6]을 반환합니다.
입출력 예 #3
- [2, 2, 2, 2, 2]에서 합이 6인 연속된 부분 수열은 [2, 2, 2]로 3가지 경우가 있는데, 길이가 짧은 수열이 여러 개인 경우 앞쪽에 나온 수열을 찾으므로 [0, 2]를 반환합니다.
나의 풀이
#1
package programmers;
import java.util.Arrays;
public class SumOfConsecutiveSubsequences {
public static int[] solution(int[] sequence, int k) {
int[] answer = new int[2];
int left = 0, right = 0;
int sum =sequence[0];
int minLength = Integer.MAX_VALUE;
while (right < sequence.length) {
if (sum == k) {
if (right - left < minLength) {
answer[0] = left;
answer[1] = right;
minLength = right - left;
}
sum -= sequence[left];
left++;
} else if (sum < k) {
right++;
if (right < sequence.length) {
sum += sequence[right];
}
} else {
sum -= sequence[left];
left++;
if (left > right && left < sequence.length) {
right = left;
sum = sequence[left];
}
}
}
System.out.println(Arrays.toString(answer));
return answer;
}
public static void main(String[] args) {
int[] sequence = {1,1,1,2,3,4,5};
solution(sequence, 5);
}
}
#2
package programmers;
public class SumOfConsecutiveSubsequences {
public static int[] solution(int[] sequence, int k) {
int[] answer = new int[2];
int start = 0, end = 0;
int sum = 0, len = Integer.MAX_VALUE;
while(end < sequence.length) {
sum += sequence[end];
end++;
while( sum > k) {
sum -= sequence[start];
start++;
}
if(sum == k && end - start < len) {
len = end - start;
answer[0] = start;
answer[1] = end - 1;
}
}
return answer;
}
public static void main(String[] args) {
int[] sequence = {1,1,1,2,3,4,5};
solution(sequence, 5);
}
}
삼각 달팽이
문3) 정수 n이 매개변수로 주어집니다. 다음 그림과 같이 밑변의 길이와 높이가 n인 삼각형에서 맨 위 꼭짓점부터 반시계 방향으로 달팽이 채우기를 진행한 후, 첫 행부터 마지막 행까지 모두 순서대로 합친 새로운 배열을 return 하도록 solution 함수를 완성해주세요.
제한사항
- n은 1 이상, 1,000 이하입니다.
입출력 예
| n | result |
|---|---|
| 4 | [1,2,9,3,10,8,4,5,6,7] |
| 5 | [1,2,12,3,13,11,4,14,15,10,5,6,7,8,9] |
| 6 | [1,2,15,3,16,14,4,17,21,13,5,18,19,20,12,6,7,8,9,10,11] |
나의 풀이
잘못 생각한 로직
package programmers;
import java.util.Arrays;
public class TriangleSnail {
static int length = 0;
public static int triangle(int n) {
if(n == 1) {
return 1;
}else {
return triangle(n-1) + n;
}
}
public static int[] solution(int n) {
int[] answer = new int[triangle(n)];
triangle(n);
for(int i = 1; i <= answer.length; i++) {
answer[i-1] = i;
}
System.out.println(Arrays.toString(answer));
return answer;
}
public static void main(String[] args) {
solution(4);
}
}
해결한 로직
package programmers;
import java.util.Arrays;
public class TriangleSnail {
public static int[] solution(int n) {
int[][] triangle = new int[n][n];
int[] answer;
int x = -1;
int y = 0;
int number = 1;
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
if(i % 3 == 0) x++;
else if (i % 3 == 1) y++;
else if (i % 3 == 2) {x--; y--;};
triangle[x][y] = number++;
}
}
answer = new int[number - 1];
int idx = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(triangle[i][j] == 0) continue;
answer[idx++] = triangle[i][j];
}
}
return answer;
}
public static void main(String[] args) {
solution(4);
}
}
나의 생각
처음 문제를 보자마자 n = 1, n = 2, n = 3, n = 4... 뭔가 규칙이 있음을 생각하였다. ↓,→,↖︎ 순서로 이동하면서 삼각달팽이의 총 길이가 이 문제의 핵심이라고 생각하여 규칙을 먼저 구하였다.
삼각 달팽이의 길이
n = 1 , length = 1
n = 2 , length = 3
n = 3 , length = 6
n = 4 , length = 10
n = 5 , length = 15
n = 6 , length = 21위 내용을 바탕으로 점화식을 구하면 다음과 같다.
문제를 풀면서 알게됐는데, 이 수열은 이전 항들의 합으로 표현되는 수열로서 삼각수(Triangle numbers)로 알려진 수열의 일반항은 다음과 같았다.
내가 처음 풀었던 식을 바탕으로 문제를 접근한 것이 내가 처음 문제를 풀기 시작한 로직이였으며
int[] answer = new int[triangle(n)] 로 배열의 길이는 구했지만, 1 ~ n까지 배열에 문제에서 원하는 규칙대로 숫자를 넣는 로직을 구현할 수 없었다. 그래서 문제를 처음부터 다시 접근하여, 아래와 같은 로직의 순서대로 구현해보기로 하였다.
1. 초기화 : n * n 크기의 2차원 배열을 생성하고, 모든 값을 0으로 초기화
-> 값이 변경되지 않은 배열 요소는 0을 유지
2. 방향 설정 : 배열을 채우는 방향이 아래 -> 오른쪽 -> 대각선 위 순서
3. 배열 채우기 : 순회하며 배열을 채우며, 현재 채우려는 방향으로 쭉 이동하다가
범위를 벗어나거나 이미 채워진(0이 아닌) 위치를 만나면 방향을 바꾸고 다시 진행
4. 1차원 배열로 변환 : 2차원 배열을 1차원 배열로 변환
- 모든 요소를 순회하며 0이 아닌 값만 1차원 배열에 넣음int[][] triangle = new int[n][n];
int[] answer;
int x = -1; // for문 순회하면서 바로 0으로 값이 증가하기 때문에 초기값을 -1로 설정
int y = 0;
int number = 1; // 숫자가 1부터 시작하기 때문에
위 그림을 2차원 배열로 생각하여 아래와 같이 표현할 수 있다.
핵심 로직 1
for(int i = 0; i < n; i++) {
for(int j = i; j < n; j++) {
if(i % 3 == 0) x++;
else if (i % 3 == 1) y++;
else if (i % 3 == 2) {x--; y--;};
triangle[x][y] = number++;
}
}이 로직이 어떻게 작동하는가를 보면
i = 0 일때, 내부 루프는 n번 실행
i = 1 일때, 내부 루프는 n-1번 실행
i = 2 일때, 내부 루프는 n-2번 실행
i = n-1 일때, 내부 루프는 1번 실행
따라서 전체 실행 횟수는
n + (n - 1) + (n - 2) + ... + 2 + 1로 등차 수열의 합 공식을 사용하면
내가 구하고자하는 배열의 크기(number)를 자연스럽게 구할수 있다.
배열의 좌표[x][y]
2차원 배열에 들어 있는 값
answer = new int[number - 1];
int idx = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(triangle[i][j] == 0) continue;
answer[idx++] = triangle[i][j];
}
}위의 로직은 2차원 배열을 1차원 배열에 넣는 로직을 의미하며, answer 배열의 크기는 number - 1로 배열의 idx 시작이 0번 부터 시작이기때문에, 크기에 -1을 해줘야한다. 2차원 배열에서 0의 값이 있으면 continue로 건너뛰고, 그나머지는 idx++로 인덱스를 하나씩 증가시켜가며 answer 1차원 배열에 2차원배열 값을 넣는다.
최종적으로 우리가 원하는 값의 형태를 구할 수 있다.
두 큐 합 같게 만들기
문4) 길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.
큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4]가 되며, 이어서 5를 insert하면 [2, 3, 4, 5]가 됩니다.
다음은 두 큐를 나타내는 예시입니다.
queue1 = [3, 2, 7, 2]
queue2 = [4, 6, 5, 1]두 큐에 담긴 모든 원소의 합은 30입니다. 따라서, 각 큐의 합을 15로 만들어야 합니다. 예를 들어, 다음과 같이 2가지 방법이 있습니다.
- queue2의 4, 6, 5를 순서대로 추출하여 queue1에 추가한 뒤, queue1의 3, 2, 7, 2를 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [4, 6, 5], queue2는 [1, 3, 2, 7, 2]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 7번 수행합니다.
- queue1에서 3을 추출하여 queue2에 추가합니다. 그리고 queue2에서 4를 추출하여 queue1에 추가합니다. 그 결과 queue1은 [2, 7, 2, 4], queue2는 [6, 5, 1, 3]가 되며, 각 큐의 원소 합은 15로 같습니다. 이 방법은 작업을 2번만 수행하며, 이보다 적은 횟수로 목표를 달성할 수 없습니다.
따라서 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수는 2입니다.
길이가 같은 두 개의 큐를 나타내는 정수 배열 queue1, queue2가 매개변수로 주어집니다. 각 큐의 원소 합을 같게 만들기 위해 필요한 작업의 최소 횟수를 return 하도록 solution 함수를 완성해주세요. 단, 어떤 방법으로도 각 큐의 원소 합을 같게 만들 수 없는 경우, -1을 return 해주세요.
제한사항
- 1 ≤ queue1의 길이 = queue2의 길이 ≤
- 1 ≤ queue1의 원소, queue2의 원소 ≤
- 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요합니다.
입출력 예
| queue1 | queue2 | result |
|---|---|---|
| [3,2,7,2] | [4,6,5,1] | 2 |
| [1,2,1,2] | [1,10,1,2] | 7 |
| [1,1] | [1,5] | -1 |
입출력 예 설명
입출력 예 #2
두 큐에 담긴 모든 원소의 합은 20입니다. 따라서, 각 큐의 합을 10으로 만들어야 합니다. queue2에서 1, 10을 순서대로 추출하여 queue1에 추가하고, queue1에서 1, 2, 1, 2와 1(queue2으로부터 받은 원소)을 순서대로 추출하여 queue2에 추가합니다. 그 결과 queue1은 [10], queue2는 [1, 2, 1, 2, 1, 2, 1]가 되며, 각 큐의 원소 합은 10으로 같습니다. 이때 작업 횟수는 7회이며, 이보다 적은 횟수로 목표를 달성하는 방법은 없습니다. 따라서 7를 return 합니다.
나의 풀이
package programmers;
import java.util.LinkedList;
import java.util.Queue;
public class SumOfTwoQueues {
public static int solution(int[] queue1, int[] queue2) {
Queue<Integer> q1 = new LinkedList<>();
Queue<Integer> q2 = new LinkedList<>();
int length = queue1.length;
long sum1 = 0;
long sum2 = 0;
long target = (sum1 + sum2) / 2 ;
int answerCnt = 0;
for(int i = 0; i < length; i++) {
sum1 += queue1[i];
sum2 += queue2[i];
q1.offer(queue1[i]);
q2.offer(queue2[i]);
}
while(sum1 != sum2) {
if(answerCnt >= length * 4) return -1;
if(sum1 > sum2) {
sum1 -= q1.peek();
q2.offer(q1.peek());
sum2 += q1.poll();
}else {
sum2 -= q2.peek();
q1.offer(q2.peek());
sum1 += q2.poll();
}
answerCnt++;
}
return answerCnt;
}
public static void main(String[] args) {
int[] queue1 = {1,2,1,2};
int[] queue2 = {1,10,1,2};
solution(queue1, queue2);
}
}
무인도 여행
문5) 메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.
지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.
제한사항
- 3 ≤ maps의 길이 ≤ 100
- 3 ≤ maps[i]의 길이 ≤ 100
- maps[i]는 'X' 또는 1 과 9 사이의 자연수로 이루어진 문자열입니다.
- 지도는 직사각형 형태입니다.
입출력 예
| maps | result |
|---|---|
| ["X591X","X1X5X","X231X", "1XXX1"] | [1,1,27] |
| ["XXX","XXX","XXX"] | [-1] |
입출력 예 설명
입출력 예 #1
위 문자열은 다음과 같은 지도를 나타냅니다.
연결된 땅들의 값을 합치면 다음과 같으며
이를 오름차순으로 정렬하면 [1,1,27]이 됩니다.
입출력 예 #2
위 문자열은 다음과 같은 지도를 나타냅니다.
섬이 존재하지 않기 때문에 -1을 배열에 담아 반환합니다.
나의 풀이
package programmers;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class DesertIslandTrip {
static int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
static boolean[][] visited;
public static List<Integer> bfs(int i, int j, String[][] island){
Queue<int[]> queue = new LinkedList<>();
queue.add(new int[] {i,j});
visited[i][j] = true;
int sum = island[i][j].equals("X") ? 0 : Integer.parseInt(island[i][j]);
while(!queue.isEmpty()) {
int[] current = queue.poll();
for(int[] dir : dirs) {
int ni = current[0] + dir[0];
int nj = current[1] + dir[1];
if (ni >= 0 && ni < island.length && nj >= 0 && nj < island[0].length &&
!visited[ni][nj] && !island[ni][nj].equals("X")) {
queue.add(new int[] {ni, nj});
visited[ni][nj] = true;
sum += Integer.parseInt(island[ni][nj]);
}
}
}
if(sum == 0) {
return Collections.emptyList();
}else {
return Collections.singletonList(sum);
}
}
public static int[] solution(String[] maps) {
String[][] island = new String[maps.length][maps[0].length()];
visited = new boolean[maps.length][maps[0].length()];
List<Integer> results = new ArrayList<>();
for(int i = 0; i < maps.length; i++){
for(int j = 0; j < maps[i].length(); j++) {
island[i][j] = maps[i].split("")[j];
}
}
for(int i = 0; i < island.length; i++) {
for(int j = 0; j < island[0].length; j++) {
if(!visited[i][j] && !island[i][j].equals("X")) {
results.addAll(bfs(i, j, island));
}
}
}
Collections.sort(results);
System.out.println(results);
if (results.size() == 0) {
return new int[]{-1};
} else {
return results.stream().mapToInt(Integer::intValue).toArray();
}
}
public static void main(String[] args) {
String[] maps = {"X591X","X1X5X","X231X", "1XXX1"};
solution(maps);
}
}
/*
* 1. 지도의 각 칸을 순
* 2. 현재 칸이 'X'가 아니고 아직 방문하지 않은 칸이라면 BFS를 시작
* 3. 큐(Queue)에 현재 칸을 넣고, 해당 칸을 방문했다고 표시
* 4. 큐가 빌 떄까지 다음을 반복
* - 큐에서 칸을 하나
* - 해당 의 숫자를 누적 합계에 더
* - 인전합 네 방향(상, 하, 좌, 우)를 확인
* 5.BFS가 끝나면, 누적 합계를 결과 리스트에 추
*/