[Python] 백준, 1806(두 포인터)

0.

일주일 동안 블로그를 신경 쓰지 못했다. 핑계 아닌 핑계를 대자면, 내가 작성한 코드를 ColorScript를 통해서 업로드 중이었는데, 깨짐 현상과 줄 간격이 라인 넘버와 맞지 않는 현상이 너무 많이 발생해서 다른 해결책을 강구해야 했다. 그러던 중 티스토리에서 제공하는 코드 블럭을 알게 되었는데, 라인 넘버, 하이라이트, 폰트 등 html/css를 이용해 수정해주면 깔끔하고 더 효율적인 코드 작성이 가능하더라. 문제는 각종 블로그에서 지시하는 대로 따라갔는데도 원하는 스타일이 안 나와서 한참을 헤매다가 오늘에서야 그럴듯한 모양새가 잡혔다. 지난주는 주간 주라 바쁘기도 했고, 코드 첨부 문제도 있었고... 여러모로 험난했다. 그래도 문제는 꾸준히 풀었기 때문에 오늘 그동안 푼 문제들 정리도 할 겸 업로드 양이 좀 많을 것 같다.

 

 

시작해보자.

 

https://www.acmicpc.net/problem/1806

1806번: 부분합

 

주어진 정렬에서 합이 S이상이 되는 가장 짧은 길이를 구해야 한다. 고려해야할 점은 무작위 정렬이기 때문에 이진 탐색에서 써먹었던 두 포인터랑은 살짝 다르다는 것. 문제는 직관적으로 이해가 잘 됐지만, 풀이로 구현하는 건 쉽지 않았다. (불과 몇일 지나고 다시 보니, 한 번만 확실히 해놓으면 앞으로는 헷갈릴 일이 없겠다는 생각이 들기는 한다.)

 

 

# PYTHON CODE (1) - 1차 시도

import sys

n, s = map(int, sys.stdin.readline().split())
list1 = list(map(int, sys.stdin.readline().split()))

pl, pr = 0, n - 1

while True:
    x = sum(list1[pl:pr + 1])
    if x > s:
        if x - list1[pl] - list1[pr] > s:
            pl += 1
            pr -= 1
        elif x - list1[pr] > s:
            pr -= 1
        elif x - list1[pl] > s:
            pl += 1
        else:
            print(pr - pl + 1)
            break
    else:
        print(0)

(코드 블럭 이쁘지 않나? 드래그할 때 색상도 연노랑으로 맞췄는데 ㅎ)

 

우선, 옛 기억을 더듬었을 때 두 포인터를 양쪽 끝을 잡고 한 칸씩 줄이는 방법으로 풀었던 것 같아서 pl, pr을 각각 처음과 끝의 인덱스로 잡았다. 이 방법의 가장 첫 번째 문제점은 정렬되지 않은 배열이라는 점을 고려하지 않았다는 거다. 그렇기에 쓸데없는 조건문이 달릴뿐더러 정답도 내지 못했다. 두 번째는 모든 경우를 보는 게 아니라는 점이다. 처음과 끝에서 한 칸씩 줄어들기 때문에 모든 경우를 살필 수 있을 것 같지만, 실제로 그렇지 않은 케이스들이 여럿이었다.

 

 

# PYTHON CODE (2) - 2차 시도

import sys

n, s = map(int, sys.stdin.readline().split())
list1 = list(map(int, sys.stdin.readline().split()))

pl, pr = 0, 1
answer = n

while pr < n:
    x = sum(list1[pl:pr + 1])
    while x >= s:
        answer = min(answer, pr - pl + 1)
        if x - list1[pl] >= s:
            pl += 1
            x -= list1[pl]
        else:
            break
    pr += 1

print(answer)

채점 결과는 시간 초과. sum부분이 의심스럽기는 하지만, 처음과 끝이 아니라 pl, pr = 0, 1로 지정해서 맨 앞에서 점진적으로 훑는 방법을 생각했다. 지금 sum에 대해 잠시 고찰해봤는데, 매 루프마다 지정된 인덱스의 합을 구하는 것 보다 단순히 덧셈/뺄셈을 진행해주는 게 직관적으로도 효율적이지 않을까 하는 생각이 든다.

 

 

 

 

# PYTHON CODE (3) - 정답 코드

import sys

N, S = map(int, sys.stdin.readline().split())
arr = list(map(int, sys.stdin.readline().split()))

pl, pr, x = 0, 0, arr[0]
answer = 100001

while True:
    if x >= S:
        answer = min(answer, pr - pl + 1)
        x -= arr[pl]
        pl += 1
    else:
        if pr == N - 1:
            break
        else:
            pr += 1
            x += arr[pr]
            
if answer == 100001:
    answer = 0
print(answer)

위의 생각을 반영해준 코드. 출력값을 고려해 answer값이 변하지 않았을 때의 조건을 추가해줬고, pr이 마지막 인덱스가 되기 전까지 루프를 계속해준다. 초기 합은 pl, pr = 0, 0이므로 배열의 첫 번째 값으로 지정했다.