요새 안썼는데 다시 잘 쓰도록 노력하자
언어는 Java공부 하고 있으니까 Python -> Java로 바꿨고,
Java 라이브러리나 메서드 같은걸 잘 몰라서 좀 쉬운걸로 진행할 예정이다.
문제 분석
일단 문제를 보면 배열이 주어지는데 배열에서 가장 작은 수 를 제거하여 다시 배열로 리턴해주면 된다.
다만 배열의 길이가 1인 경우 -1을 배열에 넣어 리턴해주면 된다.
문제 풀이
일단 배열의 길이가 1인 경우부터 보면
// 배열의 길이가 1인 경우
if (arr.length == 1) {
return new int[](-1);
}이건 뭐 너무 쉬우니까
다음으로는 가장 작은 수 를 구해야 한다.
내가 생각한 방법은 배열을 정렬하고,
내림 차순 정렬 : 배열의 마지막 요소 = 최소값
오름 차순 정렬 : 배열의 첫 번째 요소 = 최소값
일테니 해당 요소의 인덱스를 뺀 나머지만 순회하며 복사하면 된다고 생각했다.
// 오름 차순 정렬
Arrays.sort(arr);
// 내림 차순 정렬
Arrays.sort(arr);
int[] reversedArr = Arrays.stream(arr)
.boxed()
.sorted(Collections.reversedOrder())
.mapToInt(Integer::intValue)
.toArray();처럼 오름 차순 정렬로 간단하게 사용할 수 있고,
혹은 내림 차순 정렬은 stream을 이용하여 역순으로 정렬하고 다시 리스트로 만들어 준다.
// 내림 차순 정렬만 다루도록 하겠음
// 내림 차순 정렬 -> 깊은 복사 -> 이 과정에서 for + 1
int[] arr2 = new int[arr.length - 1];
for(int i = 0; i < arr2.length; i++){
arr2[i] = reversedArr[i];
}int[] arr2 = new int[arr.length - 1];
우린 최소값을 뺀 배열을 리턴할것이기 때문에 원래 배열 길이의 -1 이 리턴해줄 배열의 길이가 된다.
따라서 for문의 길이를 arr2의 길이로 해준다면 arr의 마지막 인덱스에 접근하지 않을테고 최소값이 빠진 배열이 생성되게 된다.
전체 코드
import java.util.*;
import java.util.Arrays;
import java.util.Collections;
class Solution {
public int[] solution(int[] arr) {
// if 배열 길이 1 이면 -1
if (arr.length == 1) {
return new int[]{-1};
}
// 배열 정렬
Arrays.sort(arr);
int[] reversedArr = Arrays.stream(arr)
.boxed()
.sorted(Collections.reverseOrder())
.mapToInt(Integer::intValue)
.toArray();
// 내림차순 정렬 -> 깊은 복사 -> 이 과정에서 for + 1
int[] arr2 = new int[arr.length - 1];
for(int i = 0; i < arr2.length; i++){
arr2[i] = reversedArr[i];
}
return arr2;
}
}이렇게 하면
테스트 케이스가 정상적으로 작동하고
채점은 실패하는 결과를 얻을 수 있다. 자연스러웠다
문제점
문제점이 무엇일까... 하고 생각을 해봤다.
테스트 케이스는 통과 했는데 왜 문제일까 생각하면서 테스트 케이스를 다시 봤다.
다시 보니 얘는 이미 정렬이 되어있는 경우니까 상관이 없는데,
만약 [1,3,2,4] 라는 arr이 입력받아지면 최소값인 1을 제외한 [3,2,4]라는 배열을 리턴해야 한다.
그렇지만 나는 물리적으로 정렬을 했고, 정렬을 하기 전의 배열을 알지도 못한다.
또한 정렬을 했기 때문에 명확한 최소값도 모르고, 그래서 배열에서 해당 값을 뺄 수도 없다.
해결 방법
문제점을 알았으면 문제점에서 해결 방법을 도출해보자.
최소값을 안다면 배열을 복사하는 과정에서 최소값을 뺀 배열을 복사할 수 있을것이다.
// 배열에서 가장 작은 수를 찾는다.
int min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
}
}C언어를 공부할 때 temp를 통해 값을 바꾸는 방법에서 힌트를 찾았다.
(Python이면 그냥 min 쓰면 되는데 ㄲㅂ...)
여튼 arr의 첫 번째 값을 최소값으로 설정해 두고 arr 전체를 탐색하면서 min 보다 작은 값으로 min을 갱신한다.
최종적으로 반복이 끝났을 때 나온 min이 해당 arr의 최소값이 된다.
// 가장 작은 수를 제외한 배열을 생성
int[] answer = new int[arr.length - 1];
int index = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] != min) {
answer[index++] = arr[i];
}
}최소값을 구했다면 배열을 복사하면서 min과 같은 값을 복사하는 배열에 넣지 않는다면 그대로 최소값만 뺀 순서가 똑같은 배열이 생긴다.
public class Solution {
public int[] solution(int[] arr) {
// 배열의 길이가 1인 경우
if (arr.length == 1) {
return new int[]{-1};
}
// 배열에서 가장 작은 수를 찾는다.
int min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
}
}
// 가장 작은 수를 제외한 배열을 생성합니다.
int[] answer = new int[arr.length - 1];
int index = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] != min) {
answer[index++] = arr[i];
}
}
return answer;
}
}전체 코드
실행 결과
시간 복잡도
같은 배열을 가지고 for문이 2번 돌지만 중첩되어 도는 경우가 아니기 때문에
시간 복잡도는 O(2N)이 되며 빅오 표기법에서 상수는 표현하지 않기 때문에 최종적으로 시간 복잡도는 O(N)이 되는 알고리즘이다.
끝!
나중에는 SQL도 조금씩 올려볼까 한다.
