Description
1.
프로그래머스 코딩 문제 큰 수 만들기를 진행하는 도중 시간초과 오류가 생겼다.
2.
매개변수로 어떤 값이 들어와있는지 모른 채로 코드를 진행해야 한다.
코드
3.
현재 코드는 for문으로 가장 큰 수를 찾고
4.
While문으로 큰 수를 제외하고 문자들을 지우고 있다.
5.
두 가지의 반복문이 시간 초과 오류를 일으키고 있는것 같다.
6.
for문과 while 문은 현재 같은 변수를 공유하는 측면이 있어서 하나를 수정하면 다른 하나도 수정을 해야한다.
7.
기능을 분리해서 처리하는것도 나쁘지 않은 방법인것 같다.
Try
첫번째 시도 for문과 while문을 내부함수로 변경하여 분리도 유지하기
현재 for문을 분리하고 해당 코드가 제대로 동작하는지 화깅ㄴ하기 위해 코드를 돌려봤더니 코드가 제대로 돌아갔다.
import java.util.*;
class Solution {
public String solution(String number, int k) {
String answer = "";
int start = 0;
StringBuilder sb = new StringBuilder(number);
while(0 < k) {
// 가장 큰 문자의 인덱스를 저장할 변수
int maxIndex = findBigCharIndex(start, k, sb);
char max = sb.charAt(maxIndex);
while(sb.charAt(start) != max) {
sb.delete(start,start+1);
k--;
}
start++;
}
return sb.toString();
}
public int findBigCharIndex(int start, int k, StringBuilder sb) {
// 가장 큰 문자를 저장할 변수
char max = ' ';
// 가장 큰 문자의 인덱스를 저장할 변수
int maxIndex = 0;
// 0부터 K까지의 문자들중 가장 큰 문자와 인덱스 탐색
for(int i = start; i <= start+k; i++) {
// 현재 탐색중인 문자가 이전에 탐색한 문자보다 크다면
if(max < sb.charAt(i)) {
// 이전에 탐색한 문자를 현재 탐색중인 문자로
max = sb.charAt(i);
// 이전에 탐색한 인덱스를 현재 탐색중인 인덱스로
maxIndex = i;
// 변경
}
}
return maxIndex;
}
}
JavaScript
복사
심지어 오류가 일어나던 테스트 케이스 10번은 기존의 10초가 넘어가서 오류가 일어났지만 현재 4초 밖에 안 걸린다.
정확성 테스트
테스트 1 〉 통과 (0.05ms, 72.5MB)
테스트 2 〉 통과 (0.06ms, 79.1MB)
테스트 3 〉 통과 (0.21ms, 66.1MB)
테스트 4 〉 통과 (0.35ms, 71MB)
테스트 5 〉 통과 (4.00ms, 74MB)
테스트 6 〉 통과 (19.79ms, 78.2MB)
테스트 7 〉 통과 (37.83ms, 74.4MB)
테스트 8 〉 통과 (180.50ms, 81.4MB)
테스트 9 〉 통과 (5.23ms, 85.3MB)
테스트 10 〉 통과 (4241.78ms, 103MB)
테스트 11 〉 통과 (0.05ms, 75.5MB)
테스트 12 〉 실패 (런타임 에러)
채점 결과
정확성: 91.7
합계: 91.7 / 100.0
JavaScript
복사
Solution
1.
내부 함수로 돌리면 함수를 재 호출하지 않아도 되기에 이런 일이 일어난걸까?
AI의 답변 내용
실행 시간의 차이는 코드의 구조와 실행 환경에 따라 달라질 수 있습니다. 기존 코드와 수정된 코드에서 실행 시간이 다르게 나타나는 이유를 몇 가지 예로 들어보겠습니다:
함수 호출 오버헤드: 함수를 호출할 때마다 일정한 시간이 소요됩니다. 이를 함수 호출 오버헤드라고 합니다. 함수를 분리하면 함수 호출 횟수가 늘어나므로, 함수 호출 오버헤드가 증가하여 실행 시간이 늘어날 수 있습니다. 하지만 이 경우, 함수 호출 오버헤드는 전체 실행 시간에 비해 매우 작은 부분을 차지하므로 실행 시간에 큰 영향을 미치지 않습니다.
컴파일러 최적화: 컴파일러는 코드를 실행 가능한 기계어로 변환할 때 다양한 최적화 기법을 사용합니다. 함수를 분리하면 컴파일러가 이를 인식하고, 코드를 더 효율적으로 최적화할 수 있습니다. 이로 인해 수정된 코드가 기존 코드보다 빠르게 실행될 수 있습니다.
가비지 컬렉션: 자바는 가비지 컬렉션을 통해 사용하지 않는 메모리를 자동으로 회수합니다. 함수를 분리하면 메모리 사용 패턴이 바뀌어 가비지 컬렉션이 더 효율적으로 동작하게 될 수 있습니다. 이로 인해 수정된 코드가 기존 코드보다 빠르게 실행될 수 있습니다.
캐시 효율: 컴퓨터의 메모리는 여러 단계로 구성되어 있고, 각 단계마다 접근 속도와 크기가 다릅니다. 코드의 실행 패턴에 따라 어떤 데이터가 캐시에 로드되는지가 달라집니다. 함수를 분리하면 메모리 접근 패턴이 바뀌어 캐시 효율이 높아질 수 있습니다. 이로 인해 수정된 코드가 기존 코드보다 빠르게 실행될 수 있습니다.
이 외에도 실행 환경의 상태(예: CPU 사용률, 메모리 사용량 등), 입력 데이터의 특성 등 여러 요인이 실행 시간에 영향을 미칠 수 있습니다. 따라서 실행 시간을 정확하게 예측하거나 비교하려면 동일한 환경에서 여러 번 실행하여 평균 실행 시간을 측정하는 것이 좋습니다.
해당 답변 내용과 현재 내가 코드를 돌리고 있는 프로그래머스 라는 특수성을 적용하면
컴파일러 최적화 방식과 가비지 컬렉션 때문에 호출시간과 메모리 사용량이 변한 것 같다.
이로서 알게 된 방법은 프로그래머스 내부에서만 적용되는 사항일 수도 있지만 함수를 사용해 기능 분리르 하게 되면 컴파일러 최적화와 가비지 컬렉션 덕분에 메모리 사용량과 사용 시간에서 우위를 가져올 수도 있다는것이다.
하지만 함수 호출 오버헤드라는 단점도 있으니 해당 방법은 나중에 좀 더 고민을 해봐야 할 것 같다.
1.
함수가 많은 매개변수를 가지거나
2.
함수가 많은 로컬변수를 가지거나
3.
함수 호출시 참조 값이 아닌 변수 값을 전달한다면
오버헤드가 늘어난다.