[프로그래머스] 뒤에 있는 큰 수 찾기 - [투 포인터 말만?]

구현, 투 포인터, 이중 포문

https://school.programmers.co.kr/learn/courses/30/lessons/154539

프로그래머스

 

설명

 코드부터 먼저 올리고 설명을 하는데, 이번에는 순서를 좀 바꿔서 설명해야 할 필요성이 있는 문제라서 설명과 코드 순서를 바꿨다. 또 지고의 영역인 분들에게 배운 기본이론을 바탕으로 증명과 동시에 설명해보려고 한다.

 

 우선 이 문제를 먼저 읽고 와서 내용을 보아야 이해가 간다. 만약 저 문제를 읽고 왔다면 혹시라도 본인이 풀지 못했거나, 이게 왜 틀린 풀이일까를 생각하여 '투 포인터' 혹은 '완전탐색'을 생각했다면 끝까지 보는 것을 추천드립니다. 좋은 정보는 공유하면 좋으니까요.

 

 틀린 풀이부터 살펴보자. 첫번째 만약 당신이 '완전탐색'을 생각했다면, 문제에서 요구하는 시간복잡도 상에선 틀렸을지 몰라도, 완전탐색으로 접근한 풀이가 답이 될 수 없는 것은 아니다. 즉 다시 말해 문제 요구 조건에 부합하지 않는다는 것이지. 문제에서 구하라고 하는 로직의 아이디어는 맞다고 생각한다.

 

 왜냐하면, 완전 탐색을 이용해서 해당 문제를 풀게 될 경우 특정 수 다음으로 나오는 가장 큰 수를 찾기 위해서 아마 아래와 같은 코드로 작성했을 가능성이 있다.

// 임시배열
int[] numbers = [2,3,3,5];

int[] result = new int[numbers.length];
int pos = 0;
for (int i = 0; i < numbers.length; i++) {
	for (int j = i + 1; j < numbers.length; j++) {
    	if(numbers[i] < numbers[j]) {
        	result[pos++] = numbers[j];
        }
    }
}

 

 완전탐색 풀이를 보고 틀린 풀이는 아니라고 볼 수 있다. 답은 나오니까. 저 코드에서 뒤 큰 수를 찾을 수 없으면 조건만 추가해 주면 -1을 넣는 것도 쉽게 구현할 수 있다고 생각한다. 하지만 완전탐색이 문제 조건에 맞지 않는 이유는 배열의 크기에 있다. 배열의 크기가 100만 인 것을 본다면, 100만 * 100만 만큼의 시간이 필요로 하므로, 이는 시간초과가 난다는 것을 보여준다. 따라서 완전탐색 풀이는 문제의 시간복잡도를 만족하지 못하기 때문에 틀리다.

 

 다음으로 '투 포인터'를 생각했다면, 잘 읽어 보면 좋을 것 같다. 우선 나도 '투 포인터' 라는 방법을 생각했었고, 어디까지나 나의 큰 착각과 무지에서 나오는 건방이라는 것을 가르침을 받고 깨달았다. 우선 내가 투 포인터라고 접근했던 코드는 아래와 같다.

	int start = 0;
        int end = 1;
        int index = 0;
        
        int []answer = new int[numbers.length];

        while (start < numbers.length) {
            if(start == numbers.length -1 && end == numbers.length){
               answer[index] = -1;
               break;
            }
            
            // 뒷 큰 수를 발견했다면
            if(numbers[start] < numbers[end]) {
                answer[index++] = numbers[end];
                start++;
                end = start + 1;
            } else if(start != numbers.length - 1 && end == numbers.length - 1)  {
                if(numbers[start] >= numbers[end]) {
                    answer[index++] = -1;
                    start++;
                    end = start + 1;
                }
            } else{
                end++;
            }
        }

        // return answer;

 

 포인터 두 개를 이용해서, 탐색을 진행하고 있으며, 위 완전 탐색 코드와 똑같은 결과를 내지만, 마지막 4개의 케이스들에서 시간 초과가 난다. 왜일까? 분명 투 포인터의 알고리즘 시간 복잡도는 선형시간이므로 O(N)의 시간복잡도를 갖게 된다. 그렇다면 문제의 시간복잡도에 부합하여 정답이 되어야 하는데 O(N) 시간으로도 풀 수 없다고? 말이 안 되는 거 같다. (적어도 나의 지식선에선)

 그럼 도대체 어디가 문제일까? 나는 분명 투 포인터로 풀었다. 아마 여기까지 읽었다면 내 코드에서 문제점이 있다는 것을 알 수도 있을 것이다. 나는 내 코드의 문제점을 도저히 파악하지 못해 더 높은 수준을 가진분에게 가르침을 지도 편달받았다. 그래서 이제부터 왜 이게 투 포인터로 풀 수 없는지 알아보려고 한다.

 

