수학과의 개발자 도전기

- 문제 : 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

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

문제 이해 

1. 컨베이어 벨트 순서대로 박스를 꺼낸다. 

2. 꺼낸 박스가 order에 나온 순서와 같다면 담는다.

3. 만약 꺼낸 박스가 order에 나온 순서와 다르면 보조 컨테이너에 추가한다.

-> 위에 이해한 걸로 컨베이어 벨트와 보조 컨테이너를 따로 계산했는데 로직이 복잡해서 그런가 계속해서 틀렸다

그래서 구글링을 통해 찾은 풀이로 이해해보자면

어차피 컨베이어벨트 순서대로 처리하는 거나 stack에 넣어서 끝에서부터 처리하는 거나 같기때문에 처음부터 모든 숫자를 stack에 추가한 후 그 값들이 order[index]의 값과 같은지 여부에 따라 로직을 수행하면 되는 것 같다. 

- 정답 풀이 :

참고한 블로그

def solution(order):
    stacks = []
    i = 1 # 현재 컨베이어 벨트에 있는 박스번호
    now = 0 # order의 현재 인덱스 
    while i < len(order) + 1:
        stacks.append(i) # 순서대로 박스 추가 
        while stacks[-1] == order[now]:
            now += 1
            stacks.pop()
            if len(stacks) == 0:
                break
        i += 1 # 컨베이어 벨트 이동 
        
    return now

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

문제 이해

• 교점을 구하는 두직선은 조합을 통해서 임의로 진행한다. 
• 두 직선의 교점이 있다면 찾는 find_intersection_point()를 실행한다
  
  • 평행하거나 일치하는 선분은 건너뛰고, 기울기가 다른 선분들에 대해서 진행한다.
  • 교점이 있고, 좌표가 모두 정수라면 튜플 형태로 반환한다.
  • 튜플로 반환하는 이유는 교점이 중복될 수 있으므로 중복을 없애기 위해 set()을 이용할 건데, 그러기 위해선 원소들을 튜플로 해야하기 때문이다. ([]를 set에 넣으면 에러난다)
• 임의의 두 선분에 정수인 교점이 존재한다면 points에 추가하고, 교점의 x좌표, y좌표를 따로 x_points, y_points에 추가한다.
• x좌표와 y좌표의 최소, 최댓값을 구하기 위해서 x_points, y_points를 사용한다.
• 가로 세로의 최대 ~ 최소 값으로 2차 행렬을 만든다. 
• 행은 좌표에서 y값, 열은 좌표에서 x값이므로 교점 (x,y)에 대해서 [y_max - y][x - x_min] 위치 값을 '*'로 바꿔준다.
• 각 행렬을 문자열로 바꿔서 반환한다. 

- 정답 풀이 : 

문제 중 여기가 가장 안됐는데, 행렬의 인덱스와 좌표 구조가 달라서 어떻게 할지 몰랐다. 

x_max/min, y_max/min 모두 좌표값이므로 (x,y)에서 x는 x_min로부터 x만큼 오른쪽으로 더 갔고, y는 y_max로부터 y만큼 줄어든 위치에 있다. (이부분은 나중에 그림 추가할 예정) 

 	for x, y in points:
        answer[y_max - y][x - x_min] = '*'  # 교점에 별 만들기
        
    return list(map(''.join, answer))

참고한 블로그

from itertools import combinations


def find_intersection_point(line1, line2):  # 두 직선의 모든 좌표가 정수인 교점 구하기
    a, b, e = line1  # ax + by + e = 0
    c, d, f = line2  # cx + dy + f = 0
    if a * d == b * c:  # 기울기가 일치하거나 평행인 경우
        return
    x = (b * f - e * d) / (a * d - b * c)
    y = (e * c - a * f) / (a * d - b * c)
    if x == int(x) and y == int(y):  # 교점이 정수라면
        return (int(x), int(y))


