[241219] TIL

오늘은 선긋기와 카드점수라는 코딩 문제에 대해서 정리해보려고 한다.

 

 

[선긋기]

한 번의 선긋기는 수직선상의 한 점에서 다른 한 점까지 선을 긋는 것입니다. 선을 그을 때는 이미 선이 있는 위치에 겹쳐서 그을 수도 있습니다. 여러번 그은 곳과 한 번 그은 곳의 차이는 없습니다. 수직선은 0번 지점부터 m번 지점까지의 길이를 갖고 있습니다. 매개변수 nums에 각각의 선긋기 정보가 주어지면 0번 지점부터 m번 지점까지 연속적인 선이 그어지도록 하기 위한 선긋기 최소횟수를 반환하는 프로그램을 작성하세요. 모든 입력은 0번 지점부터 m번지점까지 연속적인 선이 그어집니다.

 

nums는 2차원 배열로 nums[i][0]은 i번째 선긋기의 시작 점,  nums[i][1]은 i번째 선긋기의 끝점이다.

 

이 문제는 시작점을 기준으로 배열을 정렬한 뒤에 시작점보다 작거나 같은 선들 중에서 끝점이 가장 긴 선들을 찾고,

해당 선의 끝점을 다시 시작점으로 설정해서 시작점이 m번 지점이 될 때까지 반복하면서 개수를 세야한다.

 

이를 어떻게 구현할 수 있을까 하다가 오늘따라 머리가 안돌아가서 gg치고 답을 확인했는데, while 반복문으로 이를 해결할 수 있었다. 아래는 코드다.

 

def solution(m, nums):
    answer = 0

    nums.sort(key= lambda x: x[0]) # 시작점을 기준으로 오름차순 정렬
    start, end, i = 0, 0, 0 # 시작점, 끝점, 인덱스
    n = len(nums) # 2차원 배열의 개수로 선의 개수를 나타냄

    while start < m: # 시작점이 m 지점보다 작을 경우 반복
		
        # 인덱스가 2차원 배열의 개수보다 작으면서
        # (중요) 선의 시작점이 이전 선의 시작점보다 작거나 같으면 반복
        while i < n and nums[i][0] <= start: 
        	
            # 반복하면서 가장 긴 선을 찾는다
            end = max(end, nums[i][1])
            
            # 끝 점이 m 지점에 도달했다면 해당 선을 카운트하고 반환
            if end == m:
                answer += 1
                return answer
                
            # 다음 선을 살펴본다.
            i += 1
		
        # 내부 반복이 끝났다면 시작점을 끝점으로 바꿔주고 해당 선을 카운트한다.
        start = end
        answer += 1
        

    return answer

 

 

[카드 점수]

N개의 카드가 일렬로 놓여져 있습니다. 각 카드에는 숫자가 적혀있습니다. 현수는 카드가 일렬로 놓여진 줄의 양 끝 즉 왼쪽 맨 끝카드와 오른쪽 맨 끝 카드 둘 중 하나 를 가져갈 수 있습니다. 현수는 양 끝에서 가져가는 방식으로 k개의 카드를 가져갈 수 있습니 다. 그리고 가져간 카드에 적혀진 숫자의 총합이 현수가 얻는 점수입니다. 일려로 놓여진 각 카드의 숫자가 매개변수 nums에 주어지고, 현수가 가져갈 수 있는 카드의 개수 k가 주어지면 현수가 얻을 수 있는 최대점수를 반환하는 프로그램을 작성하세요.

 

예를 들어 nums가 [4, 2, 1, 8, 2, 1, 7, 3] 이고 k = 4 라면 답은 16이다. (4 + 2+ 7 + 3 = 16)

 

이 문제는 슬라이딩 윈도우라는 기법을 사용해서 풀면 효율적으로 풀 수 있다. 슬라이딩 윈도우라는 것은 각 단계에서 전체 리스트를 다시 슬라이싱하지 않고, 현재 합에서 값을 더하거나 빼는 방식으로 최적화하는 것이다. 2중 for문을 돌지 않고 그냥 for문을 하나 돌면서 현재 합에서 왼쪽값을 하나 빼주고 오른쪽 값을 하나 더해주는 식이다. 

 

def solution(nums, k):
	
    n = len(nums)
    score = sum(nums[:k]) # 첫번째 합
    max_sum = score
    
    # 각 조합의 합을 구한다
    for i in range(1, k+1):
    
        # 오른쪽 값을 더하고 왼쪽 값을 빼줌으로서 합을 구한다
        score += (nums[-i] - nums[k-i])
        max_sum = max(max_sum, score)
    
    return max_sum