Coding 공부

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()

N,M = map(int,input().split())

arr = list(map(int,input().split()))


prefix_sum = [0] + arr[:]
result = 0
num_dict = defaultdict(int)
for i in range(1,N+1):
    prefix_sum[i] += prefix_sum[i-1]
    calc = prefix_sum[i] - M*i

    result += num_dict[calc]
    num_dict[calc] += 1


print(result+num_dict[0])

몇달 전에 푼 문제라 정확히 복기는 못하지만, 현재 생각 나는대로 복기를 할려고 한다.

 이 문제는 누적합을 이용해 구간의 평균합의 개수를 구하는 것이다.

현재까지의 누적합에서 지금까지의 평균의 총합을 빼주게 된다면, 

현재 위치에서 평균이 되기 위해 사라져야할 값이 보인다.

이 점을 이용해 푸는 문제이다.

구해야하는 평균이 K일때

즉 현재의 누적합 - 구간*K 을 했을때 나오는 값을 calc이라 했을 때,

이 calc 만큼만 사라지면 현재 구간 앞에서 얻을 수 있는 평균이 K인 구간의 개수가 되는 것이다.

이 문제는 누적합에서 구간의 평균합을 뺀 숫자와 일치하는 개수를 계속 누적해서 더해주면 풀 수 있는 문제이다.

그리고 마지막에 0을 더해준 이유는 현재 구간의 앞에서 나올 수 있는것을 더해준 것이니,

전체 구간에서 더해줄 필요가 있어서, 마지막에 더해주는 것이다.

6달전에 풀었던 것을 다시 복기할려니 정확하게 설명은 못했지만, 위와 같은 방법을 활용하면 된다.

from itertools import combinations

def solution(info, query):
    answer = []
    languages = ['cpp','java','python','-']
    positions = ['backend','frontend','-']
    careers = ['junior','senior','-']
    soulfoods = ['chicken','pizza','-']
    total_dict = {language : {position : {career : {soulfood : [0]*100001 for soulfood in soulfoods} for career in careers}  for position in positions} for language in languages}
    for info_string in info:
        language,position,career,soulfood,score = info_string.split(' ')
        score = int(score)
        info_list = [language,position,career,soulfood]
        for i in range(1<<4):
            temp = []
            for j in range(4):
                if i&(1<<j):
                    temp.append(info_list[j])
                else:
                    temp.append('-')
            total_dict[temp[0]][temp[1]][temp[2]][temp[3]][score] += 1
    for language in total_dict.keys():
        for position in total_dict[language].keys():
            for career in total_dict[language][position].keys():
                for soulfood in total_dict[language][position][career].keys():
                    for score in range(1,100001):
                        total_dict[language][position][career][soulfood][score] += total_dict[language][position][career][soulfood][score-1]
    for query_string in query:
        language,position,career,last_query = map(str.strip,query_string.split('and'))
        soulfood,score = last_query.split(' ')
        score = int(score)
        answer.append(total_dict[language][position][career][soulfood][100000] - total_dict[language][position][career][soulfood][score-1])
    return answer

처음 풀었던 방식이다. dictionary를 이용해서, 각 쿼리에 맞게 저장을 하는 방식이다. 각 쿼리를 저장할때 나올수 있는 겨우의 수는 16가지이다. 그걸 만들기 위해서 조합을 만드는 방식으로 중간에 비트마스크를 활용해서 각조합을 만들고, 저장을 해주었다.

그리고 각 score에 대해서 그 이상값을 추출하면 시간이 오래걸리므로, prefix_sum을 통해 저장을 해놓은 뒤, query가 들어왔을때, 최대값이 10만에서 찾고자 하는 값-1을 빼줘서 찾아줬다.

해당 코드의 효율성 통과 시간이다.

