수학과의 개발자 도전기

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/131130

스스로 푼 문제다!

문제 이해

처음엔 무슨 문제지 하면서 하나도 이해가지 않았다. 

예제를 기반으로 풀어보니 

- cards의 원소 - 1는 다음 인덱스의 값을 가리키고 있고,

- 0인덱스부터 시작하는데 인덱스 i에서 cards[i]로 이동한 다음,

- cards[i]를 방문하지 않았다면 cards[cards[i]]로 계속 이동하는 문제였다.

위와 같은 방식으로 계속 이동하다가 멈추었을 때가 하나의 박스 세트다. 각 갯수를 저장한 다음 가장 큰 값과 두번째로 큰 값의 곱을 반환하면 된다고 이해했다. 

풀이 이해

• cards의 값과 인덱스를 통일하기 위해서 전체 값에 -1을 한다. 
• 방문하지 않은 인덱스를 구별할 것이므로 visit를 초기화하고, 각 박스 세트의 박스 갯수를 세기위해 box_set도 초기화한다. 
• 인덱스 0부터 순차적으로 진행한는데, 방문하지 않은 인덱스 i에 대해 while문을 돌린다. 
  • index = cards[i]로 설정한뒤 visit[index] == 1이라면 while문을 break 하고
  • 아니라면 방문처리와 갯수를 증가하고 cards[index]로 이동한다.(index = cards[index])
• 갯수가 첫 번째로 많은 세트와 두번째로 많은 세트를 구해야하므로 내림차순으로 정렬한다. 
• 문제에서 세트가 한번에 끝나면 0을 반환하라고 했으므로 box_set가 하나만 있으면 0을 반환하고
• 아니라면 가장 큰 두 값의 곱을 반환한다. 

- 정답 풀이 :

def solution(cards):
    n = len(cards)
    for i in range(n):
        cards[i] -= 1
        
    box_set = []
    visit = [0] * n
    for i in range(n):
        if not visit[i]:
            visit[i], count, index = 1, 1, cards[i]
            while True:
                if visit[index]:
                    box_set.append(count)
                    break
                visit[index] = 1
                count += 1
                index = cards[index]            
    box_set.sort(reverse = True)
    
    if len(box_set) == 1:
        return 0
    else:
        return box_set[0] * box_set[1]

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/134239

스스로 푼 문제다!

문제 이해

처음에는 ranges의 원소가 이해가지 않았는데, [a,b]형태라면 범위는 [a, 마지막 인덱스 + b] (b는 0이하인 정수이므로 더한다)인 것이다. 그래서 [a, 마지막 인덱스 + b]에 해당하는 넓이를 구하면 된다. 

풀이 이해

• 우박수열(sequence) 구한다. i 인덱스에 해당하는 값이 i번째 수열의 값이다. 
• 마지막 x 좌표는 마지막 인덱스 값이므로 last = len(sequence) - 1 해준다.
• ranges 원소를 탐색하면서 시작과 끝이
  • 유효한 경우(end > start) 해당 범위의 넓이(사다리꼴)를 구해서 answer에 추가한다. 
  • 유효하지 않은 경우(end < start)는 -1을 answer에 추가한다.
  • end == start인 경우 넓이는 존재하지 않으므로 0을 answer에 추가한다. 

- 정답 풀이 : 

각 구간에 해당하는 넓이를 각각 따로 계산해서 answer에 추가하니 정답이 떴다!

def get_area(a, b, sequence):
    # 높이가 1인 사다리꼴의 넓이 
    return (sequence[a] + sequence[b]) / 2

def solution(k, ranges):   
    K = k
    sequence = [k]
    while K != 1:
        if K % 2 == 0:
            K //= 2
        else:
            K = K * 3 + 1        
        sequence.append(K)  
    
    last = len(sequence) - 1
    answer = []
    for each in ranges:
        start, offset = each
        end = last + offset
        if end < start:
            answer.append(-1.0)
        if end == start:
            answer.append(0.0)
        if end > start:
            temp = 0
            for i in range(start, end):
                temp += get_area(i, i + 1, sequence)
            answer.append(temp)
       
    return answer

- 시도해본 풀이 :

이 풀이로는 10퍼센트만 맞혔는데, 각 단위 구간에 해당하는 넓이를 areas에 저장한 뒤 start, end가 유효할 때 areas의 start부터 end까지의 합을 구하려했다. 이렇게 구하면 원하는 값이 안 나오는 것 같다.

def get_area(a, b, sequence):
    # 높이가 1인 사다리꼴의 넓이 
    return (sequence[a] + sequence[b]) / 2

def solution(k, ranges):   
    K = k
    sequence = [k]
    while K != 1:
        if K % 2 == 0:
            K //= 2
        else:
            K = K * 3 + 1        
        sequence.append(K)
        
    last = len(sequence) - 1
    areas = [0]
    for i in range(1, last + 1):
        areas.append(get_area(i - 1, i, sequence))
        
    answer = []
    for each in ranges:
        start, offset = each
        end = last + offset
        if 0 <= start <= last and 0 <= end <= last:
            if end < start:
                answer.append(-1)
            if end == start:
                answer.append(0)
            if end > start:
                answer.append(sum(areas[start : end + 1]))
        else:
            answer.append(-1)
                

    return answer