1. 문제 설명
2. 접근 방식
삽입 정렬을 이용하여 문제를 풀어보았다.
정렬된 영역에서 현재 값을 삽입할 위치 선택을 위해 단순 반복문을 사용하는 것보다 이진 탐색을 사용하는 것이 그나마 시간이 빠를 것 같아서, 이진 탐색을 이용했다.
이진 탐색에서 중간 값보다 작았을 시, 클 시 start나 end에 그냥 mid를 더해줘서 무한 Loop에 빠지는 실수를 범했다.
start = mid +1, end = mid -1로 해주어서 start= 0, mid = 1인 경우를 대비해줘야 한다.
3. 코드 분석
import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 1. 입력
int N = Integer.parseInt(br.readLine());
ArrayList<Integer> list = new ArrayList<>();
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
list.add(Integer.parseInt(st.nextToken()));
}
// 2.
for (int i = 1; i < N; i++) {
int pos = binarySearch(list, i);
int value = list.remove(i);
list.add(++pos, value);
}
int [] sum = new int [N];
sum[0] = list.get(0);
for (int i = 1; i < N; i++) {
sum[i] = sum[i-1] + list.get(i);
}
int acc = 0;
for (int i = 0; i < N; i++) {
acc += sum[i];
}
System.out.println(acc);
}
public static int binarySearch(ArrayList<Integer> list, int now_idx) {
int start = 0;
int end = now_idx-1;
while (start <= end){
int mid = (start+end)/2;
if(list.get(mid)< list.get(now_idx)){
start = mid+1;
}
else if(list.get(mid) > list.get(now_idx)){
end = mid-1;
}
else if(list.get(mid).equals(list.get(now_idx))){
return mid;
}
}
return end;
}
}
4. 성장 하기
배열에서 중간 삽입을 어떻게 할지 잘 몰라서, ArrayList를 썼다. 배열만 이용하는 풀이로 해보고 싶어서, 다른 사람의 풀이를 봤다. 방법은 다음과 같다.
- 0 ~ 현재값 -1의 정렬된 영역 중 현재 값이 들어갈 위치 찾기
- 현재 값이 들어갈 위치 + 1 ~ 현재 값의 위치 내의 영역의 값을 Arr[j] = Arr[j-1]로 한칸씩 땡기기.
(최초의 값인 Arr[현재값 위치]는 어짜피 지어져도 상관 無 -> 값 옮기기 전에 미리 빼놓기만 하면 된다.)
5. 다른 풀이
import java.io.*;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 1. 입력
int N = Integer.parseInt(br.readLine());
int [] arr = new int [N];
int [] sum = new int [N];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
// 2. 값 넣기
for (int i = 1; i < N; i++) {
int insert_idx = i;
int insert_value = arr[i];
// 현재 값이 삽입될 위치 찾기
for (int j = i-1; j >=0; j--) {
// 현재 자신보다 값이 작은 위치를 찾았다면, 그 앞에 넣으면 됨.
if(arr[i] > arr [j]){
insert_idx = j+1;
break;
}
if(j == 0) insert_idx =0;
}
// 앞쪽 전부 땡기기
for (int j = i; j > insert_idx ; j--) {
arr[j] = arr[j-1];
}
arr[insert_idx] = insert_value;
}
// 3.누적 합의 합 구하기
sum[0] = arr[0];
for (int i = 1; i < N; i++) {
sum[i] = sum[i-1] + arr[i];
}
int acc = 0;
for (int i = 0; i < N; i++) {
acc += sum[i];
}
System.out.println(acc);
}
}
'알고리즘 > 문제 풀이' 카테고리의 다른 글
[백준] 1377 버블소트 JAVA (0) | 2024.07.02 |
---|---|
[백준] 17298 오큰수 JAVA (0) | 2024.07.02 |
[백준] 1253 좋다 (0) | 2024.06.28 |
[백준] 2018 수들의 합 5 Java 풀이 (0) | 2024.06.28 |
[백준] 11659 구간 합 구하기 4 쉬운 풀이 여러가지 풀이 java (0) | 2024.06.22 |