def solution(info, query):
    answer = []
    index_dict = {'-':0,
    'cpp': 1,
    'java':2,
    'python': 3,
    'backend':1,
    'frontend' :2,
    'junior':1,
    'senior':2,
    'chicken':1,
    'pizza':2,
    }
    store_query = [[0]*100001 for _ in range(108)]
    for info_string in info:
        language,position,career,soulfood,score = info_string.split(' ')
        score = int(score)
        for ind1 in [0,index_dict[language]]:
            for ind2 in [0,index_dict[position]]:
                for ind3 in [0,index_dict[career]]:
                    for ind4 in [0,index_dict[soulfood]]:
                        ind = ind1*27 + ind2*9 + ind3*3 + ind4
                        store_query[ind][score] += 1
    for ind in range(108):
        for score in range(1,100001):
            store_query[ind][score] += store_query[ind][score-1]

    for qu in query:
        language,position,career,last_query = map(str.strip,qu.split('and'))
        soulfood,score = last_query.split(' ')
        score = int(score)
        ind = index_dict[language]*27 + index_dict[position]*9 + index_dict[career]*3 + index_dict[soulfood]
        answer.append(store_query[ind][100000] - store_query[ind][score-1])
    

    return answer

두번째 코드는 www.youtube.com/watch?v=FX9n1PFv2K4 의 코드에서 차용해와서 푼 방식이다.

dicationry로 키를 만드니 너무 난잡해 보여서 2차원 배열로 만든 방식이다.

이 방식으로 했을때 시간이 좀 더 빨랐다.

import bisect

def solution(info, query):
    answer = []
    index_dict = {'-':0,
    'cpp': 1,
    'java':2,
    'python': 3,
    'backend':1,
    'frontend' :2,
    'junior':1,
    'senior':2,
    'chicken':1,
    'pizza':2,
    }
    store_query = [[] for _ in range(108)]
    for info_string in info:
        language,position,career,soulfood,score = info_string.split(' ')
        score = int(score)
        for ind1 in [0,index_dict[language]]:
            for ind2 in [0,index_dict[position]]:
                for ind3 in [0,index_dict[career]]:
                    for ind4 in [0,index_dict[soulfood]]:
                        ind = ind1*27 + ind2*9 + ind3*3 + ind4
                        store_query[ind].append(score)
    for ind in range(108):
        store_query[ind].sort()
    for qu in query:
        language,position,career,last_query = map(str.strip,qu.split('and'))
        soulfood,score = last_query.split(' ')
        score = int(score)
        ind = index_dict[language]*27 + index_dict[position]*9 + index_dict[career]*3 + index_dict[soulfood]
        cnt = len(store_query[ind]) - bisect.bisect_left(store_query[ind],score)
        answer.append(cnt)
    

    return answer

마지막은 구간합으로 하면  16*100000번의 계산이 필요하므로 실행시간이 오래걸린다. 그래서 해결한 방법중 하나가 bisect라는 라이브러리를 활용한것이다.

bisect에 있는 기능 중 bisect_left는 정렬된 리스트에서, 순서대로 정렬되는 것을 유지하고, 현재값이 들어갈수 있는 위치의 왼쪽좌표를 알려준다. 즉, 자기보다 작은 값의 위치를 알려주는 것이다. 이걸 이용해서 그 리스트의 길이에서 해당 index의 위치를 빼주면 이상을 구할 수 있게된다.

이걸로 했을때가 시간이 제일 빨랐다. bisect를 이용하지 않고, 이분탐색을 직접구현해도 된다.

해당 문제는 query로 나올수 있는 경우의 수를 모두 예상하고 저장해놓는게 힘들었다.

def changeSeconds(times):
    return  sum(int(x) * 60 ** i for i, x in enumerate(reversed(times.split(':'))))
def changeString(times):
    hour = times//3600
    minute = (times-hour*3600)//60
    seconds = times%60
    return "%02d:%02d:%02d"%(hour,minute,seconds)

def solution(play_time, adv_time, logs):
    answer = ''
    play_time =  changeSeconds(play_time)
    adv_time = changeSeconds(adv_time)
    time_laps = [0]*(play_time+1)
    for timeString in logs:
        start_time,end_time = map(changeSeconds, timeString.split('-'))
        time_laps[start_time] += 1
        time_laps[end_time] -= 1

    for ind in range(1,play_time+1):
        time_laps[ind] += time_laps[ind-1]
    max_times = sum(time_laps[:adv_time])
    max_start_time = 0
    current_sum_times = max_times
    for ind in range(1,play_time+1-adv_time):
        current_sum_times = current_sum_times - time_laps[ind-1] + time_laps[ind+adv_time-1]
        if current_sum_times > max_times:
            max_times = current_sum_times
            max_start_time = ind
    answer = changeString(max_start_time)
    return answer

