부분합 - BOJ

부분합 - BOJ

• 대표적인 투포인터 문제
• 포인터를 두 개 설정(start, end)하여, end를 한 칸씩 늘려가며 target보다 부분합이 작을 때까지만 부분합을 더하고, target보다 커지면 start를 1칸 올려주는 식으로 구현

N, S = map(int, input().split())
li = list(map(int, input().split()))

end = 0
summary = 0
shortest_len = float('inf')

for s in range(N):
    while summary < S and end < N:
        summary += li[end]
        end += 1
    if summary >= S:
        shortest_len = min(shortest_len, end - s)
    summary -= li[s]

if shortest_len == float('inf'):
    print(0)
else:
    print(shortest_len)

n진수 게임 - 프로그래머스

n진수 게임 - 프로그래머스

• 말할 숫자들을 하나의 string으로 쭉 늘어놓고, 자기 순서가 될 때, 즉, idx % m == p - 1 일 때만 결과 ret에 붙여주는 식으로 구현
• 여기서 말할 숫자의 개수를 설정할 때 조금 애를 먹었는데, 문제에서 제시되는 충분히 큰 값인 t^2 값을 설정함으로 해결

def convert(n, base):
    T = "0123456789ABCDEF"
    q, r = divmod(n, base)
    if q == 0:
        return T[r]
    else:
        return convert(q, base) + T[r]
def solution(n, t, m, p):
    num_str = ""
    ret = ""
    for i in range(t**2):
        num_str += convert(i, n)
    for idx, j in enumerate(num_str):
        if t == len(ret):
            return ret
        if idx % m == p - 1:
            ret += j
    return ret

쿼드압축 후 개수 세기 - 프로그래머스

쿼드압축 후 개수 세기

• 분할정복 방법으로 접근한다.

  def solution(arr):
    def compress(x, y, n):
        check = arr[x][y]
        for i in range(x, x + n):
            for j in range(y, y + n):
                if arr[i][j] != check:
                    compress(x, y, n // 2)
                    compress(x, y + n // 2, n // 2)
                    compress(x + n // 2, y, n // 2)
                    compress(x + n // 2, y + n // 2, n // 2)
                    return
        ret.append(check)
  
    ret = []
    compress(0, 0, len(arr))
    return [ret.count(0), ret.count(1)]

비슷한 문제로 백준 1992 - 쿼드트리를 들 수 있다.

3진법 뒤집기 - 프로그래머스

3진법 뒤집기 - 프로그래머스

def convert(n, base):
    T = "012"
    q, r = divmod(n, base)
    if q == 0:
        return T[r]
    else:
        return convert(q, base) + T[r]

def solution(n):
    converted_n = (convert(n, 3))
    ret = 0
    for idx, ele in enumerate(converted_n):
        ret += 3 **(idx) * int(ele)
    return ret

방금그곡 - 프로그래머스

방금그곡 - 프로그래머스

def solution(m, musicinfos):
    m = m.replace("C#",'H').replace("D#", 'I').replace("F#", 'J').replace("G#",'K').replace("A#",'L')
    ret = []
    for info in musicinfos:
        s, e, name, sheet = info.split(',')
        sheet = sheet.replace("C#",'H').replace("D#", 'I').replace("F#", 'J').replace("G#",'K').replace("A#",'L')
        sh, sm = map(int, s.split(':'))
        eh, em = map(int, e.split(':'))
        time = (eh - sh) * 60 + em - sm
        while len(sheet) < time:
            sheet += sheet
        if m in sheet[:time]:
            ret.append([name, time, sh])
    if not ret:
        return "(None)"
    ret.sort(key = lambda x: (x[1], -x[2]))
    return ret.pop()[0]

풍선 터뜨리기 - 프로그래머스

풍선 터뜨리기 - 프로그래머스

• 풍선이 끝까지 남기 위해서는 이 풍선보다 작은 풍선이 없거나, 풍선의 왼쪽 오른쪽에 해당 풍선보다 큰 풍선이 존재해야함.
• 반대로 생각했을 때 양끝에서 시작했을 때 자기보다 작은 숫자의 풍선이 있다면 해당 풍선은 남을 수 있는 풍선
• 위와 같이 생각했을 때 양쪽 끝값은 무조건 남길 수 있다.
• 즉, left와 right는 자기보다 작은 숫자가 나타날 때 갱신됨
• 남는 풍선 = left에 갱신된 횟수 + right에 갱신된 횟수 + 양끝값 개수(2) - 1(중복일 경우)

def solution(a):
    ret = 2
    if 0 <= len(a) <= 2:
        return len(a)
    left = a[0]
    right = a[-1]

    for i in range(1, len(a) - 1):
        if left > a[i]:
            left = a[i]
            ret += 1
        if right > a[-1 - i]:
            right = a[-1 - i]
            ret += 1
    if left == right:
        return ret - 1
    else:
        return ret