백준 1806번 부분합 풀이/해설/코드 (파이썬)

코드만 궁금한 분은 링크

GitHub - Rhyankwon/algorithms

 

문제 설명

 

숫자로 이루어진 리스트가 주어지고 임의의 숫자가 주어진다. 

 

그 리스트 안에서 연속된 숫자들의 합으로 임의의 숫자와 같거나 큰 수를 만들 수 있는데 그 연속된 숫자열들 중 가장 길이가 짧은 것의 길이를 반환해야 한다.

 

문제 풀이

 

전형적인 투포인터문제이다.

 

1. 리스트의 왼쪽 끝 부분과 오른쪽 끝 부분을 가리키는 포인터를 만든다.

 

2. for문이나 while문을 사용해서 왼쪽끝~오른쪽끝까지의 합을 계산한다.

 

3. 계산된 값이 조건으로 주어진 값보다 크면 길이를 우선 저장하고

 

4. 왼쪽포인터를 하나씩 옮기면서 여전히 조건을 만족하는지 확인한다.

 

5. 조건을 만족하지 않는 경우 다시 오른쪽 포인터를 움직인다.

 

6. 반복

 

 

딱 보자마자 전에 풀었던건가? 싶었다. 물론 풀이는 생각나지 않지만 전에 파이썬 알고리즘 인터뷰 책에 소개됐던 문제라 그런지 수월하게 풀었다. 이게 정답률이 25%라니. 이게 골드티어라니. 내가 최근 못 풀었던 문제들의 정답률이나 티어를 생각해보면 투포인터는 조금 익숙해진것같다. 빗물문제 이런건 책에 똑같은 문제가 있었는데 다시 풀 때에도 너무..헷갈렸걸 생각해보면 그리디 알고리즘이나 스택은 아직 어렵게 느끼는 것 같다.