일단 하나를 해보자

https://school.programmers.co.kr/learn/courses/30/lessons/12938

답지 안보고 풀었을 때 쾌감이란~

모든 문제가 이렇게 잘 풀렸으면 좋겠다 

정말 코테는 종이 없으면 못풀겠다 

갤탭씨에게 감사인사를 드립니다. 

문제 풀이

{} 집합에 어떤 수가 올지, 몇 개가 올지는 모르지만 

조건 

집합 안의 수 합이 S가 되는 애들

그리고 집합 수끼리 곱한 수가 최대인 애들을 return 해라 

처음에는 {} 집합 안에 있는 수를 주는 줄 알았다. 

매개변수를 보니 n 집합 안의 수의 갯수, s 집합 안의 수들의 합  

이렇게 두가지만 주어졌다. 

집합 안의 수들의 곱이 최대인 애가 답이라서 

합해진 S를 찢어서 곱해봤다. 

총합S 나누기 집합갯수 를 했을 때 몫이 0보다 작거나 0이면 바로 return -1

나눴을 때 나머지 없이 몫이 떨어지면 간단! [몫, 몫, 몫] 이렇게 몫이 n개 있으면 됐다.

나머지가 있으면 나머지를 처리해야했다. 집합끼리 곱했을 때 최대가 되도록!

(처음에는 n이 2개라고 가정하고 식을 써봤다. 곱한 최대값을 어떻게 비교할지가 막막해서. 그런데 막상 보니까 나머지 없이 잘 나눠떨어지는 애들은 전부 집합이 몫으로 같음. 이걸보니 집합끼리 수 차이가 작을수록 모두 곱했을 때 결과가 크구나가 보였다. 기준을 몫으로 나눠떨어지는 애들 아닌애들로 처리해야함이 보였다.)

<막혔던 부분>

인덱스 초과를 자꾸 시켰다. 

문제1. answer 답 배열에 몫을 n번 저장하면 되는데  n번을 while안에서 1씩 없애주면서 n 반복해서 넣어주었다. 

넣는 값을 s//n로 해놔서 n이 값이 변경되었다.  

k =n으로 해서 k를 하나씩 빼줬다. 지금 보니 그냥 s//n 몫을 제대로 선언하는게 나을듯

문제2. 아직 answer 에 값 넣지도 않았는데 나머지를 처리한다고 answer[0] = 값을 할당했다. 이렇게 했다.  아직 0번째 값은 없는데.. answer은 빈 배열인데요.. 그리고 답은 (집합의 수는) 작은 수부터 정렬을 원해서 나머지를 뒤에서부터 넣어줘야했다. 

나머지를 1씩 쪼개서 맨뒤에서부터 하나씩 더해줬다. 

range로 범위정할 때 잘 안돼서 찾아봤다. 

my_list = [1, 2, 3, 4, 5]

for i in range(len(my_list) - 1, -1, -1):
    print(my_list[i])

시작: len(my_list_ -1)

맨 뒤!

범위: -1

맨뒤! 앞에서 조회하는 range와 마찬가지로 범위는 하나 더 한 값으로 써준다. 근데 얘는 마이너스가 붙은.. 맨뒤에서 첫번째까지 

스텝: -1

한번 작동할 때마다 인덱스를 1칸씩 이동한다. 

결과 

