모서리 IT 블로그

문제 설명

계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다.
아래 그림은 m = 4, n = 3 인 경우입니다.

가장 왼쪽 위, 즉 집이 있는 곳의 좌표는 (1, 1)로 나타내고 가장 오른쪽 아래, 즉 학교가 있는 곳의 좌표는 (m, n)으로 나타냅니다.
격자의 크기 m, n과 물이 잠긴 지역의 좌표를 담은 2차원 배열 puddles이 매개변수로 주어집니다. 오른쪽과 아래쪽으로만 움직여 집에서 학교까지 갈 수 있는 최단경로의 개수를 1,000,000,007로 나눈 나머지를 return 하도록 solution 함수를 작성해주세요.

제한사항

• 격자의 크기 m, n은 1 이상 100 이하인 자연수입니다.
  • m과 n이 모두 1인 경우는 입력으로 주어지지 않습니다.
• 물에 잠긴 지역은 0개 이상 10개 이하입니다.
• 집과 학교가 물에 잠긴 경우는 입력으로 주어지지 않습니다.

입출력 예

입출력 예 설명

내 문제풀이

1. 웅덩이를 피해서 되돌아가는 경우 없이 오른쪽 또는 아래로만 이동하면 모두 최소 이동 경로가 된다.

2. 집의 위치 값을 1로 두고, 각 격자의 칸마다 해당 칸으로 도착하는 서로 다른 경로(위쪽에서 아래로 오는 경우, 왼쪽에서 오른쪽으로 오는 경우)의 갯수를 저장한다.

3. 위쪽, 왼쪽에서 해당 칸으로 올 수 있으므로 위쪽, 왼쪽의 값을 더하며 격자를 채워나간다.

4. 웅덩이로 도착하는 경로는 없으므로 0으로 저장한다.

내 코드 - 파이썬

def solution(m, n, puddles):
    matrix = [[0 for i in range(m+1)] for i in range(n+1)]
    matrix[1][1] = 1
    
    for r in range(1, n+1): #행 = n
        for c in range(1, m+1): #열 = m
            if matrix[r][c] == 1: #집
                continue
            if [c, r] in puddles:
                matrix[r][c] = 0
            else:
                matrix[r][c] = matrix[r-1][c] + matrix[r][c-1]   
            
    return matrix[-1][-1]%1000000007

문제 설명

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.

각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.
각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요.

제한사항

• 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다.
• money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다.

입출력 예

내 문제풀이

1. 집이 원형으로 배치되어 있기 때문에 단순하게 바로 옆 집을 털면 안되는 조건만 고려하면 안되고, 첫 번째 집과 마지막 집을 동시에 털 수 없는 점도 고려해야 한다.

2-1. 먼저 첫 번째 집을 제외하고 마지막 집을 포함하는 경우 첫 번째 집의 돈을 0으로 설정해둔다. 따라서 두 번째 집의 돈도 입력값대로 설정한다. 

2-2. 세 번째 집부터 반복문을 돌며 바로 전 집의 돈 vs 전전 집의 돈+현재 집의 돈을 비교하여 큰 값을 저장한다.

3-1. 마지막 집을 제외하고 첫 번째 집을 포함하는 경우 첫 번째 집의 돈은 입력값대로 설정한다. 그리고 두 번째 집은 첫 번째 집의 돈과 두 번째 집의 돈 중 큰 값으로 설정한다.(첫 번째 집의 돈이 큰 경우 첫 번째 집을 털고 두 번째 집은 털지 않는 것)

3-2. 2-2와 같은 로직으로 len(money)-1만큼만 반복문을 수행하여 마지막 집은 계산하지 않는다.

4. 첫 번째 집을 제외한 경우, 마지막 집을 제외한 경우 중 큰 값을 반환한다.

내 코드 - 파이썬

def solution(money):
    
    # 마지막 집 포함 -> 첫 번째 집 제외
    x1 = [0]*len(money)
    x1[0] = 0
    x1[1] = money[1]
    
    for i in range(2, len(money)):
        x1[i] = max(x1[i-1], x1[i-2]+money[i]) 
        
    # 첫 번째 집 포함 -> 마지막 집 제외
    x6 = [0]*(len(money)-1)
    x6[0] = money[0]
    x6[1] = max(money[0], money[1])
    
    for i in range(2, len(money)-1):
        x6[i] = max(x6[i-1], x6[i-2]+money[i]) 
    
    return max(x1[-1], x6[-1])

