AndroidTeacher

www.acmicpc.net/problem/1806

문제 설명

수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는것 중, 가장 짧은 것의 길이를 구하는 문제이다.

풀이 과정

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

시작점과 끝점을 적절히 이동시키며 그 사이에 있는 부분들의 합을 이용해 정답을 찾는 문제이다.

처음에 시작점과 끝점을 0으로 둔다.

그 후 시작점과 끝점을 움직이면서 구간의 길이를 조절하게 되는데,

현재 구간이 S보다 작다면, 구간을 더 늘려야 하므로 끝점을 뒤로 움직여 구간을 늘려주고

현재 구간이 S보다 크다면, 구간을 더 줄여야 하므로 시작점을 뒤로 움직여 구간을 줄여준다.

처음 풀었을 때는 mysum이라는 변수 대신에,

매번 sum[start:end+1] 을 통해 합을 구해주었더니 시간초과 오류가 났다.

그래서 mysum 변수를 통해 값을 저장해두어, 그 값에 더 더하거나 빼는 방식으로 변경하였고 통과하였다.

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

start, end = 0, 0
flag = 0
shortest = n
count = 0
mysum = nlist[0]

while end < n:

    if mysum < s:   # 현재 구간합이 s보다 작으면
        end += 1    # 현재 구간의 끝점을 늘려준다
        if end < n: # 끝이 n을 벗어나면 안되기 때문에 범위 고려
            mysum += nlist[end]

    else:           # 현재 구간합이 s보다 크거나 같을 경우
        flag = 1    # 답을 찾을 수 있다는 표시
        if shortest > end-start:    # 현재까지의 최소거리보다 짧으면
            shortest = end-start+1  # 최소거리 갱신

        if start < end:             # 구간 시작점이 끝점보다 앞에있으면
            mysum -= nlist[start]   # 구간 시작점을 하나 늘린다
            start += 1
        else:                       # 구간 시작점이 끝점과 같거나 뒤에있으면
            end += 1                # 구간 끝점을 하나 뒤로 늘려서 end가 start뒤에 오도록 유지
            if end < n:
                mysum += nlist[end] # 끝점을 늘려가며 부분합 추가

if flag==1:
    print(shortest)
else:
    print(0)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

www.acmicpc.net/problem/2003

문제 설명

N개의 수열 A[1],A[2], ..., A[N]이 주어졌을 때, 수열의 부분 합이 M이 되는 경우의 수를 구하는 문제입니다.

즉, 중간중간 A[2]+A[3]+A[4] = M이라면 경우의 수가 하나 추가가 되는 문제입니다.

풀이 과정

전형적인 투포인터 문제입니다.

시작점과 끝점을 먼저 시작점에 놓습니다.

주어진 수들은 모두 자연수이기 때문에

현재 구간의 합이 M보다 작다면 현재 구간의 끝점을 늘려야 합니다.

반대로, 현재 구간의 합이 M보다 크다면 시작점을 늘려야 합니다.

같은 경우는 카운트를 하나 늘려주고, start가 end보다 앞에 있는 경우는 start를 한 칸 뒤로,

반대의 경우는 end를 한 칸 뒤로 늘려주어 start가 end뒤로 오지 않도록 유지해줍니다.

n, m = map(int, input().split())
alist = list(map(int, input().split()))

start = 0
end = 0
count = 0

while end < len(alist) and start < len(alist):
    if sum(alist[start:end+1]) < m:
        end += 1

    elif sum(alist[start:end+1]) == m:
        count += 1
        if start < end:
            start += 1
        else:
            end += 1

    else:
        start += 1

print(count)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

programmers.co.kr/learn/courses/30/lessons/67258

문제 설명

위 링크에 나온 설명처럼, 모든 종류의 보석을 적어도 1개 이상 포함하는 가장 짧은 구간을 찾는 문제입니다.

풀이 과정

이 문제는 투 포인터 유형의 문제입니다.

변수로 주어진 보석들의 목록인 gems에는 보석들이 중복되어 포함되어 있습니다.

그래서 보석의 종류만을 구하기 위해 set을 이용해 setlen에 보석의 종류를 넣어줬습니다.

start와 end를 처음지점으로 놓고, 최초의 길이는 처음부터 끝까지로 지정합니다.

end를 하나씩 늘려가며 범위를 넓혀갈건데

현재 지정한 범위에 모든 종류의 보석이 들어오게 되면

범위를 더 좁힐 수 있는지를 확인해야 합니다.

저 같은 경우는, 처음에 풀 때 마지막 부분의 elif부분을 구현하지 않아서 통과하지 못했습니다.

그래서 ["a", "b", "c", "b", "c", "d", "f", "d", "b", "e", "g", "e", "a"] 이런 케이스를 만들었더니

[5, 13] 이라는 더 짧은 구간이 있음에도 불구하고[1, 11]로 값을 반환한 것을 확인했습니다.

그 이유는, 뒤에 "e"와 "a"가 더 등장함에도 불구하고,

모든 종류의 보석이 구간안에 들어오면 앞의 start를 막았기 때문이었습니다.

이 부분을 꼭 고려하여 작성하시면 될 것 같습니다!

def solution(gems):
    answer = []
    setlen = len(set(gems)) # 보석의 종류수
    gemdict = {} # 보석 종류별로 개수를 셀 딕셔너리

    start = 0 # 투 포인터의 시작점
    end = 0 # 끝점
    sect = len(gems)+1

    while end < len(gems): # 끝점이 범위안에 있을 때만 검사

        if gems[end] not in gemdict: # 새로 발견한 보석
            gemdict[gems[end]] = 1
        else: # 기존에 존재하는 보석
            gemdict[gems[end]] += 1

        end += 1 #보석을 새로 추가했으니 end칸 한 칸 뒤로

        if len(gemdict) == setlen: # 범위안에 모든 보석이 존재할 때
            while start < end:
                if gemdict[gems[start]] > 1:  # 하나 이상 존재하면 뒤에도 더 존재한다는 뜻이므로
                    gemdict[gems[start]] -= 1  # 하나를 제거해주고
                    start += 1  # start칸을 뒤로 한칸 이동
                elif end-start < sect: # 지정한 구간보다 현재 구간이 짧으면
                    sect = end-start # 지정한 구간 바꿔주기
                    answer = [start+1, end]
                    break
                else:
                    break

    return answer

print(solution(["XYZ", "XYZ", "XYZ"]))

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !