오랜만에 작성하는 TIL.. 반성한다
오늘은 저번주 다 정리했다고 생각한 알고리즘 관련 시간복잡도를
실제 프로그래머스 문제를 풀이하는 과정에서 만나 이해한 것을 정리해볼까 한다.
먼저 문제부터 살펴보면
문제 설명
자연수 n을 뒤집어 각 자리 숫자를 원소로 가지는 배열 형태로 리턴해주세요. 예를들어 n이 12345이면 [5,4,3,2,1]을 리턴합니다.
처음에은 간단한 방법으로 전체를 돌며 맨뒤 인덱스 값을 answer 배열에 넣는식으로 구현했다
public static long[] solution(long n) {
long count = String.valueOf(n).length();
long[] answer = new long[(int)count];
String temp = String.valueOf(n);
for (int i = 0; i < answer.length; i++){
answer[i] = Long.parseLong(temp.substring((int)(count-1), (int)count));
count--;
}
return answer;
}answer[i]에 배열 temp 문자열을 substring으로 맨뒤부터 서로 거꾸로 된 인덱스 값으로 빼서 넣는 형식이다
하지만 뭔가 아쉬었다 잘 생각해보면 하나하나 넣는것 말고 맨앞과 맨뒤를 바꿔주면 뒤집어질것이 아닌가 하는 생각에 구현해 보았다
public static long[] solutionBetter(long n) {
int size = String.valueOf(n).length();
long[] answer = new long[size];
String[] list = String.valueOf(n).split("");
if (size % 2 == 1) {
int centerIndex = size / 2;
answer[centerIndex] = Long.parseLong(list[centerIndex]);
}
for (int i = 0; i < list.length/2; i++) {
int oppositeIndex = size - 1 - i;
String opposite = list[oppositeIndex];
answer[i] = Long.parseLong(list[oppositeIndex]);
answer[oppositeIndex] = Long.parseLong(list[i]);
}
return answer;
}if문을 통해 중앙값이 빠지는 경우를 핸들링하고 반대 되는 익덱스 값을 넣어준다
내 예상은 첫 번째 방법은 O(n)이고 두번째는 O(n/2) 라고 생각했으나 프로그래머스에 정답제출을 하면
1번
2번
이게 무슨일인가 더 개선하고자 한 코드가 오래걸리는 것이였다..
곰곰이 생각해보니 단편적으로 for문을 돌며 수행하는건 절반으로 맞는 말이지만 그 내부에서 수행하는 작업이 두 번째 로직이 첫 번째 로직보다 많기 때문에 n이 작은 값일때는 첫 번째 로직이 더 효율적인 것 이였고
다른 한가지 요인은 프로그래머스의 테스트 케이스는 작은 값으로 주어져서 그랬던 것이었다.
만약 단순히 1231415 같은 하나의 값이 아닌 12,31,4,1,5 와 같이 여러개를 담는 배열 혹은 주어진 n값이 클때는 뒤집는 로직으로 그 반대의 간단한 요구조건은 첫 번째와 같은 로직으로 구현하도록 하자!