문제 설명

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

제한사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

입출력 예

내 문제풀이

1. 삼각형의 위에서 아래로 내려가면서, 바로 윗 level의 대각선 왼쪽/오른쪽 값 중 큰 값을 현재 위치 값에 더한다.

2. 현재 위치가 현재 level의 가장 왼쪽인 경우에는 바로 윗 level의 대각선 왼쪽이 없고, 현재 위치가 현재 level의 가장 오른쪽인 경우에는 바로 윗 level의 대각선 오른쪽이 없다. 따라서 이 경우에는 직접적으로 윗 level 값 하나를 넣어준다.(반복문의 if, elif 문)

3. 2번의 경우가 아닌 경우에는, 바로 윗 level의 대각선 왼쪽/오른쪽 값 중 큰 값을 더한다.

4. 결국 삼각형의 위에서 아래로 내려오며 계산된 값이 triangle의 가장 마지막 level에 모이게 되며, 따라서 triangle[-1] 중 가장 큰 값을 반환한다.

내 코드 - 파이썬

def solution(triangle):
    
    for i in range(1, len(triangle)):
        for j in range(0, i+1):
            if j == 0: //현재 위치가 현재 level의 가장 왼쪽인 경우
                triangle[i][j] += triangle[i-1][j]
            elif j == i: //현재 위치가 현재 level의 가장 오른쪽인 경우
                triangle[i][j] += triangle[i-1][j-1]
            else:
                triangle[i][j] += max(triangle[i-1][j-1], triangle[i-1][j])
                
    return max(triangle[-1])

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.
고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

내 문제풀이

1. 고속도로에서 나간 지점이 가장 빠른 순으로 routes를 정렬한다.

2. 첫 번째 카메라는 정렬한 routes의 가장 첫 번째 차량이 나간 지점에 설치한다. 따라서 설치 카메라 개수(answer)은 1로 초기화를 한다.

3. 두 번째 차량부터 확인하며 반복문을 돈다. 만약 차량이 들어온 시점이 카메라 설치 지점보다 늦다면, 단속카메라와 만날 수 없다. 따라서 해당 경우에 새로운 카메라를 차량이 나가는 시점에 설치해준다.

내 코드 - 파이썬

def solution(routes):
    answer = 1
    routes.sort(key=lambda x:x[1])
    cam = routes[0][1]
    for idx in range(1, len(routes)):
        if (routes[idx][0] > cam):
            cam = routes[idx][1]
            answer += 1        
    
    return answer

문제 설명

n개의 섬 사이에 다리를 건설하는 비용(costs)이 주어질 때, 최소의 비용으로 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 solution을 완성하세요.
다리를 여러 번 건너더라도, 도달할 수만 있으면 통행 가능하다고 봅니다. 예를 들어 A 섬과 B 섬 사이에 다리가 있고, B 섬과 C 섬 사이에 다리가 있으면 A 섬과 C 섬은 서로 통행 가능합니다.

제한사항

• 섬의 개수 n은 1 이상 100 이하입니다.
• costs의 길이는 ((n-1) * n) / 2이하입니다.
• 임의의 i에 대해, costs[i][0] 와 costs[i] [1]에는 다리가 연결되는 두 섬의 번호가 들어있고, costs[i] [2]에는 이 두 섬을 연결하는 다리를 건설할 때 드는 비용입니다.
• 같은 연결은 두 번 주어지지 않습니다. 또한 순서가 바뀌더라도 같은 연결로 봅니다. 즉 0과 1 사이를 연결하는 비용이 주어졌을 때, 1과 0의 비용이 주어지지 않습니다.
• 모든 섬 사이의 다리 건설 비용이 주어지지 않습니다. 이 경우, 두 섬 사이의 건설이 불가능한 것으로 봅니다.
• 연결할 수 없는 섬은 주어지지 않습니다.

입출력 예

내 문제풀이

1. costs를 다리 건설 비용 기준 내림차순 정렬을 한다. 그리고 다리가 연결되어 이어진 섬을 1로 표시하는 리스트(island)를 모두 0으로 초기화를 한다.

2. 섬이 모두 연결된 경우인, island의 합이 섬의 갯수일 때까지 반복문을 수행한다.

3. costs의 한 원소에 있는 첫 번째 섬을 A, 두 번째 섬을 B라고 할 때, A와 B가 모두 island에 표시가 되어 있는 경우 무시하고 다음 원소를 확인한다. 

4. 하지만 A와 B 중 하나만 island에 표시가 되어 있는 경우 모두 모든 섬의 통행 가능한 최소 비용(answer)에 해당 원소의 비용을 더하고 island에 섬 A, B를 표시한다.

5. 여기에서 costs 길이만큼 반복하지 않고 while문을 도는 이유, 섬 A, B 모두 island에 없는 경우는 제외한 이유는 각각이 연결된 동 떨어진 섬들이 생기는 것을 방지하기 위해서이다. 이렇게 하지 않는다면, 섬 1-2, 섬3-4-5 와 같이 각각 따로 연결되어 있는 상태에서 해당 함수가 끝나버리게 된다.

내 코드 - 파이썬

def solution(n, costs):
    answer = 0
    island=[0]*n 
    costs.sort(key=lambda x:x[2])
    island[costs[0][0]]=1
    new_island=[]
    
    while(1):
        if sum(island)==n:
            break
        for cost in costs:
            if island[cost[0]] and island[cost[1]]:
                continue            
            elif island[cost[0]] or island[cost[1]]:
                answer+=cost[2]
                island[cost[0]]=1
                island[cost[1]]=1
                break
            
    return answer

문제 설명

무인도에 갇힌 사람들을 구명보트를 이용하여 구출하려고 합니다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없고, 무게 제한도 있습니다.
예를 들어, 사람들의 몸무게가 [70kg, 50kg, 80kg, 50kg]이고 구명보트의 무게 제한이 100kg이라면 2번째 사람과 4번째 사람은 같이 탈 수 있지만 1번째 사람과 3번째 사람의 무게의 합은 150kg이므로 구명보트의 무게 제한을 초과하여 같이 탈 수 없습니다.
구명보트를 최대한 적게 사용하여 모든 사람을 구출하려고 합니다.
사람들의 몸무게를 담은 배열 people과 구명보트의 무게 제한 limit가 매개변수로 주어질 때, 모든 사람을 구출하기 위해 필요한 구명보트 개수의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 무인도에 갇힌 사람은 1명 이상 50,000명 이하입니다.
• 각 사람의 몸무게는 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 40kg 이상 240kg 이하입니다.
• 구명보트의 무게 제한은 항상 사람들의 몸무게 중 최댓값보다 크게 주어지므로 사람들을 구출할 수 없는 경우는 없습니다.

입출력 예

내 문제풀이

1. 몸무게 무거운 순, 가벼운 순으로 정렬한 두 개의 리스트를 생성한다.

2. 전체 사람의 수보다 구출된 사람의 수(live)가 더 작을 동안 반복문을 수행한다.

3. 가장 무거운 사람 + 가장 가벼운사람 이 구명보트의 무게 제한보다 작거나 같다면, 구출된 사람의 수를 +2하고, 구명보트 개수(answer), 몸무게 무거운 순 리스트(rev_people), 몸무게 가벼운 순 리스트(people)의 index 모두 +1 해준다.

4. 3번의 경우에 맞지 않다면, 가장 무거운 사람만 구출하며, 구출된 사람의 수, 구명보트 개수(answer), 몸무게 무거운 순 리스트(rev_people)의 index 모두 +1 해준다.

내 코드 - 파이썬

def solution(people, limit):
    answer = 0
    live = 0 # 구출된 사람 수
    
    rev_people = sorted(people, reverse=True) # 몸무게 무거운 순
    people.sort() # 몸무게 가벼운 순
    big = 0
    small = 0
    
    while(live < len(people)):
        if rev_people[big] + people[small] <= limit:
            live += 2
            answer, big, small = answer+1, big+1, small+1
        else :
            live, answer, big = live+1, answer+1, big+1
            
    return answer

