[프로그래머스] 징검다리 건너기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

프로그래머스

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 이분 탐색과 슬라이딩 윈도우로도 해결할 수 있지만 정렬로 직관적으로 해결할 수도 있다.

우선 리스트를 생성하여 디딤돌에 적힌 숫자(밟을 수 있는 횟수)와 디딤돌의 위치를 묶어 리스트에 추가하고 디딤돌에 적힌 숫자를 기준으로 오름차순 정렬을 한다.

숫자가 적을수록 먼저 밟혀 없어질 것이기 때문이다.

디딤돌의 숫자가 적은 돌부터 불러오며 다리를 건너가고 디딤돌을 제거한다.

현재 디딤돌이 빠지면서 다음 디딤돌과 이전 디딤돌 사이의 길이를 확인하여 주어진 K보다 큰지 판별한다.

K보다 크면 더 이상 징검다리를 건널 수 없으므로 종료한다.

아직 다리를 건널 수 있다면 각 이전 디딤돌 위치와 다음 디딤돌 위치의 값을 변경하며 계속 징검다리를 건너간다.

 

1. 징검다리 위치와 각 징검다리에 적힌 디딤돌 숫자를 저장할 리스트를 생성한다. li = list()
2. 각 위치와 디딤돌 숫자를 차례로 불러오며 (디딤돌 숫자, 징검다리 위치)를 리스트에 저장한다. 이때 징검다리 위치는 인덱스에서 1을 더하여 1부터 시작하도록 저장한다. for i, s in enumerate(stones) : li.append((s, i + 1))
3. 리스트를 디딤돌 숫자를 기준으로 오름차순 정렬한다. li.sort()
4. 현재 디딤돌에서 이전 디딤돌 위치를 저장할 리스트를 생성한다. pre_idx = list(i - 1 for i in range(len(stones) + 2))
5. 현재 디딤돌에서 다음 디딤돌 위치를 저장할 리스트를 생성한다. next_idx = list(i + 1 for i in range(len(stones) + 2))
6. 리스트에서 각 디딤돌 숫자를 값으로, 위치를 인덱스로 하여 불러온다. for value, index in li
   1. 만약 현재 디딤돌을 가능한 모두 밟아 디딤돌이 제거되었을 때, 다음 디딤돌과 이전 디딤돌의 거리를 확인하여 건널 수 있는 최대 가능거리인 K보다 크면 if (next_idx[index] - pre_idx[index] > k)
      1. 정답에 해당 디딤돌 숫자 값을 저장한다. answer = value
      2. 더 이상 디딤돌을 건널 수 없으므로  징검다리 건너기를 종료한다. break
   2. 아직 징검다리를 건널 수 있으면 이전 디딤돌의 다음 디딤돌은 현재 디딤돌의 다음 디딤돌로 변경한다. next_idx[pre_idx[index]] = next_idx[index]
   3. 또한 다음 디딤돌의 이전 디딤돌은 현재 디딤돌의 이전 디딤돌로 변경한다. pre_idx[next_idx[index]] = pre_idx[index]

3. 소스코드

def solution(stones, k):
    answer = 0

    li = list()
    for i, s in enumerate(stones):
        li.append([s, i + 1])
    
    li.sort()

    pre_idx = list(i - 1 for i in range(len(stones) + 2))
    next_idx = list(i + 1 for i in range(len(stones) + 2))

    for value, index in li:
        if (next_idx[index] - pre_idx[index] > k):
            answer = value
            break

        next_idx[pre_idx[index]] = next_idx[index]
        pre_idx[next_idx[index]] = pre_idx[index]
            
    return answer