문제1) 분수의 덧셈 - 최대공약수 구하기
첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.
제한사항
0 <numer1, denom1, numer2, denom2 < 1,000
입출력 예
| numer1 | denom1 | numer2 | denom2 | result |
| 1 | 2 | 3 | 4 | [5, 4] |
| 9 | 2 | 1 | 3 | [29, 6] |
입출력 예 설명
입출력 예 #1
1 / 2 + 3 / 4 = 5 / 4입니다. 따라서 [5, 4]를 return 합니다.
입출력 예 #2
9 / 2 + 1 / 3 = 29 / 6입니다. 따라서 [29, 6]을 return 합니다.
내가 푼 풀이)
import java.math.BigInteger;
class Solution {
public int[] solution(int numer1, int denom1, int numer2, int denom2) {
int son = numer1 * denom2 + numer2 * denom1;
int mother = denom1 * denom2;
int gcd = BigInteger.valueOf(son).gcd(BigInteger.valueOf(mother)).intValue();
return new int[]{son/gcd,mother/gcd};
}
}
시간복잡도 :
자바에서 int 타입은 크기 제한이 있기 때문에 매우 큰 수는 BigInteger를 사용합니다. 일반적으로 BigInteger를 사용한 수는 시간 복잡도가 O(n^2)이지만, 이 문제에서는 숫자의 크기가 매우 작은편에 속하기 때문에 O(log(min(son, mother)))입니다.
그런데 son의 값과 mother의 값은 int 범위안에 있으므로 실질적으로는 O(1)입니다.
공간복잡도 :
각 지역변수 son, mother,gcd는 크기는 모두 O(1)이며 BigInteger.valueOf()를 두번 사용하므로 2개 객체를 생성하지만 내부의 값이 매우 작으므로 공간복잡도는 O(1)이 됩니다. 또한 intValue()도 공간복잡도는 O(1)입니다.
더 효율적인 풀이)
class Solution {
private int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
public int[] solution(int numer1, int denom1, int numer2, int denom2) {
int son = numer1 * denom2 + numer2 * denom1;
int mother = denom1 * denom2;
int gcd = gcd(son, mother);
return new int[]{son / gcd, mother / gcd};
}
}
시간복잡도 :
이 문제에서는 숫자의 크기가 매우 작은편에 속하기 때문에 gcd를 직접 구할 수도 있습니다. 이때 시간복잡도는 동일하게 O(log(min(son, mother)))입니다. 그런데 son의 값과 mother의 값은 int 범위안에 있으므로 실질적으로는 O(1)입니다.
단지 더 효율적인 이유는 BigInteger 객체를 생성하지않고 모듈을 불러오지않기 때문에 더 효율적입니다.
공간복잡도 :
공간복잡도도 동일하지만 시간복잡도와 마찬가지로 BigInteger 객체를 생성하지 않고 모듈을 불러오지 않기 때문에 더 효율적입니다.
문제2) 배열만들기
정수 l과 r이 주어졌을 때, l 이상 r이하의 정수 중에서 숫자 "0"과 "5"로만 이루어진 모든 정수를 오름차순으로 저장한 배열을 return 하는 solution 함수를 완성해 주세요.
만약 그러한 정수가 없다면, -1이 담긴 배열을 return 합니다.
제한사항
1 ≤ l ≤ r ≤ 1,000,000
입출력 예
| l | r | result |
| 5 | 555 | [5, 50, 55, 500, 505, 550, 555] |
| 10 | 20 | [-1] |
입출력 예 설명
입출력 예 #1
5 이상 555 이하의 0과 5로만 이루어진 정수는 작은 수부터 5, 50, 55, 500, 505, 550, 555가 있습니다. 따라서 [5, 50, 55, 500, 505, 550, 555]를 return 합니다.
입출력 예 #2
10 이상 20 이하이면서 0과 5로만 이루어진 정수는 없습니다. 따라서 [-1]을 return 합니다.
내가 푼 풀이)
import java.util.*;
class Solution {
public int[] solution(int l, int r) {
List<Integer> numList = new ArrayList<>();
for(int i=l;i<=r;i++){
String str = String.valueOf(i);
str = str.replace("5","");
str = str.replace("0","");
if(str.isEmpty()){
numList.add(i);
}
}
if(numList.size()==0){
numList.add(-1);
}
return numList.stream().mapToInt(i->i).toArray();
}
}
시간복잡도 :
이 풀이는 반복문안에서 문자열을 계속해서 수정하는 작업을 합니다. 따라서 외부 반복문은 r-l+1번 반복하며 내부 반복문은 문자열 길이만큼 반복합니다. int형의 범위때문에 문자열로 변경시 매우 크지는 않겠지만 문자열 길이를 s라고 했을때 총 반복횟수는 (r-l+1)*s가 되고 이를 빅오 표기법으로 계산시 최악의 경우에는 O(n^2)이 될 수 있습니다.
공간복잡도 :
문자열과 새로운 리스트가 만들어질 공간이 필요하므로 각 O(n)이 되어 공간복잡도는 O(n)이 됩니다.
더 효율적인 풀이)
import java.util.*;
class Solution {
public int[] solution(int l, int r) {
List<Integer> result = new ArrayList<>();
Queue<Integer> queue = new LinkedList<>();
queue.add(5);
while (!queue.isEmpty()) {
int num = queue.poll();
if (num > r) continue; // 범위 벗어나면 무시
if (num >= l) result.add(num);
queue.add(num * 10); // 끝에 0 붙이기
queue.add(num * 10 + 5); // 끝에 5 붙이기
}
if (result.isEmpty()) {
return new int[]{-1};
}
Collections.sort(result); // BFS라 이미 정렬되었지만 안전하게
return result.stream().mapToInt(i -> i).toArray();
}
}
시간복잡도 :
이 풀이는 후보군이 될 수 있는 값만 큐에 저장합니다. 문제에서 배열에 들어갈 값은 0과 5뿐이라고 했으므로 큐에 초기값을 삽입한 후 큐에서 값을 꺼내어 *10과 *10+5를 해서 후보군을 만들어서 다시 큐에 넣습니다. 예를 들면 처음에는 큐에 5만 들어있으므로 첫번째 반복때는 5가 범위안에 들어있으면 result 리스트에 넣고 큐에는 50과 55를 넣습니다. 다음 반복때는 50과 55가 큐에 들어있으므로 선입선출에 따라 50을 먼저 꺼내어 범위안에 있으면 넣고 큐에는 500,505를 넣습니다. 그다음에는 55를 꺼내어 반복합니다. 이때 큐에서 나온값이 r보다 크다면 패스하게 되므로 결국 범위안에 있는 값만 큐에 들어갔다가 나오게 됩니다. 자료구조에서 큐의 삽입 삭제의 시간복잡도는 O(1)이고 반복은 큐에 들어간 값의 개수만큼만 반복하므로 총 시간복잡도도 O(1)이 됩니다. 참고로 정렬작업은 필요가 없는 이유는 코드를 보면 큐에는 오름차순으로 삽입되기 때문입니다.
공간복잡도 :
공간복잡도도 큐에 들어간 값의 개수만큼만 필요하므로 O(1)이 됩니다.
문제3) 2차원 배열만들기
정수 배열 num_list와 정수 n이 매개변수로 주어집니다. num_list를 다음 설명과 같이 2차원 배열로 바꿔 return하도록 solution 함수를 완성해주세요.
num_list가 [1, 2, 3, 4, 5, 6, 7, 8] 로 길이가 8이고 n이 2이므로 num_list를 2 * 4 배열로 다음과 같이 변경합니다. 2차원으로 바꿀 때에는 num_list의 원소들을 앞에서부터 n개씩 나눠 2차원 배열로 변경합니다.
| num_list | n | result |
| [1, 2, 3, 4, 5, 6, 7, 8] | 2 | [[1, 2], [3, 4], [5, 6], [7, 8]] |
제한사항
num_list의 길이는 n의 배 수개입니다.
0 ≤ num_list의 길이 ≤ 150
2 ≤ n < num_list의 길이
입출력 예
| num_list | n | result |
| [1, 2, 3, 4, 5, 6, 7, 8] | 2 | [[1, 2], [3, 4], [5, 6], [7, 8]] |
| [100, 95, 2, 4, 5, 6, 18, 33, 948] | 3 | [[100, 95, 2], [4, 5, 6], [18, 33, 948]] |
입출력 예 설명
입출력 예 #1
num_list가 [1, 2, 3, 4, 5, 6, 7, 8] 로 길이가 8이고 n이 2이므로 2 * 4 배열로 변경한 [[1, 2], [3, 4], [5, 6], [7, 8]] 을 return합니다.
입출력 예 #2
num_list가 [100, 95, 2, 4, 5, 6, 18, 33, 948] 로 길이가 9이고 n이 3이므로 3 * 3 배열로 변경한 [[100, 95, 2], [4, 5, 6], [18, 33, 948]] 을 return합니다.
내가 푼 풀이)
class Solution {
public int[][] solution(int[] num_list, int n) {
int c = num_list.length / n;
int[][] answer = new int[c][n];
int k =0;
int j=0;
answer[0][0]=num_list[0];
for(int i=1;i<num_list.length;i++){
if(i % n==0){
j++;
k=0;
}else{
k++;
}
answer[j][k] = num_list[i];
}
return answer;
}
}시간복잡도 :
배열 num_list를 한번만 순회하므로 시간복잡도는 O(n)입니다.
공간복잡도 :
2차원 배열이지만 공간의 크기는 c*n이고 이것은 num_list의 길이와 같으므로 공간복잡도는 O(n)입니다.
개선된 풀이)
class Solution {
public int[][] solution(int[] num_list, int n) {
int c = num_list.length / n;
int[][] answer = new int[c][n];
for (int i = 0; i < num_list.length; i++) {
answer[i / n][i % n] = num_list[i];
}
return answer;
}
}
시간복잡도와 공간복잡도는 줄일 수 없습니다. 그러나 가독성 측면에서 개선된 풀이가 조금 더 낫습니다.
문제4)
정수 배열 array와 정수 n이 매개변수로 주어질 때, array에 들어있는 정수 중 n과 가장 가까운 수를 return 하도록 solution 함수를 완성해주세요.
제한사항
1 ≤ array의 길이 ≤ 100
1 ≤ array의 원소 ≤ 100
1 ≤ n ≤ 100
가장 가까운 수가 여러 개일 경우 더 작은 수를 return 합니다.
입출력 예
| array | n | result |
| [3, 10, 28] | 20 | 28 |
| [10, 11, 12] | 13 | 12 |
입출력 예 설명
입출력 예 #1
3, 10, 28 중 20과 가장 가까운 수는 28입니다.
입출력 예 #2
10, 11, 12 중 13과 가장 가까운 수는 12입니다.
내가 푼 풀이)
import java.util.*;
class Solution {
public int solution(int[] array, int n) {
List<Map<String,Integer>> mapList = new ArrayList<>();
int check = Integer.MAX_VALUE;
for(int i=0;i<array.length;i++){
int absMinus = Math.abs(array[i] - n);
Map<String, Integer> map = new HashMap<>();
map.put("value", absMinus);
map.put("index", i);
mapList.add(map);
}
mapList.sort(Comparator.comparingInt(a -> a.get("value")));
int standardValue = mapList.get(0).get("value");
List<Integer> minList = new ArrayList<>();
for(Map<String,Integer> map : mapList){
int value = map.get("value");
if(value == standardValue){
minList.add(array[map.get("index")]);
}
}
minList.sort(Integer::compareTo);
return minList.get(0);
}
}
시간복잡도 :
array 배열을 순회하는데 걸리는 시간은 O(n), mapList를 정렬하는데 걸리는 시간은 O(nlog n), mapList를 순회하는데 걸리는 시간 O(n), minList를 정렬하는데 걸리는 시간은 O(nlog n)입니다. 따라서 시간복잡도는 O(nlog n)이 됩니다.
공간복잡도 :
mapList가 차지할 공간인 O(n)과 minList가 차지할 공간인 O(n)이라서 공간복잡도는 O(n)이 됩니다.
더 효율적인 풀이)
class Solution {
public int solution(int[] array, int n) {
int answer = 0;
int minDiff = Integer.MAX_VALUE;
for (int num : array) {
int diff = Math.abs(num - n);
if (diff < minDiff) {
minDiff = diff;
answer = num;
} else if (diff == minDiff && num < answer) {
// 거리가 같으면 더 작은 수 선택
answer = num;
}
}
return answer;
}
}
시간복잡도 :
array를 순회하는 시간만 걸리므로 총 시간복잡도는 O(n)입니다.
공간복잡도 :
변수가 차지할 공간만 필요하므로 O(1)입니다.
'Tools & Functions > 코딩 테스트 복기' 카테고리의 다른 글
| 프로그래머스 level1 파이썬 복기 -1 (0) | 2025.09.01 |
|---|---|
| 프로그래머스 level0 파이썬 복기 -3 (2) | 2025.08.26 |
| 프로그래머스 level0 파이썬 복기 -2 (5) | 2025.08.26 |
| 프로그래머스 level0 파이썬 복기 -1 (0) | 2024.05.19 |