99클럽 코테스터디 16일차 TIL - 프로그래머스 신규 아이디 추천, JadenCase 문자열 만들기, 경주로 건설

1. 문제:https://school.programmers.co.kr/learn/courses/30/lessons/72410 

✅ 풀이

def solution(new_id):
    # 1단계
    answer = new_id.lower()
    # 2단계
    temp = ""
    for c in answer:
        if c.islower() or c.isdigit() or c in ["-", "_", "."]:
            temp += c
    answer = temp
    # 3단계
    while ".." in answer:
        answer = answer.replace("..", ".")
    # 4단계
    answer = answer.strip(".")
    # 5단계
    if len(answer) == 0: # 길이 0은 not answer로 치환 가능
        answer = "a"
    # 6단계
    if len(answer) >= 16:
        answer = answer[:15]     # 길이가 16이상이면 첫 15자로 자르기
    answer = answer.rstrip(".")
    # 7단계
    if len(answer) <= 2:
        last = answer[-1]
        while len(answer) < 3:   # 길이가 3 이상이 될때까지 마지막 문자 이어붙이기
            answer += last
    return answer

 

2. 문제: https://school.programmers.co.kr/learn/courses/30/lessons/12951

이 문제에서 막혔던 부분은 "공백 문자가 연속해서 나올 수 있습니다." 이다.

조건에 의하면, "3people unFollowed me" 가 예시로 들어오면 정답은 "3people Unfollowed Me" 이다.

그리고 "   hello   world"가 예시로 들어오면 정답은 "   Hello  World"이다. 즉 연속되는 공백을 그대로 살려야 한다는 것

 

관련해서 split() 과 split(' ')의 차이점에 대해서 알아보았다.

- split(): 공백 문자의 갯수와 상관 없이, 공백 문자를 제외하고 분리하여 반환한다.

- split(''): 공백 문자의 갯수다로, 공백 문자를 포함하여 문자열 분리 후 반환한다.

s = "ABC DEFG  HIJK   LMNOP"
print(s.split())
print(s.split(''))

['ABC', 'DEFG', 'HIJK', 'LMNOP']
['ABC', '', 'DEFG', '', '', 'HIJK', '', '', '', 'LMNOP']

 

따라서 이 문제는 연속된 공백이 포함될 수 있고, 해당 공백을 문자열에 포함시켜야 하므로 s.split('')으로 나눠야한다.

 

✅ 풀이

def solution(s):
    answer = []
    arr = s.split(' ')
    for c in arr:
        if c:
            answer.append(c.capitalize())
            # 첫문자가 대문자이고, 나머지는 소문자로 만들어주는 함수: capitalize
            # 첫 문자가 알파벳이 아닌 경우 무시하므로 첫문자가 숫자인 예외 케이스도 포함
        else:
            answer.append('')   # 공백 문자의 갯수대로 리스트에 공백 문자 포함하여
    return " ".join(answer)    # 공백 문자의 갯수대로 공백을 포함하면서 다른 문자열도 공백 포함하여 출력

 

3. 문제: https://school.programmers.co.kr/learn/courses/30/lessons/67259

해당 문제는 첫번째로 "다익스트라 알고리즘"으로 접근했다. 문제에서 다음과 같은 근거로 판단했다.

1) "그래프", "(0,0) 부터 출발하여 (N-1, N-1)까지 도달했을 때의 경주로 건설 최소 비용" --> BFS 혹은 다익스트라

2) 직선도로는 100, 코너는 500원인 조건을 "양의 가중치"로 가정 --> 다익스트라

 

그러나 여기서 막힌점이 있었는데,

- 같은 방향으로 연결된 도로와 코너로 만나는 도로가 각각 비용이 다른데, 이를 어떻게 판단할 수 있는가?

에 대한 아이디어가 떠오르지 않아서 아래와 같이 코드를 짜다가 막혔다.

 

import heapq

def solution(board):
    n = len(board)
    INF = int(1e9)
    dx = [-1, 1, 0, 0]   # 상하 좌우로 이동하는 데 도움을 줄 방향 배열
    dy = [0, 0, -1, 1]
    
    # 각각 x, y 좌표까지 이동하는 데 드는 최소 비용을 저장할 2차원 배열
    distance = [[INF] * n for _ in range(n)]
    distance[0][0] = 0    # 처음에는 비용을 0으로 초기화
    
    heap = []
    heapq.heappush(heap, (0, 0, 0))  # 비용, x, y
    # 처음에는 (0, 0)에서 시작하고 비용이 0이므로 (0, 0, 0) 추가

    while heap:
        cost, x, y = heapq.heappop(heap)

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 0: # 이동할 수 있는 범위라면
                next_cost = # 여기서 어떻게 계산?
                if distance[nx][ny] > next_cost:   # 방문한 적이 없거나 이전보다 더 최소 비용이 존재하는 경우
                    distance[nx][ny]= next_cost
                    heapq.heappush(heap, (next_cost, nx, ny))

    return distance[n - 1][n - 1]

 

그래서 다른 사람들의 풀이를 보면서 종합해보니, dx와 dy 배열을 순서대로 상 좌 하 우, 즉

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]

 

로 설정한다고 했을 때

이전 도로를 세운 방향 인덱스를 현재 도로를 세우려는 방향 인덱스를 뺀 값에서 2로 나누면 나머지가 0이라는 조건을 세울 수 있다.

 

즉,

