알고리즘 - Python / 백준 - 14246번 : K보다 큰 구간

14246번: K보다 큰 구간 (acmicpc.net)

14246번: K보다 큰 구간

 

---

풀이

• 일정 길이만큼의 수열이 주어지고 , 이 수열의 구간합이 k 이상인 구간이 얼마나 있는지 구하는 문제다.
• 전형적인 구간합 + 투 포인터 문제라고 생각하고 문제를 풀었다.
• 하지만 계속해서 백준 상에서 valueerror가 나왔고 , 이 문제 때문에 블로그에 글로 남기기로 했다.
• 문제 풀이 자체는 심플하게 구간합을 구해주고 , 투 포인터로 구간합에 접근하는 방식이다.
• 만약 이번 포인터에서 합이 k보다 크게 나왔다면 뒤는 볼 필요도 없다. 왜냐하면 빼는 경우가 없기 때문에 뒤쪽의 합들은 무조건 k보다 크기 때문이다. 그러므로 바로 뒤에 남아있는 개수만큼 정답에 더하고 다음으로 넘아가면 된다.
• 만약 끝까지 갔는데도 k이상이 아니다 라면 더 볼 필요가 없다. end 포인터를 더 뒤까지 못옮기니 first 포인터를 앞으로 밀어야 하는데 그러면 작아지면 작아졌지 커지지 않기 때문이다.
• 즉 더 볼 필요가 없으므로 바로 break 후 정답을 출력하면 된다.
• 그런데 풀이는 둘째치고 , 계속 valueerror가 나왔다...
• 이럴 때 자주 사용하는 해결법은 try - exception 으로 코드 부분을 살살 넣어보는 것이다.
• 예를 들어 문제가 되는 코드가 try 바깥에 있다면 , 계속 valueerror로 나올 것이고 , 만약 try 안이라면 에러를 스킵하고 답을 안 내버리니까 "틀렸습니다"가 나올 것이다.
• 이런 방식으로 테스트를 하다가 갑자기 정답이 나왔다 ㅋㅋㅋㅋ
• 두 코드의 차이가 뭔지는 모르겠지만 , 일단 올려본다.

 

 

#틀렸습니다 코드 1

import sys
n = int(sys.stdin.readline())
s = list(map(int,sys.stdin.readline().split(" ")))
oo = [0 for i in range(n+1)]
oo[0] = 0
for i in range(1,n+1):
    oo[i] = oo[i-1] + s[i-1]
k = int(sys.stdin.readline())
fp = 0
ep = 1
ans = 0


try:
    while True:
        if ep > n or fp > n:
            break
        if oo[ep] - oo[fp] <= k:
            ep += 1
        else:
            ans += (n - ep + 1)
            fp += 1
            ep = fp + 1
except Exception:
        pass
print(ans)

 

 

#정답코드 1

import sys
n = int(sys.stdin.readline())
s = list(map(int,sys.stdin.readline().strip().split(" ")))
k = int(sys.stdin.readline())


try:
    oo = [0 for i in range(n + 1)]
    oo[0] = 0
    for i in range(1, n + 1):
        oo[i] = oo[i - 1] + s[i - 1]
    fp = 0
    ep = 1
    ans = 0
    while True:
        if ep > n or fp > n:
            break
        if oo[ep] - oo[fp] <= k:
            ep += 1
        else:
            ans += (n - ep + 1)
            fp += 1
            ep = fp + 1
except Exception:
        pass
print(ans)

 

아니 그래서 두 코드가 무슨 차이인지 아직도 모르겠다.

입력단 / 구간합 + 투 포인터 세팅 / 투 포인터 실행 코드 이렇게 3 부분으로 나누고 try - exception에 왔다 갔다 넣어보고 있는데 이게 정답이라고 나온다.

 

진짜 정말 두 코드 차이가 뭔지 잘 모르겠다...

아시는 분은 댓글로 말씀 부탁드립니다.

 

일단 try - exception 을 사용하지 않고 해결해보기 위해 가장 문제가 있을 가능성이 있는 입력단 코드를 수정해보았다.

split() 과 split(" ")은 미묘하지만 차이가 있다. 

버릇처럼 써오던 split(" ")을 split()으로 바꿔보자 또 정답이 나왔다...

문제 테스트 케이스에 공백 2칸 이상 짜리가 있어서 그런가... 그러면 문제가 잘못된 거 아닌가 이런 생각도 든다.

 

 

#정답코드 2

import sys
n = int(sys.stdin.readline())
s = list(map(int,sys.stdin.readline().split()))
k = int(sys.stdin.readline())
oo = [0 for i in range(n + 1)]
oo[0] = 0
for i in range(1, n + 1):
    oo[i] = oo[i - 1] + s[i - 1]
fp = 0
ep = 1
ans = 0

try:
    while True:
        if ep > n or fp > n:
            break
        if oo[ep] - oo[fp] <= k:
            ep += 1
        else:
            ans += (n - ep + 1)
            fp += 1
            ep = fp + 1
except Exception:
        pass
print(ans)

 

 

 

맨 위의 틀린코드 1에서 split()으로만 바꾼 코드이다. 그런데 정답으로 나온다.

아무튼 넘어가고 , 그러면 strip() 으로도 해결이 되나? 생각해보았다.

왜냐면 strip()으로 공백제거니까, 공백이 2개 이상 있던걸 없애고 , 입력을 받는다? 그러면 내 생각상 정답이 나와야 한다.

그래서 시도 해보았고 정답이 나왔다.

추측하기로는 테스트 케이스에 공백 여러 칸 사이로 수가 입력된 건가 싶다.

정확히 코드의 차이를 아시는 분은 댓글 남겨주시면 감사드리겠습니다.

 

 

#정답코드 3

import sys
n = int(sys.stdin.readline())
s = list(map(int,sys.stdin.readline().strip().split(" ")))
k = int(sys.stdin.readline())
oo = [0 for i in range(n + 1)]
oo[0] = 0
for i in range(1, n + 1):
    oo[i] = oo[i - 1] + s[i - 1]
fp = 0
ep = 1
ans = 0

try:
    while True:
        if ep > n or fp > n:
            break
        if oo[ep] - oo[fp] <= k:
            ep += 1
        else:
            ans += (n - ep + 1)
            fp += 1
            ep = fp + 1
except Exception:
        pass
print(ans)

 

 

---