처음에 문제를 보았을 때 투 포인터로 전체를 탐색하면서 문자를 연결해서 숫자 형식으로 바꿔서 max값을 구해서 다시 String으로 바꿔서 출력을 하려고 했는데 실패했다. int형 배열을 String 배열로 바꾸고 Array.sort를 이용해서 정렬을 한다. 만약 전부 0이면 0000으로 나와서 0으로 된 배열만 예외 처리를 해준다.
정확한 풀이
import java.util.*;
import java.io.*;
class Solution {
public String solution(int[] numbers) {
String answer = "";
String[] str = new String[numbers.length];
for(int i = 0; i < numbers.length; i++) {
str[i] = String.valueOf(numbers[i]);
}
Arrays.sort(str, new Comparator<String>() {
@Override
public int compare(String a, String b) {
return (b + a).compareTo(a + b);
}
});
if(str[0].equals("0")) {
return "0";
}
else {
for(int i = 0; i < str.length; i++) {
answer += str[i];
}
}
return answer;
}
}
step 1 - 3. 예산
내가 떠올린 풀이
이분 탐색으로 해결하면 되는 문제였다. 근데 이분탐색을 푸는데 갑자기 머릿속이 꼬여서 엄청 헤매면서 풀었다. 정답도 100점 만점에 90점이다.
정확한 풀이
import java.util.*;
class Solution {
public int solution(int[] budgets, int M) {
int answer = 0;
int sum = 0;
Arrays.sort(budgets);
for(int i = 0; i < budgets.length; i++) {
sum += budgets[i];
}
int max = 0;
if(sum >= M) {
int start = budgets[0];
int end = budgets[budgets.length - 1];
sum = 0;
while(start <= end) {
int midv = (start + end) / 2;
sum = 0;
//midv = 119 124 127
for(int i = 0; i < budgets.length; i++) {
if(midv > budgets[i]) {
sum += budgets[i];
}
else {
sum += midv;
}
}
if(sum > M) {
end = midv - 1; //end 129
}
else {
start = midv + 1;
answer = midv;
}
}
}
else {
answer = budgets[budgets.length - 1];
}
return answer;
}
}
오늘의 회고
오늘 문제를 풀면서 너무 헤맷습니다. 공부를 좀 더 열심히 해야 될 것 같습니다. 자신감이 떨어진 하루입니다.ㅠㅠ 좀 더 분발해서 공부하겠습니다. 중간고사도 있는데 중간고사 때 많이 못 풀 것 같은 느낌이.... 열심히 하겠습니다.
import java.io.*;
import java.util.*;
public class Baek1377 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [] arr = new int[n +1];
for(int i = 1; i <= n; i++) {
arr[i] = Integer.parseInt(br.readLine());
}
boolean change = false;
for(int i = 1; i <= n + 1; i++) {
change = false;
for(int j = 1; j <= n - i; j++) {
if(arr[j] > arr[j + 1]) {
change = true;
int swap = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = swap;
}
}
if(change == false) {
System.out.println(i);
break;
}
}
}
}
내가 떠올린 풀이 해설
C++ 예시로 보여준 코드를 그대로 적용해서 풀었습니다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1377 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
Sort [] arr = new Sort[n];
for(int i = 0; i < n; i++) {
arr[i] = new Sort(Integer.parseInt(br.readLine()), i);
}
Arrays.sort(arr);
int max = 0;
for(int i = 0; i < n; i++) {
if(max < arr[i].index - i) {
max = arr[i].index - i;
}
}
System.out.println(max + 1);
}
}
class Sort implements Comparable<Sort> {
int value;
int index;
public Sort(int value, int index) {
this.value = value;
this.index = index;
}
@Override
public int compareTo(Sort o) {
return this.value - o.value;
}
}
문제점
이 문제는 N의 최대 범위가 500,000이므로 버블 정렬로 문제를 풀면 시간 초과가 나온다. 각 데이터마다 정렬 전 index값에서 정렬 후 index값을 빼고 최댓값을 찾는다. 그리고 swap이 일어나지 않은 반복문이 한번 더 실행되는 것을 감안해 max에 + 1을 해준다.
17번 문제 소트 인사이드
내가 떠올린 풀이 해설
N의 크기가 1,000,000,000 보다 작거나 같은 자연수이다. 자연수를 받아 자릿수 별로 정렬하는 문제이므로 숫자를 String으로 받은 후 정렬을 List에 Arrays.stream(arr).boxed().collect(Collectors.toList()); 로 담아 Collections.sort(integer, Comparator.reverseOrder()); 를 이용해 내림차순 정렬을 진행했다.
정확한 풀이
import java.util.*;
import java.util.stream.Collectors;
public class Baek1427 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String str = br.readLine();
int []arr = new int[str.length()];
for(int i = 0; i < str.length(); i++) {
arr[i] = str.charAt(i) - 48;
}
List<Integer> integer = Arrays.stream(arr).boxed().collect(Collectors.toList());
Collections.sort(integer, Comparator.reverseOrder());
for(int i = 0; i < str.length(); i++) {
System.out.print(integer.get(i));
}
}
}
18번 문제 ATM
내가 떠올린 풀이 해설
N의 최댓값이 1,000이고 시간제한이 1초이므로 시간 복잡도가 O(n^2) 이하인 정렬 알고리즘 아무거나 사용해도 된다.
Arrays.sort로 정렬을 하고 인출 시간을 sum에 더하고 total 걸린 시간을 구하기 위해 sum을 다시 total에 더했다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek11399 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int []arr = new int[n];
StringTokenizer st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
int sum = 0;
int total = 0;
for(int i = 0; i < n; i++) {
sum += arr[i];
total += sum;
}
System.out.println(total);
}
}
19번 문제 K번째 수
내가 떠올린 풀이 해설
N의 최대 범위가 5,000,000이므로 O(nlogn)의 시간 복잡도로 정렬을 해야 된다. 간단하게 Arrays.sort로 풀었다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek11004 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
int[] arr = new int[n];
st = new StringTokenizer(br.readLine());
for(int i = 0; i < n; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr);
System.out.println(arr[m - 1]);
}
}
20번 문제 수 정렬하기 2
내가 떠올린 풀이 해설
N의 최대 범위가 1,000,000이므로 O(nlogn)의 시간 복잡도로 정렬을 수행해야 된다. Collections.sort을 이용해서 해결했다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek2751 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuffer bf = new StringBuffer();
int n = Integer.parseInt(br.readLine());
int [] arr = new int[n];
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < n; i++) {
list.add(Integer.parseInt(br.readLine()));
}
Collections.sort(list);
for(int i = 0; i < n; i++) {
bf.append(list.get(i) + "\\n");
}
System.out.println(bf.toString());
}
}
문제점
Arrays.sort 로 쓰면 시간 초과가 난다.Arrays.sort() 의 경우dual-pivot Quicksort알고리즘을 사용한다. 물론 평균 시간 복잡도가O(nlogn) 이고 매우 빠른 알고리즘이다. 그러나 최악의 경우 시간 복잡도는O(n2) 이다. Collections.sort() 은 Timsort이다. Timsort 의 경우 합병 및 삽입 정렬 알고리즘을 사용한다. 두 가지가 섞여있는 정렬 알고리즘을hybrid sorting algorithm이라고 하는데, 합병 정렬은 최선, 최악 모두O(nlogn)을 보장하고 삽입 정렬은 최선의 경우는O(n), 최악의 경우는O(n2)이다. 그리고 두 정렬 모두 안정 정렬이기 때문에 Timsort를hybrid stable sorting algorithm이라고도 한다. 즉, 합병 정렬의 최악의 경우와 삽입 정렬의 최선의 경우를 짬뽕한 알고리즘이 Timsort라는 것이다.
오늘은 Do it 알고리즘 책에 있는 문제를 풀었습니다. 정렬에 관한 기본적인 문제 5문제를 풀었고 그동안 문제를 풀면서 Arrays.sort, Collections.sort를 많이 사용하였는데 시간 복잡도와 어떤 정렬을 사용하는지 모르고 사용하였습니다. sort에 대해 오늘 정렬 문제를 풀면서 학습하게 되었습니다. 정렬에 관한 알고리즘을 공부하고 시간 복잡도를 고려에 적절한 알고리즘을 사용해야 될 것 같습니다.
기준점 (0, 0)에서 끝점 (w, h)까지의 직사각형이 생기는데 기준점과 끝면으로 생긴 직사각형 면에 가장 가까운 거리를 구하는 문제이다. 저는 x의 좌표에서 기준점을 빼고 w좌표에서 x를 빼주고 Math.min을 이용해서 최솟값을 저장하고 y도 같은 방법으로 최솟값을 저장하고 두개의 최솟값을 다시 Math.min으로 최솟값을 구해서 출력해준다.
정확한 풀이
import java.util.*;
import java.io.*;
public class Baek1085 {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());
int w = Integer.parseInt(st.nextToken());
int h = Integer.parseInt(st.nextToken());
int endX = w - x;
int endY = h - y;
int m = Math.min(x, y);
int n = Math.min(endX, endY);
int answer = Math.min(m, n);
System.out.println(answer);
}
}
백준 1181번 단어 정렬
내가 생각한 풀이
String 배열로 문자열을 받아서 Comparator를 이용해서 단어 길이가 같을 경우 return o1.compareTo(o2);를 해주고 길이가 다르면 길이 순으로 정렬을 한다. 같은 단어가 있을 때 for문으로 탐색 후 그 전의 단어와 같을 경우 하나만 출력을 해줘서 중복을 방지한다.
정확한 풀이
import java.io.*;
import java.util.*;
public class Baek1181 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
String []str = new String[n];
for(int i = 0; i < n; i++) {
str[i] = br.readLine();
}
Arrays.sort(str, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
if(o1.length() == o2.length()) {
return o1.compareTo(o2);
}
else {
return o1.length() - o2.length();
}
}
});
System.out.println(str[0]);
for(int i = 1; i < n; i++) {
if(!str[i].equals(str[i - 1])) {
System.out.println(str[i]);
}
}
}
}
오늘의 회고
오늘은 어제 못풀었던 정렬에 관한 쉬운 문제 2문제를 풀어봤습니다. 정렬의 comparator를 이용하는 문제에서 아직은 완벽하게 구현하기 부족한 점이 있고 복습을 하면서 완전하게 내것으로 만들어야 될 것 같습니다. 아직 갈 길이 멀지만 급하게 하지 않고 천천히 꾸준하게 준비하겠습니다.
