[TIL Day6] 코딩테스트 더 풀어보기 (2)

🟢 푼 문제
🟡 접근 방법을 알았지만 못 푼 문제
🔴 접근 방법도 모르고 못 푼 문제

Lv2.

1. 문자열 압축 🟡

  • 문제 해결 방법
    - 결국 완전 탐색이었다.
    • 문자열 슬라이싱은 문자의 길이를 넘어가도 오류 없이 작동한다는 것.
def solution(s):
    answer = len(s)
    
    # 1부터 문자열s의 절반 길이까지 압축 단위를 늘려가며 확인한다
    for size in range(1, len(s) // 2 + 1):
        count = 1
        # 압축했을 때 문자열의 길이 저장
        compress = 0
        
        prev = s[:size]
        for i in range(size, len(s) + size, size):
            curr = s[i:i + size]
            # 이전 단위 문자열 prev와 현재 단위 문자열 curr이 같으면
            if prev == curr:
                count += 1
            # 다르면
            else:
                # count가 2이상인 경우와 1인 경우 구분
                compress += size + len(str(count)) if 1 < count else len(prev)
                prev = curr
                # count 초기화
                count = 1
                
        answer = min(answer, compress)
        
    return answer

Lv3.

1. 배달 🔴

  • BFS 풀이
    - 정확도가 50점이 나왔다.
    • 다른 도시를 거쳐가는 것이 바로 가는 도로보다 비용이 더 싼 경우가 있을 수 있다.
from collections import deque

def solution(N, road, K):
    graph = [[0] * (N + 1) for _ in range(N + 1)]
    for r in road:
        # 출발지와 도착지가 같은 도로가 또 있는 경우 더 비용이 작은 것만 기록
        if graph[r[0]][r[1]] != 0:
            graph[r[0]][r[1]] = min(graph[r[0]][r[1]], r[2])
        else:
            graph[r[0]][r[1]] = r[2]
        # 반대 방향도 기록
        graph[r[1]][r[0]] = graph[r[0]][r[1]]
        
    # print(graph)
    distance = [-1] * (N + 1)
    distance[1] = 0 
    
    # BFS
    q = deque([1])
    while q:
        now = q.popleft()
        for next_node in range(1, N + 1):
            # 도로가 있고 아직 방문하지 않은 도시라면
            if graph[now][next_node] != 0 and distance[next_node] == -1:
                # 최단 거리 갱신
                distance[next_node] = distance[now] + graph[now][next_node]
                q.append(next_node)
    
    # print(distance)
    return len([x for x in distance[1:] if x <= K])

다익스트라 알고리즘

그래프에서 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘으로, 음의 간선이 없을 때 사용할 수 있다.

  • 알고리즘의 작동 과정
    1. 출발 노드를 설정한다.

    1. 최단 거리 테이블을 초기화한다.
    2. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
    3. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단거리 테이블을 갱신한다.
    4. 위 과정에서 3과 4번을 반복한다.
  • 알고리즘의 특징
    - '각 노드에 대한 현재까지의 최단 거리' 정보를 항상 1차원 리스트(최단 거리 테이블)에 저장하여 리스트를 계속 갱신한다.

    • 매번 '가장 비용이 적은 노드'를 선택해서 임의의 과정(4번)을 반복하므로 그리디 알고리즘으로 분류된다.
import heapq
INF = int(1e9)

def solution(N, road, K):
    graph = [[] for i in range(N + 1)]
    # 최단 거리 테이블을 모두 무한으로 초기화
    distance = [INF] * (N + 1)
    
    # 양방향 도로임에 주의
    for r in road:
        graph[r[0]].append((r[1], r[2]))
        graph[r[1]].append((r[0], r[2]))
        
    # 다익스트라 알고리즘
    def dijkstra(start):
        q = []
        # 최소 힙으로 cost가 낮은 순서로 정렬되게 함
        heapq.heappush(q, (0, start))
        # 시작 노드까지의 비용은 0으로 초기화
        distance[start] = 0
        while q:
            dist, now = heapq.heappop(q)
            # 이미 처리된 노드인지 확인
            if distance[now] < dist:
                continue
            # 현재 노드를 거쳐 다른 노드로 가는 최단 거리를 계산한다
            for i in graph[now]:
            	# 비용 = 현재 노드까지의 거리 + 현재 노드에서 다음 노드까지 거리
                cost = dist + i[1]
                # 저장된 값보다 작으면 최솟값 갱신
                if cost < distance[i[0]]:
                    distance[i[0]] = cost
                    heapq.heappush(q, (cost, i[0]))
                    
    dijkstra(1)
    
    return len([x for x in distance if x <= K])

2. FloodFill 🔴

  • 문제 해결 방법
    - BFS 알고리즘을 사용한다.
    • 이미지를 탐색하면서 방문한 칸을 visited에 체크하고 큐에 넣는다.
    • 큐의 원소를 모두 pop하면 영역 count를 증가시킨다.
from collections import deque

def solution(n, m, image):
    # 영역 count
    cnt = 0
    # 방문 여부 체크
    visited = [[False] * m for _ in range(n)]
    # 이동 방향
    directions = [[0, -1], [0, 1], [-1, 0], [1, 0]]
    
    for i in range(n):
        for j in range(m):
            # 방문하지 않은 칸에 대해서
            if not visited[i][j]:
                q = deque()
                # 큐에 해당 칸 삽입
                q.append([i, j])
                # 방문 체크
                visited[i][j] = True
                # 칸 색상 체크
                color = image[i][j]
                # 큐가 빌 때까지
                while q:
                    x, y = q.popleft()
                    # 인접한 네 칸에 대해 검사
                    for dx, dy in directions:
                        nx, ny = x + dx, y + dy
                        # 새로 움직인 좌표가 image 안에 있는지 확인
                        if 0 <= nx < n and 0 <= ny < m:
                            # 아직 방문하지 않았고
                            if not visited[nx][ny]:
                                # 색깔이 같은 칸이라면
                                if image[nx][ny] == color:
                                    # 방문 처리한 뒤 큐에 삽입 
                                    visited[nx][ny] = True
                                    q.append([nx, ny])
                cnt += 1
    
    return cnt

3. 방문 길이 🟢

  • 문제 해결 방법
    - 지나온 경로를 따로 저장해둔다.
def solution(dirs):
    direction = {'U':(-1, 0), 'D':(1, 0), 'R':(0, 1), 'L':(0, -1)}
    x, y = 5, 5
    # 지나온 경로 저장
    # ((x, y), (nx, ny))
    road = []
    answer = 0
    for i, d in enumerate(dirs):
        nx = x + direction[d][0]
        ny = y + direction[d][1]
        if nx < 0 or nx > 10 or ny < 0 or ny > 10:
            continue
        # 지나온 경로가 아니라면 길의 길이 업데이트
        if [(x, y), (nx, ny)] not in road and [(nx, ny), (x, y)] not in road:
            answer += 1
            road.append([(x, y), (nx, ny)])
        x, y = nx, ny
        
    return answer

4. 게임아이템 🟡

  • 문제 해결 방법
    - heapq를 사용해 캐릭터별로 사용할 수 있는 아이템 중 공격력을 최대로 높이는 아이템을 선택한다.
    • 선택된 아이템을 삭제할 때는 deque의 popleft를 이용한다.
    • 최소 힙인 heapq를 최대 힙처럼 사용하고자 할 때에는 원소의 부호를 (음수로) 바꾸자.
from heapq import heapify, heappush, heappop
from collections import deque


def solution(healths, items):
    # 체력을 오름차순 정렬
    healths.sort() 
    # 아이템이 소모하는 체력을 오름차순으로 정렬
    items = sorted([(item[1], item[0], index + 1) for index, item in enumerate(items)])
    items = deque(items)
    answer = []
    heap = []
    
    for health in healths: # 제일 작은 체력을 가진 캐릭터부터 
        while items:
            # 가장 깎는 체력이 낮은 아이템을 쓸 수 있는지
            # 낮추는 체력, 높여줄 공격치, 아이템 번호
            debuff, buff, index = items[0]
            if health - debuff < 100: # 체력이 100보다 적게 남게 되는 경우 루프 종료
                break
            items.popleft() # 아이템 목록에서 삭제
            heappush(heap, (-buff, index)) # 공격치의 부호를 바꾸어 최대 힙을 구현함
        if heap: # 힙이 비어있지 않으면
            # 쓸 수 있는 아이템 중 공격치를 최대로 높이는 아이템 사용
            _, index = heappop(heap)
            answer.append(index)
            
    return sorted(answer)

5. 빙고 🔴

  • 문제 해결 방법
    - nums가 n x n 보드판에 있는지 매번 확인하려면 O(n^2 * nums)의 시간복잡도가 소요된다.
    • nums를 hash로 만들어서 O(1)로 체크하자.
def solution(board, nums):
    n = len(board) 
    # nums 리스트의 값을 키로 변환하여 dict로 만들어준다
    nums = dict.fromkeys(nums, True)
    row_list = [0] * n # 행 방향으로 지운 숫자의 개수를 센다
    col_list = [0] * n # 열 방향으로 지운 숫자의 개수를 센다
    left_diagonal = 0 # 왼쪽 대각선
    right_diagonal = 0 # 오른쪽 대각선
    
    for i in range(n): # O(n)
        for j in range(n): # O(n)
            if board[i][j] in nums: # O(1)
                board[i][j] = 0
                row_list[i] += 1
                col_list[j] += 1
                
                if i == j:
                    left_diagonal += 1
                if n - 1 - i == j:
                    right_diagonal += 1
                    
    answer = 0
    answer += sum([1 for i in row_list if i == n])
    answer += sum([1 for j in col_list if j == n])
    answer += 1 if left_diagonal == n else 0
    answer += 1 if right_diagonal == n else 0
    
    return answer

6. N-Queen 🔴

  • 문제 해결 방법: DFS로 풀자.(정석)
    - 경우의 수를 모두 찾으면서 가능하지 않은 것은 가지치기 <- 이것이 백트래킹이다.
    - 2차원 보드판이라고 해서 무조건 2차원 배열을 사용하려고 하지 말자.
    • 1차원 row 리스트에 col 값을 저장해서 쓸 수 있다.
# 해당 위치에 퀸을 둘 수 있는지 체크
def check(queen, row):
    for i in range(row):
        # i행의 값과 row행의 값이 같다면 퀸을 둘 수 없음
        # 왼쪽, 오른쪽 대각선으로 인접한지도 확인 
        if queen[i] == queen[row] or abs(queen[i] - queen[row]) == row - i:
            return False
    return True


# 맨 위 행부터 열을 이동하면서 체크, 퀸을 뒀으면 다음 행으로 이동
def search(queen, row):
    # stack = 1
    n = len(queen)
    count = 0
    
    # 끝에 도달한 경우 1을 리턴
    if n == row:
        return 1

    for col in range(n):
        queen[row] = col # row, col 영역에 퀸을 둔다
        if check(queen, row): # 둘 수 있는지 체크한다
            # 가능하다면 다음 행으로 이동한다
            count += search(queen, row + 1)
            
    return count


def solution(n):

    return search([0] * n, 0)

7. N으로 표현 🟡

  • 문제 해결 방법
    - 다이나믹 프로그래밍으로 재귀적 방식으로 접근하자.
    - 강의에서 푼 문제였지만 풀이법이 곧장 떠오르지 않았다.
    - 숫자 x를 n번 사용해서 만들 수 있는 경우의 수는, 1번 사용한 숫자들과 n-1번 사용한 숫자들을 연산한 결과 + 2번 사용한 숫자들과 n-2번 사용한 숫자들을 연산한 결과 + ... + n-1번 사용한 숫자들과 1번 사용한 숫자들을 연산한 결과
def solution(N, number):
    # i번 사용해서 만들 수 있는 수들의 집합을 원소로 갖는다
    s = [set() for x in range(8)]
    # 5, 55, 555 ... 를 각 set에 먼저 채워주자
    # enumerate에 start=1 주의하자
    for i, x in enumerate(s, start=1):
        x.add(int(str(N) * i))
        # 이 때 이미 정답이 있는 경우가 있다
        if number in s[i - 1]:
            return i
        
    for i in range(1, len(s)):
        for j in range(i):
            # j번 사용해서 만든 수 중 피연산자 op1을 가져온다
            for op1 in s[j]:
                # i - j - 1번 사용해서 만든 수 중 피연산자 op2를 가져온다
                for op2 in s[i - j - 1]:
                    s[i].add(op1 + op2)
                    s[i].add(op1 - op2)
                    s[i].add(op1 * op2)
                    if op2 != 0:
                        s[i].add(op1 // op2)
        if number in s[i]:
            answer = i + 1
            break 
    else:
        answer = -1
        
    return answer

8. 2 x n 타일링 🟢

  • 문제 해결 방법
    - 점화식 f(x) = f(x - 1) + f(x - 2)임을 이용하여(피보나치 수열)
    - 보텀업 방식으로 가로 길이가 n일 때까지 경우의 수를 구하자.
def solution(n):
    fibo = [1, 2, 3]
    
    for i in range(3, n):
        fibo.append((fibo[i - 2] + fibo[i - 1]) % 1000000007)
        
    return fibo[n - 1]

9. 등굣길 🔴

  • 문제 해결 방법
    - 격자모양의 맵에서 목표 칸까지 가는 모든 경우의 수를 더해가며 저장한다.
    - 웅덩이가 있는 곳은 갈 수 없으므로, 이후 칸에 영향을 주지 않기 위해 0으로 바꿔 처리한다.
def solution(m, n, puddles):
    maps = [[0] * (m + 1) for _ in range(n + 1)]
    # 1, 1 좌표의 경우의 수는 1이다
    maps[1][1] = 1
    
    # 웅덩이 좌표는 -1로 표시
    for x, y in puddles:
        maps[y][x] = -1
    
    for y in range(1, n + 1):
        for x in range(1, m + 1):
            # 웅덩이인 경우 이후 합에 영향이 가지 않도록 0으로 바꾼다
            if maps[y][x] == -1:
                maps[y][x] = 0
                continue
            
            # 왼쪽과 위의 경우의 수를 합해여 해당 칸으로 오는 모든 경로를 구한다
            maps[y][x] += (maps[y - 1][x] + maps[y][x - 1]) % 1000000007
                
    # n, m 좌표의 경우의 수를 반환
    return maps[n][m]

10. 가장 긴 팰린드롬 🟢

  • 제한 시간이 넉넉할 때
    - 앞에서부터 단위를 늘려가며 모든 경우의 수를 확인
def solution(s):
    answer = 1
    for num in range(2, len(s) + 1):
        for start in range(0, len(s) - num + 1):
            temp = s[start:start + num]
            if temp == temp[::-1]:
                answer = max(answer, num)
    return answer
  • 정말 빠른 알고리즘으로 푸는 방법
    -

좋은 웹페이지 즐겨찾기