[프로그래머스/181861] 배열의 원소만큼 추가하기
in Study / Coding Test
☑️ 문제
☑️ 풀이
첫 번째 풀이
import java.util.*;
class Solution {
public int[] solution(int[] arr) {
List<Integer> list = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
list.add(arr[i]);
}
for (int i = 0; i < list.size(); i++) {
int n = list.get(i);
for (int j = 0; j < n; j++) {
list.add(n);
}
}
int[] answer = new int[list.size()];
for (int i = 0; i < list.size(); i++) {
answer[i] = list.get(i);
}
return answer;
}
}
- 메모리 초과로 실패한 풀이이다.
- 배열을 반복하면서 크기를 조정해야 하는데, 리스트가 실시간으로 커져서 루프가 계속 반복되기 때문이다.
- 메모리 초과 문제를 해결하기 위해 리스트를 사용하는 걸 피해보자.
두 번째 시도
import java.util.*;
class Solution {
public int[] solution(int[] arr) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < arr.length; i++) {
int num = arr[i];
for (int j = 0; j < num; j++) {
sb.append(num);
}
}
String str = sb.toString();
int[] answer = new int[str.length()];
for (int i = 0; i < str.length(); i++) {
answer[i] = Integer.parseInt(String.valueOf(str.charAt(i)));
}
return answer;
}
}
StringBuilder를 사용해서 문자열로 변환 후 다시 배열로 변환하려고 했다.- 이렇게 하면 불필요한 문자열 연산이 발생하게 되어 효율성이 떨어진다.
- 그리고 최종적으로 리턴할 배열의 크기를 사전에 알 수 있기 때문에 이를 이용해야 한다.
세 번째 풀이 (성공)
//시간: 0.16ms
//메모리: 92.6MB
import java.util.*;
class Solution {
public int[] solution(int[] arr) {
int size = 0;
for (int num : arr) {
size += num;
}
int[] answer = new int[size];
int idx = 0;
for (int i = 0; i < arr.length; i++) {
int num = arr[i];
for (int j = 0; j < num; j++) {
answer[idx++] = num;
}
}
return answer;
}
}
- 배열의 크기를 미리
size변수에 저장해두었다. for문을 돌면서idx값을 이용하여num의 개수만큼 배열에 넣는 방식을 사용하였다.
두 번째 풀이
//시간: 0.12ms
//메모리: 81.2MB
import java.util.*;
class Solution {
public int[] solution(int[] arr) {
int size = 0;
for (int num : arr) {
size += num;
}
int[] answer = new int[size];
int idx = 0;
for (int i = 0; i < arr.length; i++) {
int num = arr[i];
Arrays.fill(answer, idx, idx + num, num);
idx += num;
}
return answer;
}
}
- 위와 동일하지만
fill()메서드를 사용하여 조금 더 효율적으로 배열을 채울 수 있었다.
☑️ 문법 정리 - Arrays.fill()
Arrays.fill()
- 배열의 특정 범위를 특정 값으로 채우는
Java의 내장 메서드이다.
기본 문법
Arrays.fill(배열, 값);
- 배열 전체를
값으로 채운다. O(N)시간 복잡도로 동작한다. (배열 크기만큼 반복함)예제
import java.util.Arrays; public class Main { public static void main(String[] args) { int[] arr = new int[5]; Arrays.fill(arr, 7); System.out.println(Arrays.toString(arr)); // [7, 7, 7, 7, 7] } }
부분 범위 채우기
Arrays.fill(배열, 시작인덱스, 끝인덱스, 값);
시작 인덱스부터끝 인덱스 -1까지값으로 채운다.예제
import java.util.Arrays; public class Main { public static void main(String[] args) { int[] arr = new int[10]; Arrays.fill(arr, 2, 6, 9); // 인덱스 2부터 5까지 9로 채움 System.out.println(Arrays.toString(arr)); // [0, 0, 9, 9, 9, 9, 0, 0, 0, 0] } }
2차원 배열 채우기
Arrays.fill()은 1차원 배열만 지원하기 때문에, 2차원 배열을 채울 때는for문을 사용해야 한다.예제
import java.util.Arrays; public class Main { public static void main(String[] args) { int[][] arr = new int[3][4]; for (int i = 0; i < arr.length; i++) { Arrays.fill(arr[i], 5); // 각 행을 5로 채우기 } for (int[] row : arr) { System.out.println(Arrays.toString(row)); } } }- 출력
[5, 5, 5, 5] [5, 5, 5, 5] [5, 5, 5, 5]