def solution(line):
    points = set()  # 교점
    x_points, y_points = set(), set()  # x_points : 교점의 x좌표들, y_points : 교점의 y좌표들
    for a, b in combinations(line, 2):  # 선분들 중 2개 골라서
        point = find_intersection_point(a, b)
        if point:  # 교점이 존재한다면
            points.add(point)
            x_points.add(point[0])
            y_points.add(point[1])

    x_min, x_max = min(x_points), max(x_points)  # 교점의 x좌표들 중 최소값과 최대값
    y_min, y_max = min(y_points), max(y_points)  # 교점의 y좌표들 중 최소값과 최대값

    answer = [['.'] * (x_max - x_min + 1) for _ in range(y_max - y_min + 1)]
    for x, y in points:
        answer[y_max - y][x - x_min] = '*'  # 교점에 별 만들기
    return list(map(''.join, answer))

- 시도해본 풀이 :

직선의 형태가 각각 3개씩이라 총 9가지 경우라서 모두 직접 구현했다. (기울기 있는 경우, x = c 인경우, y = c인 경우) -> 이렇게 하면 안된다

각 상황에서 정수인 교점을 모두 구해서 intersect에 저장한 다음 그 중에서 최대 행, 최소 행을 이용해 총 행의 수를 구하고 최대 열, 최소 열을 이용해 총 열의 수를 구한다.

그다음 좌표들 위치에 하나씩 *를 찍는데, 좌표를 어떻게 행렬로 옮겨야할지 모르겠어서 걸렸던 문제다. 

def check(x,y):
    if float(x).is_integer() and float(y).is_integer():
        return True
    return False

def solution(line):
    intersect = []
    
    for i in range(len(line)):
        for j in range(i + 1, len(line)):
            x1, y1, c1 = line[i]
            x2, y2, c2 = line[j]
            # 기울기 있는 직선
            if x1 != 0 and y1 != 0:
                if x2 != 0 and y2 != 0 :
                    y1, c1 = y1 / (-1 * x1), c1/ (-1 * x1) #x의 계수로 나눔 
                    y2, c2 = y2 / (-1 * x2), c2 / (-1 * x2)
                    tempy, tempc = y1 - y2, c2 - c1
                    y = tempc / tempy
                    x = y1 * y + c1
                if x2 == 0 and y2 != 0:
                    y = c2 / (-1 * y2)
                    x = -(y1 * y + c1) / x1
                if x2 != 0 and y2 == 0:
                    x = c2 / (-1 * x2)
                    y = -(x1 * x + c1) / y1 
                if check(x,y):
                    intersect.append((int(x),int(y)))
                    
            # y축에 평행한 직선 
            if x1 == 0 and y1 != 0:
                y = -1 * c1 / y1
                if x2 != 0 and y2 != 0:
                    x = -(y2 * y + c2) / x2
                    if check(x,y):
                        intersect.append((int(x),int(y)))
                if x2 != 0 and y2 ==0:
                    x = -1 * c2 / x2
                    if check(x,y):
                        intersect.append((int(x),int(y)))
            # x축에 평행한 직선 
            if x1 != 0 and y1 == 0:
                x = -1 * c1 / x1
                if x2 != 0 and y2 != 0:
                    y = -(x2 * x + c2) / y2
                    if check(x,y):
                        intersect.append((int(x),int(y)))

                if x2 == 0 and y2 != 0:
                    y = -1 * c2 / y2
                    if check(x,y):
                        intersect.append((int(x),int(y)))
                        
    max_row,min_row,max_col,min_col = 0, 1001, 0, 1001
    for i in range(len(intersect)):
        max_row, min_row = max(max_row, intersect[i][0]), min(min_row, intersect[i][0])
        max_col, min_col = max(max_col, intersect[i][1]), min(min_col, intersect[i][1])
         
         
	# 이 부분이 잘 안풀렸다 
    answer = [['.'] * (max_row - min_row + 1) for _ in range(max_col - min_col + 1)]
    intersect.sort()
    std_x, std_y = intersect[0][0], intersect[0][1]
    for i in range(len(intersect)):
        x, y = intersect[i][0] - std_x, intersect[i][1] - std_y
        answer[y][x] = '*'
        
    ans = []
    for i in range(len(answer)):
        ans.append(''.join(answer[i]))
        
    return ans