방향이 상 (인덱스 0)= 하 (인덱스 2) 이니 (0-2)% 2 == 0, (2-0) % 2 == 0 이며 (참고로 python에서는 a % b에서 b가 양수이기만 하면 a가 음수여도 양수로 치환하여 나머지를 반환해준다)

방향이 좌 (인덱스 1) = 우 (인덱스 3) 이니 (1-3) % 2 == 0, (3-1) % 2 == 0 라는 조건이 성립하므로

이 식을 통해 방향이 같은지 다른지를 판단할 수 있다는 점을 알 수 있다.

 

그리고 도로를 세울 때 이전 방향을 알아야만 비용이 100원인지 600원 (100 + 500) 인지 판단 가능하니,

distance 배열은 좌표와 비용 말고도 이전 방향에 대한 정보도 같이 들고 있어야하는 것으로 3차원 배열로 설계한다.

방향은 차례대로 상 좌 하 우 를 인덱스 0, 1, 2, 3으로 치환한다.

 

따라서 이를 고려하여 코드를 수정하면 다음과 같다.

 

✅ 다익스트라 문제풀이

import heapq

def solution(board):
    n = len(board)
    INF = int(1e9)
    # 방향: 차례대로 상 좌 하 우
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]
    
    # 3차원 거리 배열: [x][y][dir] --> dir은 방향을 의미한다.
    distance = [[[INF] * 4 for _ in range(n)] for _ in range(n)]
    
    # 초기 위치 (0, 0) 에 대해 모든 방향의 비용을 0으로 초기화한다.
    for i in range(4):
        distance[0][0][i] = 0
    
    heap = []
    heapq.heappush(heap, (0, -1, 0, 0))  # 비용, 이전방향, x, y
    # 초기에는 방향이 정해져있지않으므로 이를 -1로 설정한다.

    def calculate_cost(direction, prev_direction, cost):
        if prev_direction == -1 or (prev_direction - direction) %2 == 0:  
        # 초기이거나 방향이 같은 직선 도로일 경우
            return cost + 100
        else:
            return cost + 600

    while heap:
        cost, direction, x, y = heapq.heappop(heap)

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 0:  # 유효한 범위 내에 있고, 도로를 세울 수 있는 영역이라면
                next_cost = calculate_cost(i, direction, cost)
                if distance[nx][ny][i] > next_cost:    # 처음 방문했거나 이전 계산한 최소 비용보다 지금 계산한 최소 비용이 더 적다면, 해당 값으로 치환한다.
                    distance[nx][ny][i] = next_cost
                    heapq.heappush(heap, (next_cost, i, nx, ny))   # 지금 계산한 최소 비용을 힙에 추가

    return min(distance[n - 1][n - 1])  # 도착점에 상, 하, 좌, 우 별로 각 최소 비용이 포함되어있으니 이중에서 한번 더 최소값을 선택해야하므로 min을 통해 최소값을 반환한다.

 

그리고 다른 사람들의 풀이를 보니 BFS로도 많이 푸는 것 같다.

(0, 0)에서 (N-1, N-1) 까지 탐색하면서 최소 비용을 계산한다는 점에서 BFS를 떠올릴 수 있다. 

 

✅ BFS 문제풀이

from collections import deque

def solution(board):
    n = len(board)
    INF = 1e9
    
    # 방향: 상(0), 좌(1), 하(2), 우(3)
    dx = [-1, 0, 1, 0]
    dy = [0, -1, 0, 1]

    # 3차원 거리 배열: [x][y][dir]
    distance = [[[INF] * 4 for _ in range(n)] for _ in range(n)]

    # 초기 위치에서 네 방향 모두 시작 가능하므로 모든 후보지에 대한 distance 배열 초기화 및 큐에 추가한다.
    q = deque([])
    for i in range(4):
        distance[0][0][i] = 0
        q.append((0, 0, i))  # x, y, 방향

    def calculate_cost(direction, prev_direction, cost):
        if (prev_direction - direction) % 2 == 0:  # 같은 방향 --> 100
            return cost + 100
        else:
            return cost + 600       # 다른 방향: 코너이므로 500 + 100 = 600

    while q:
        x, y, direction = q.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == 0:  # 유효한 범위에 있고, 도로를 세울 수 있는 영역일 경우
                next_cost = calculate_cost(i, direction, distance[x][y][direction])
                if distance[nx][ny][i] > next_cost:  # 아직 방문하지 않았거나 지금 계산한 비용이 기존 최소 비용보다 더 작다면,
                    distance[nx][ny][i] = next_cost   # distance 배열 갱신 후
                    q.append((nx, ny, i))   # 새로운 후보지를 큐에 추가한다.

    return min(distance[n - 1][n - 1])

 

오늘의 배운점

- split()은 공백 포함 X, 연속된 공백을 하나의 공백으로 간주 / split('')은 공백 포함 O, 연속된 공백을 여러개의 공백으로 간주

- strip()은 양쪽에서 구분자 제거, rstrip / lstrip은 각각 오른쪽, 왼쪽에서 구분자 제거

- 그래프 탐색 문제에서, 좌표 말고 다른 들고 다니면서 판단해야할 정보가 있는지를 고려하여 배열을 설계하자.

- 특정 좌표 혹은 노드에서 특정 좌표, 노드까지 이동하면서 가중치가 양수이고, 최소 비용을 계산할 경우 BFS와 다익스트라 모두 활용 가능하다.