구간합을 이용해 푼 방식이다.

각 start와 end_time에 각각 +1, -1을 해주고,

누적값을 해준다. 그리고 그 광고시간의 길이만큼의 sum을 해주면, 해당 시간동안 보는 광고사용자의 수가 될수 있다.

def changeSeconds(times):
    return  sum(int(x) * 60 ** i for i, x in enumerate(reversed(times.split(':'))))
def changeString(times):
    hour = times//3600
    minute = (times-hour*3600)//60
    seconds = times%60
    return "%02d:%02d:%02d"%(hour,minute,seconds)

def solution(play_time, adv_time, logs):
    answer = ''
    play_time =  changeSeconds(play_time)
    adv_time = changeSeconds(adv_time)
    time_laps = [0]*(play_time+1)
    diff = [0]*(play_time+1)
    for timeString in logs:
        start_time,end_time = map(changeSeconds, timeString.split('-'))
        diff[start_time] += 1
        diff[end_time] -= 1
    diff_count = 0
    for ind in range(1,play_time+1):
        time_laps[ind] += time_laps[ind-1] + diff_count
        diff_count += diff[ind]

    max_times = time_laps[adv_time]
    max_start_time = 0
    for ind in range(1,play_time+1-adv_time):
        if time_laps[adv_time+ind] - time_laps[ind] > max_times:
            max_times = time_laps[adv_time+ind] - time_laps[ind]
            max_start_time = ind
    answer = changeString(max_start_time)
    return answer

같은 원리이지만, sum 하는 방식을 개선을 한것이다. diff_count를 해줘서 해당구간에서 보는 인원을 누적해줘서 하는 방식이다.

# 3020 개똥벌레

N,H = map(int,input().split())

bottom_list = [0]*H
top_list = [0]*H


for ind in range(N):
    height = int(input())
    if ind%2:
        top_list[height] += 1
    else:
        bottom_list[height] += 1

for ind in range(1,H):
    bottom_list[ind] += bottom_list[ind-1]
    top_list[ind] += top_list[ind-1] 

bottom_list.append(bottom_list[-1])
top_list.append(top_list[-1])
min_result = float('inf')
min_cnt = 0
for k in range(H):
    bottom_cnt = bottom_list[-1] - bottom_list[k]
    top_cnt = top_list[-1] - top_list[(H-1)-k]
    if bottom_cnt +top_cnt < min_result:
        min_result = bottom_cnt+top_cnt
        min_cnt = 1
    elif bottom_cnt + top_cnt == min_result:
        min_cnt += 1

print(min_result,min_cnt)

prefix sum 을 이용해서 푼 방식이다.  종유석과 석순을 구분해서 prefix_sum을 해주고, 그 다음에 상황에 맞게 최저값을 구해주면 된다.

# 3020 개똥벌레
import sys


N,H = map(int,sys.stdin.readline().split())

bottom_list = [0]*(H+1)
top_list = [0]*(H+1)

for ind in range(N):
    height = int(input())
    if ind%2:
        top_list[height] += 1
    else:
        bottom_list[H-height+1] += 1
for ind in range(H-1,0,-1):
    top_list[ind] += top_list[ind+1]


for ind in range(2,H+1):
    bottom_list[ind] += bottom_list[ind-1]

min_total = N
min_cnt = 0
for ind in range(1,H+1):
    sub_sum = bottom_list[ind] + top_list[ind]
    if sub_sum < min_total:
        min_total = sub_sum
        min_cnt = 1
    elif sub_sum == min_total:
        min_cnt += 1
print(min_total,min_cnt)

이 코드는 석순의 저장 방식을 다르게 하여, 한번에 계산이 편하게 한 방식이다.