[TEST] Frog Possible Distance

What is the longest distance that they can possibly between each other? 

이번에 코딩테스트로 만났던 문제를 소개하고자 한다.

There are N blocks, numbered from 0 to N-1, arranged in a row.
A couple of frogs were sitting together on one block when they had a terrible quareel.
Now they want to jump away from one another so that the distance between them will be as large as possible.
The distance between blocks numbered J and K, where J <= K is computed as K - J + 1 
The frogs can only jump up, meaning that they can move from one block to antther only if the two blocks are adjacent and the second block is of the same or greater height as the first.
What is the longest distance that they can possibly create between each other. if they also chose to sit on the optimal starting block initailly? 

def soluton(block):

요약

개구리 두마리가 있다.

개구리 두마리는 한마리는 왼쪽으로, 한마리는 오른쪽으로 이동한다.

이동할때, 제일 높은 블록으로 이동하고 낮은 블록이 나타나면 멈춘다.

이때 첫번째 개구리와 두번째 개구리가 위치하고 있는 블록거리를 리턴하면 된다. 

 

아이디어

우선 가장 긴 블록거리를 찾으려면 첫번쨰 개구리와 두번쨰 개구리가 최적의 위치에 있어야 최대 거리를 구할 수 있다.

그렇다면 어떻게 하면 효율적으로 최적의 위치를 빠르게 찾을 수 있을까가 이 문제의 핵심이었다. 

 

선언된 블록들 모든 위치를 탐색하고 그중에서 가장 넓은 거리를 찾기로 했다. 

최적의 위치를 찾아 개구리들의 사이의 최장거리를 구하는 것이 이 문제의 핵심이다. 

 

1. 우선 나는 첫번째 개구리와 두번째 개구리가 이동할 블록들을 슬라이스로 쪼개서 각각 나눠 이동한 거리를 체크했다. 

2. 첫번째 개구리와 두번째 개구리들이 이동방향이 다르기 때문에 편하게 계산하기 위해 첫번째 개구리를 역순으로 배치했다. 

 

3. 이후 첫번째 개구리는 첫번째 블록에서 두번째 블록과 비교하면서, 만약에 두번째 블록이 높다면 result1에 1을 추가했다. 

     그렇지 않으면, 멈추도록 했다. 

4. 두번째 개구리도 같은 논리로 result2에 이동거리를 측정했다. 

 

5. 최종 result에는 처음 시작한 위치에서의 두개구리 사이의 거리를 합쳤다. 

 

6. 마지막으로 이렇게 추가된 두 개구리의 사이 거리 중 가장 큰 거리를 리턴하도록 했다. 

 

def solution(blocks):
    result = [] 

    for i in range(len(blocks)):

        start_point = i 
        first_frog = blocks[:start_point+1]
        first_frog.reverse()

        second_frog = blocks[start_point:]

        result1 = [] 
        for k in range(len(first_frog)-1):
            for j in range(k+1,len(first_frog)):
                a = first_frog[k]
                b = first_frog[j]
                if a <= b:
                    result1.append(1)
                elif a > b:
                    continue
        result2 = [] 
        for k in range(len(second_frog)-1):
            for j in range(k+1,len(second_frog)):
                a = second_frog[k]
                b = second_frog[j]
                if a <= b:
                    result2.append(1)
                    k = k+1
                elif a > b:
                    k = k+1
                    continue
                    
        result.append(sum(result1) + sum(result2))
        LongestDistance = max(result)
        return LongestDistance

문제점

우선 반복문이 너무 많다.

어떻게 효율적으로 문제를 풀어가야할지 추후 알고리즘을 생각하면서 다시한번 풀어봐야겠다. 

 

 

문제출처 

 

https://www.chegg.com/homework-help/questions-and-answers/n-blocks-numbered-0-n-1-arranged-row-couple-frogs-sitting-together-one-block-terrible-quar-q79338186