문제 설명

어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다.
예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다.
문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요.

제한 조건

• number는 1자리 이상, 1,000,000자리 이하인 숫자입니다.
• k는 1 이상 number의 자릿수 미만인 자연수입니다.

입출력 예

내 문제풀이

1. 완성된 수를 넣을 리스트(new_list)에 number의 첫 원소 수를 넣는다.

2. number의 길이만큼 도는 반복문 내부에서 while문을 수행한다. k, new_list가 존재하고 new_list의 가장 마지막 원소가 number의 현재 원소 값보다 작은 경우에 수행한다. 이 경우에 new_list의 마지막 원소를 제거하고, k-1을 해준다. 

3. while문이 끝나면 number의 현재 원소 값을 new_list에 추가한다.

4. 내가 생각한 반환하는 경우의 수는 총 3가지이다. 

4-1. 만약 for문이 다 끝나기 전, k가 0이 되었을 때 현재 number 원소의 인덱스 값을 answer에 저장하고 반복문을 나온다.이 경우는 뺄 수 있는 만큼의 수를 이미 다 뺸 것이기 때문에 number에 남은 뒤의 숫자들을 new_list에 추가해주고 new_list를 반환한다.

4-2. 만약 위의 while문에서 계속 new_list의 가장 마지막 원소가 number의 현재 원소 값보다 큰 경우, while문이 실행되지 않고 new_list에 number의 원소만 append할 수 있다. 따라서 for문이 다 끝났지만 k가 0이 아닌 경우, new_list의 원소는 이미 가장 큰 수의 조건은 만족하고 있으므로 [:-k]의 인덱스 슬라이싱을 사용한다. 따라서 남은 k만큼의 뒷 부분 숫자를 잘라서 반환한다.

4-3. 위의 for문에서 k가 0이 되었지만 그 전에 for문이 끝난 경우, new_list가 깔끔하게 완성된 것이다. 따라서 그대로 new_list를 반환한다.

내 코드 - 파이썬

def solution(number, k):
    answer = 0
    new_list = [number[0]]
        
    for n in range(1, len(number)):
        if k == 0:
            answer = n
            break
        
        while k and new_list and new_list[-1] < number[n]:
            new_list.pop()
            k-=1
        new_list.append(number[n])
            
    # 위의 while문에서 new_list[-1]보다 작은 수만 들어와서 계속 append 하고 k가 남은 상황
    if k!=0:
        return ''.join(new_list[:-k])
    
    # 위의 for문을 다 돌고 나온 상황(k==0 조건문에 걸리기 전에) -> 깔끔하게 new_list 완성
    if answer == 0:
        return ''.join(new_list)
    
    # 위의 for문을 다 돌기 전 k==0에 걸린 상황
    new_list.append(number[answer::])     
    return ''.join(new_list)

문제 설명

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

내 문제풀이

1. 여벌 체육복을 가져온 학생이 체육복을 도난당한 경우, 해당 학생을 reserve, lost 리스트에서 모두 삭제한다. 또한 이를 고려한, 처음부터 본인의 체육복으로 수업을 들을 수 있는 학생 수를 계산한다.

2. 1번에서 새로 생성한 new_lost, new_reserve를 가지고 반복문을 수행한다. 체육복이 없는 학생을 보며, 먼저 바로 뒤 학생이 여벌 체육복을 가지고 있는지 확인하고 이후에는 바로 앞 학생이 여벌 체육복을 가지고 있는지 확인한다. 
이 경우에 수업에 참여할 수 있는 학생의 수(answer)+1을 하고, 여벌 체육복을 빌려 줄 수 있는 학생을 new_reserve에서 삭제한다.

내 코드 - 파이썬

def solution(n, lost, reserve):
  
    new_reserve = set(reserve)-set(lost)
    new_lost = set(lost)-set(reserve)
            
     # 초기 체육복 있는 학생
    answer = n-len(new_lost)
    
    for idx in new_lost:
        if idx+1 in new_reserve:
                answer+=1
                new_reserve.remove(idx+1)
        elif idx-1 in new_reserve:
            answer+=1
            new_reserve.remove(idx-1)
    
    return answer