게임맵 최단거리

프로그래머스 / 게임맵 최단거리 / Level 2

• 전형적인 BFS 2차원 배열 문제.
• BFS는 가까운 노드 (여기선 칸)부터 방문하므로, 시작점으로부터 모든 칸까지의 최소거리를 구할 수 있음.
  • 이때 시작 칸도 거리(이동한 칸 수)에 포함됨에 유의
• 시간 복잡도: $N$행 $M$열일 때, 모든 칸을 방문하면 $O(N \times M)$

from collections import deque
      
def solution(maps):      
    # maps: 1이면 열린 칸, 0이면 벽
    N = len(maps)                           # 행의 수
    M = len(maps[0])                        # 열의 수
    
    # 미방문 시 -1. 방문 시 distance.
    visited = [[-1] * M for _ in range(N)]
    visited[0][0] = 1                       # 시작 칸도 한 칸으로 침.
    queue = deque([(0, 0)])
    dx = [-1, 0, 1, 0]                      # 좌우 이동
    dy = [0, -1, 0, 1]                      # 상하 이동

    while queue:
        cx, cy = queue.popleft()

        # 상하좌우 탐색
        for i in range(4):
            nx, ny = cx + dx[i], cy + dy[i]

            # 맵 안의 칸인가? 벽이 없는가? 방문하지 않은 칸인가?
            if 0 <= nx < N and 0 <= ny < M and maps[nx][ny] == 1 and visited[nx][ny] == -1:
                queue.append((nx, ny))
                visited[nx][ny] = visited[cx][cy] + 1
                
    return visited[-1][-1]

체육복

프로그래머스 / 체육복 / Level 1

• 체육복을 잃어버린 학생들은 리스트 lost로
• 체육복을 빌려줄 수 있는 학생들은 집합 reserve_set으로 관리
  • $O(1)$ 연산을 위하여
• 단, 여벌체육복을 가져온 학생이 체육복을 잃어버렸을 수 있음
  • 이 경우 자기 체육복을 입을 순 있지만, 빌려줄 순 없음. 즉 reserved_set, lost 양쪽에 존재하면 안 됨에 유의할 것.
• lost를 순회하면서 앞사람이 체육복을 가져왔는지 확인. 없으면 뒷사람이 가져왔는지 확인.
• 시간 복잡도: lost의 길이가 $N$ reserve의 길이가 $M$일 때
  • reserve_set, lost를 계산하며 $O(N + M)$
  • lost를 순회하면서 $O(N)$

def solution(n, lost, reserve):
    fail = 0                                            # 체육복이 없는 사람 수
    
    # 여벌 체육복을 가져온 학생이, 체육복을 도난당했을 수 있음
    reserve_set = set(reserve) - set(lost)              # 체육복을 빌려 줄 수 있는 번호의 집합
    lost = list(set(lost) - set(reserve))               # 체육복이 없는 학생의 집합
    
    # lost를 순회 -> 체육복을 빌려줄 사람이 존재하나?
    for l in lost:
        # 앞사람에게 빌릴 수 있나
        if (l - 1) in reserve_set:
            reserve_set.remove(l - 1)
        # 뒷사람에게 빌릴 수 있나
        elif (l + 1) in reserve_set:
            reserve_set.remove(l + 1)
        else:
            fail += 1
    return n - fail

최빈값 구하기

프로그래머스 / 최빈값 구하기 / Level 0

• 풀이법이 다양할 것 같은데, 나는 Counter의 most_common 메서드 사용함.
  • Counter(리스트 등 이터러블)로, 이터러블의 각 원소의 빈도를 셈
  • 이후 .most_common(k)로 제일 많이 등장한 k개의 원소를, (원소값, 빈도수)]의 형태로 반환
  • e.g., k=2일 때, [1, 2, 3, 3, 3, 4] -> [(3, 3), (1, 1)]
  • e.g., k=2일 때, [1, 1, 2, 2] -> [(1, 2), (2, 2)]
  • e.g., k=2일 때, [1] -> [(1, 1)]
• 반환리스트를 num_counts로 둘 때, 아래 세 가지로 경우가 나뉨
  • 리스트 내 값의 종류가 1개뿐인 경우, new_counts[0][0]
  • 리스트 내 값의 종류가 2개인 경우, new_counts[0][1]과 new_counts[1][1]을 비교
    • 동일하면 최빈값이 2개이므로, -1 반환
    • 다른 경우 최빈값이 1개이므로, new_counts[0][0] 반환
• 시간 복잡도: array의 원소가 $N$개일 때, 카운터 만들면서 $O(N)$. .most_common에선 내부적으로 정렬이 이루어지므로, $O(N \log N)$. 최종 $O(N \log N)$
  

from collections import Counter

def solution(array):
    # 제일 빈도수가 높은 두 값을, (값, 빈도)로 구성된 리스트로 반환
    num_counts = Counter(array).most_common(2)
    
    # array가 숫자 1개로만 구성됐을 때 or 최빈값이 1개일 때
    if len(num_counts) == 1 or num_counts[0][1] != num_counts[1][1]:
        # 빈도수가 제일 높은 값 반환
        return num_counts[0][0]
    # 최빈값이 2개 이상일 때
    else:
        return -1