부분합 - 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)

파일명 정렬 - 프로그래머스

파일명 정렬 - 프로그래머스

def solution(files):
    num_idx = 0
    splited_files, ret = [], []
    for file in files:
        for ele in file: # file이 img12.png라면
            if ele.isdigit():
                num_idx = file.index(ele)
                break
        head = file[:num_idx] # head = "img"
        next_head = file[num_idx:]
        tail_idx = len(file)  # tail이 없는 경우를 위함
        cnt = 0 
        for ele in next_head:
            cnt += 1
            if cnt == 5: # NUMBER은 최대 길이가 5라는 조건이 있음
                tail_idx = num_idx + 5 
            if ele.isalpha():
                tail_idx = next_head.index(ele) + num_idx - 1
                break
        number = file[num_idx:tail_idx] # number = "12"
        tail = file[tail_idx:] # tail = ".png"
        splited_files.append([head, head.lower(), number, tail, files.index(file)])
    splited_files.sort(key=lambda x: (x[1], int(x[2]), x[4])) 
    for each_file in splited_files:
        ret.append(each_file[0] + each_file[2] + each_file[3])
    return ret

print(solution(["img12.png", "img10.png", "img02.png", "img1.png", "IMG01.GIF", "img2.JPG"]))
print(solution(["F-5 Freedom Fighter", "B-50 Superfortress", "A-10 Thunderbolt II", "F-14 Tomcat"]))
print(solution(["img000012345", "img1.png","img2","IMG02"]))

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]