중앙정보기술인재개발원 개발자 과정 21일차 기록입니다.

오늘은 수업이 드디어 객체지향 부분을 들어가기 시작했습니다.

 

아마 조만간 수업을 집중해서 들어야 될 날이 올것 같습니다.

 

저는 조금이라도 수업에서 이해 못하는 부분을 줄이려고 매일 교재를 미리 예습하고 있고,

 

지금 클래스 장의 마지막 문제풀이를 하는중입니다.

 

아무튼 오늘도 오전엔 예습, 오후와 저녁엔 문제풀이를 했습니다.

 

그리고 LeetCode 를 자동커밋 연동하고 문제를 풀었는데,

 

특이한 걸 발견해서 적어봅니다.

 

 

 

문제는 이렇습니다.

 

랜덤한 원소 갯수와 랜덤한 정수값을 가진

정수배열 int[] nums 가 주어지고,

역시 랜덤한 정수변수 target 가 주어졌을때,

 

nums 배열의 각기 다른 인덱스의 원소끼리 더한 값이,

target 와 같으면,

그 원소들의 인덱스를 오름차순으로 나열해서 return해라.

 

였습니다.

 

예시)

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

 

Input: nums = [3,2,4], target = 6
Output: [1,2]

 

Input: nums = [3,3], target = 6
Output: [0,1]

 

 

 

 

첫번째 코드

class Solution {

    public int[] twoSum(int[] nums, int target) {
        int[] answer = new int[2];
        run:for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                if(nums[i]+nums[j]==target){
                    answer[0]=i;
                    answer[1]=j;
                    break run;
                }
            }
        }
        return answer;
    }
}

 

 두번째 코드

class Solution {

    public int[] twoSum(int[] nums, int target) {

        for(int i=1;i<nums.length;i++){
            for(int j=i;j<nums.length;j++){
                if(target==nums[j]+ nums[j-i])
                {
                    return new int[]{j, j-i};
                }
            }
        }
        return null;
    }
}

 

 

그런데 위 코드들은,

 

분명 둘 다 이중 for문에 if문도 똑같고,

모든 경우의 수를 중복되지 않게 확인하는 것마저 똑같은데,

 

단지 경우의 수를 확인하는 과정에서,

확인하는 순서만 다를 뿐입니다.

 

헌데 첫번째 코드는 실행시간에 44ms 가 걸리고,

두번째 코드는 실행시간에 0ms가 걸렸습니다.

(실제론 아니지만 아주 적은 시간은 0으로 처리돼서 나오는것 같습니다.)

 

챗gpt도 두루뭉술하게 대답해줘서 제가 고민해본 결과,

 

이런 이유로 추측이 됩니다.

 

 

 

예를 들어, 첫번째 코드는,

 

인덱스가 6까지 있다고 치면,

0,1 부터

0,2

0,3....

3,4

3,5

3,6

4,5

4,6

5,6  이런식으로 확인을 합니다.

 

즉, 인덱스가 아주 작은것부터 점점 커집니다.

그렇다는 것은 랜덤하게 확인하는것 같아도,

일정하게 작은인덱스부터 순차적으로 확인하기 때문에,

분명 겹치는 경우는 없지만,

확인하는 것에 흐름이 있다면,

왼쪽에서 오른쪽으로 쭉 흘러갑니다. 

 

 

헌데 두번째 코드는,

 

1,0 부터

2,1

3,2....

4,0

5,1

6,2

5,0

6,1

6,0  이런식으로 확인을 합니다.

 

보면 이 알고리즘에서 느껴지는게

뭔가 흐름이 왼쪽 오른쪽, 왔다 갔다 

더욱 랜덤하게 확인하는 것 같습니다.

 

그래서,

랜덤한 값을 구할 때,

0부터 100까지 순서대로 짚는것보다,

가능한 왔다 갔다하며 짚는 것이

더 효율적인 알고리즘인가?

라는 의문이 들고,

 

여전히 추측뿐이라 이해는 잘 가지 않습니다.

 

혹시 글 읽으신 분들중에 이 문제에 대한

명쾌한 답을 아신다면 저에게 꼭 알려주세요

 

이건 제가 알게되면 무조건 사례하겠습니다.