투 포인터

 투 포인터는 두개의 포인터를 가지고, 일정 조건을 만족시키면서 한 방향으로 포인터가 움직인다. 내가 처음 받은 질문은 바로 아래 질문이다.

 

 

"이중 포문과 투 포인터의 차이를 알고 있는가?"

  대답하지 못했다. 정확한 차이를 몰랐기 때문이다. 친절하게 알려주심에 감사하며, 다시 상기시켜 본다면 투 포인터는 위에서 작성했던 것처럼 한 방향으로 진행한다. 즉 어떤 포인터도 다시 감소하는 방향으로 가지 않는다는 게 중요하다. 다시 감소한다고 하는 것은 아래와 같은 배열을 생각해 보면 금방 이해가 갈 것이다.

 

특정 수 보다 뒤에 있는 수 중에서 큰 수를 찾아야 하기 때문에 end는 첫 번째 수부터 가정하고 1부터 시작한다.

 

[2, 3, 3, 5]
start = 0, end = 1
start = 0, end = 2

start = 0, end = 3

start = 1, end = 2

start = 2, end = 3

 

start = 2, end = 3;

 

 

 어떤 문제가 있는지 감이 오면 좋겠다. 감소한다는 건 결국 start가 증가하면서, end도 계속 진행방향 그대로 진행해야 하는데, start = 0이고 end = 3까지 탐색을 하고 나서, 모든 배열을 탐색했으니, start를 증가시키며, end가 다시 3에서 2로 돌아온다. 즉 특정 수에 대해 다시 탐색을 하기 위해서 돌아온다고 볼 수 있다.

그래서 내 코드는 이렇듯 end가 증가했다가 다시 감소하고, 증가했다가 다시 감소하는 형태가 된다. 하지만 이건 투 포인터가 아니다.

결국 투 포인터는 위에서 말했던 것 처럼 한쪽 방향으로만 진행해야 된다는 것이다. 가령 부분수열의 합을 만족하는 구간을 찾을 때도 특정 구간을 넓혀가며 target수가 맞춰지는지 확인한다. end가 줄어드는 경우는 없었다.

 

하지만 난 무의식적으로 두개의 포인터를 사용하고 있으니, 투 포인터 알고리즘이야 라고 생각하고 있던 것이다.

 정말 큰 실수를 저지른 것이다. 또 나의 풀이는 결국 각 start에 대해서, end가 초기화되는 형식. 다시 말해 이중 포문 형태를 구현한 것이다. 그렇기 때문에 시간복잡도 상에서도 나는 O(N^2)을 구현하게 된 것이다.

 이중 포문은 각 i에 대해서, j가 초기화 되거나 줄어든다. 따라서 시간복잡도가 O(N^2)이 나오게 되는 알고리즘이다. 이게 투 포인터와의 차이점이다. (end가 증가하면 증가했지, 감소하지 않으므로)

 나는 처음에 이 문제를 보고 투 포인터를 사용해야지 라는 생각은 그저 두 개의 포인터를 가지고 이중 포문을 구현해야지라는 것과 같았던 것이다. 그래서 만약 지금 이 글을 보고 있는 사람이 내가 투 포인터를 구현했다고 생각한다면 투 포인터와 이중 포문의 차이를 알고, 내가 이중 포문을 구현한 게 아닌 것인지 다시 생각해 볼 필요가 있을 것 같다.

 투 포인터를 사용하게 되는 문제는 이렇듯 일정한 방향으로 진행하면서 탐색이 가능한 문제인지를 확인해보고 적용하면 투 포인터 알고리즘을 구현하는데 활용이 가능할 것이라는 조언과 함께 좋은 가르침을 받았다. 이 문제는 스택 풀이로 가능한데, 스택 풀이에 대해서는 따로 설명하지 않고, 이런 풀이로도 풀이가 가능하구나 정도로 생각하고 직접 한번 이해해 보면 좋을 것 같다. 어렵지 않은 코드이기 때문에.

 

	int[] answer = new int[numbers.length];
        List<Integer> stack = new ArrayList<>();

        for (int i = 0; i < numbers.length; i++) {
            // 스택이 비어 있다면 추가한다.
            if (stack.isEmpty()) {
                stack.add(i);
            } else {

                // 스택이 비어있지 않다면, 검사한다
                int index = stack.size() - 1;
                while (index > -1) {
                    int compareIndex = stack.get(index);
                    // 뒤 큰 수가 될 수 있다면
                    if (numbers[i] > numbers[compareIndex]) {
                        answer[compareIndex] = numbers[i];
                        stack.remove(index);
                    } else {
                        break; 
                    }
                    index--;
                }
                stack.add(i); 
            }
        }

        for (int i : stack) {
            answer[i] = -1;
        }
        // return answer;