def solution(n, s):
    answer = []
    max =0
    if s//n <=0:
        return [-1]
    elif s%n ==0:
        k = n
        while(k>0):
            answer.append(s//n)
            k -= 1
    elif s%n >0:
        k = n
        while(k>0):
            answer.append(s//n)
            k-= 1
        for i in range( len(answer)-1, len(answer)-s%n-1,-1):
            answer[i] += 1
            
            
            
    return answer

앗!!

게비스콘~~

시간초과돼서 찾았는데 print 있어서 그랬네 짜슥아~~!! 

https://school.programmers.co.kr/learn/courses/30/lessons/178870#

처음에는 이중 for문으로 풀었다. 테스트 코드는 통과하였으나 

시간 초과가 났다. 

어떻게 애들을 더해서 k를 비교할까 고민하다가 

처음에 이중for문으로 생각한 방법은 이렇게 시작 인덱스를 줄여서 더해가다가 k 값과 비교해서 해야지~였다.

def solution(sequence, k):
    answer = []
    min_difference = float('inf')
    selected_numbers =None
    for i in range(len(sequence)):
        total_sum =0
        for j in range(i, len(sequence)):
            total_sum+= sequence[j]
            if total_sum ==k: 
                if (abs(j-i) < min_difference):
                    min_difference = abs(j-i)
                    selected_numbers = (i,j)
                    break

    return selected_numbers

문제는 조회하는 배열의 최대 길이가

5 ≤ sequence의 길이 ≤ 1,000,000

였기에 이중포문을 하면 이차시간으로 계산되어 제곱이 되어 초과된다. 

시간복잡도 참고)

그다음에 for문을 사용하지 않고 어떻게 맨앞자리 인덱스를 줄일지 고민했다. 

여기서 오래 막혔다. 

시간초과 없애려고 이중포문 없애고 해봤는데

i부터 j까지 계속 더해지는거 i를 조작못했다.

2차 시도 (사실 2차는 아니긴한데..)

    index = 0
    start = 1
    
    for i in range(start, len(sequence)):
        sequence[index] += sequence[i]
        print("sequence[index]:",sequence[index])
        if i == len(sequence)-1:
            index += 1
            start +=1

    return selected_numbers

이 코드는 그저 처음부터 끝까지 더하기만 한다. 

처음에 포인터로 시작과 끝을 가리키는 방법을 쓰려했는데 for문으로 어차피 다 조회하니까 시작만 

가리키면 되겠다고 생각해서 반복문에 집착한 것이 나의 실수였다..결국 한참 헤매다가 답지를 봤다.

최종 코드 

def solution(sequence, k):
    answer =[]
    start = 0
    end =0
    min = 1000000000
    total = sequence[0]
    while (start <= end < len(sequence)):
        if (total == k):
        
            if min > end- start+1:
                min = end - start+1
                answer =[start, end]
            total -= sequence[start]
            start += 1
        elif (total < k):
            end+= 1
            if end< len(sequence):
                total += sequence[end]  
        elif (total > k):
            total -= sequence[start]
            start += 1
          
    return answer

1.  start end 시작과 끝 두 포인터의 관계 설정이 중요

start <= end

시작포인터와 끝포인터는 같은 곳에서 시작하고 만나서 같을 수는 있어도 넘어서는 안된다. 

나는 계속 전체 배열의 길이만 넘지 말라고 맞춰서 리스트에서 벗어나는 에러가 발생했다. 

2. 전체 배열의 값을 더하는 total을 어떻게 처리할지

total 정의할 때 sequence[0] 첫번째 값을 할당하고 시작하면 된다. 

total은 구하고자 하는 k값을 기준으로 나뉜다. 

<바로 생각하기 힘들었던 부분>

1. total == k일 때 시작과 끝 두사이 거리가 최소인 값을 찾고 나서 

배열 끝까지 다시 시작과 끝을 움직여야 하는데 

end를 움직여도 될거라 생각했다. 

그렇게 한 결과 end값이 먼저 배열범위보다 커져버려서 테스트 통과를 못했다. 

전체에서 start인덱스의 값을 빼주고 start인덱스를 옮기는 것으로 수정했다. 

2. while범위에서 배열의 범위만큼 돌라고 했으니 문제 없을거라 생각했지만

end를 하나씩 추가하고  그 값을 sequence의 인덱스로 넣기 위해 조건을 안 걸면 저렇게 에러가 났다. 

결론 반복문에 그만 집착하고 효율적인 풀이를 생각해보자

컴퓨터가 우리 뇌구조랑 비슷하겠다는 생각을 했다. 생각한게 맞을 수도 있으니 포기말고 구현해봐라