Enochkon's blog

문제

코드

def solution(tickets):
    tickets.sort(reverse=True)
    routes = {}
    
    for start,end in tickets:
        if start in routes:
            routes[start].append(end)
        else:
            routes[start] = [end]
    stack = ["ICN"]
    path = []
    
    while stack:
        top = stack[-1]
        if top in routes and routes[top]:
            stack.append(routes[top].pop())  
        else:
            path.append(stack.pop())  
    
    return path[::-1]  
    

풀이

• 주어진 비행기표를 다 사용한 후 여행경로를 출력해라

1. 알파벳 순서가 빠른것을 먼저 출력하라고 했기 때문에 tickets을 역순으로 정렬
2. 우선 routes라는 딕셔너리를 만들어 출발지는 key로 목적지는 value로 만들어준다.
3. stack 으로 사용할 배열에 제일 첫번째에 “ICN”을 넣어주고, while문을 돌린다.
4. while문을 돌리면서 갈 경로가 있으면 스택에 추가해주고, 아니면 stack에서 꺼내 path에 추가한다
5. 마지막 역순으로 되어있는 경로를 뒤집어서 출력해준다.

문제

코드

from collections import deque 

def solution(board):
    answer = 0
    board = [list(_) for _ in board]
    row, col = len(board), len(board[0])
    res = [[0 for i in range(len(board[0]))] for j in range(len(board))]
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    q = deque()
    
    def slide(i,j,dr,dc):
        while True:
            ci,cj = i + dr, j + dc
            if not (0 <= ci < row and 0 <= cj < col) or board[ci][cj] == 'D':
                return ci-dr, cj-dc
            i,j=ci,cj
                
    for i in range(row):
        for j in range(col):
            if board[i][j]== 'R':
                q.append((i,j,0))
    while q:
        cx, cy, dist = q.popleft()
        res[cx][cy]=dist
        if(board[cx][cy]=='G'):
            answer=dist
            break
        for dr , dc in d:
            nx,ny=slide(cx,cy,dr,dc)
            if(res[nx][ny]==0):
                res[nx][ny]=1
                q.append((nx,ny,dist+1))
    
    if(answer==0):
        return -1
    else:
        return answer

풀이

• 리코쳇 로봇 최소 경로 찾기

1. 문자열을 리스트화 시켜준다.
2. 시작지점 R 부터 목적지 G 지점까지 도달하는 경로를 찾는다.
   1. BFS를 사용한다.
   2. 한칸씩 이동시키는 것이 아닌 slide 함수를 사용해서 진행방향에 벽 혹은 끝까지 진행하는 좌표를 얻는다.
   3. 해당 좌표를 지나간적이 없으면 q에 추가해준다.
   4. 만약 현재 좌표가 ‘G’면 answer에 거리를 추가한다
3. 모든 탐색이 끝난 후 answer이 0인 경우에는 경로를 못찾은것이기 때문에 -1을 아니면 answer을 출력한다.

문제

코드

from collections import deque 

def solution(maps):
    maps = [list(_) for _ in maps]
    rows, cols = len(maps), len(maps[0])
    distance = [[-1 for _ in range(cols)] for _ in range(rows)]
    d = [(0, 1), (1, 0), (-1, 0), (0, -1)]
    q = deque()
    
    for i in range(rows):
        for j in range(cols):
            if maps[i][j] == 'L':
                q.append((i, j, 0))
                distance[i][j] = 0
    while q:
        cx, cy, dist = q.popleft()
        
        for dx, dy in d:
            nx, ny = cx + dx, cy + dy
            if 0 <= nx < rows and 0 <= ny < cols and maps[nx][ny] != 'X' and distance[nx][ny] == -1:
                distance[nx][ny] = dist + 1
                q.append((nx, ny, dist + 1))
                
    l_dist, e_dist = -1, -1
    for i in range(rows):
        for j in range(cols):
            if maps[i][j] == 'S' and l_dist == -1:
                l_dist = distance[i][j]
            if maps[i][j] == 'E':
                e_dist = distance[i][j]
    
    if l_dist == -1 or e_dist == -1:
        return -1
    else:
        return l_dist + e_dist

풀이

• 시작지점부터 레버까지, 그리고 레버부터 탈출지점까지의 거리를 구해라

1. 입력받은 문자열을 리스트형태로 변환
2. 거리를 입력할 배열 구현
3. 시작지점부터 바로 탈출지점까지 가는게 아닌 중간에 레버를 올려야하므로 레버를 기준으로 시작지점과 탈출지점의 최단거리를 구하면 된다고 생각
   1. bfs를 활용해 레버의 위치인 ‘L’부터 시작, 전체 미로의 거리를 L을 기준으로 기입
   2. 거리를 입력한 distance 배열에서 시작지점인 S와 탈출지점인 E의 좌표에 대한 거리의 합을 출력
   3. 만약 하나라도 -1인 경우 길이 없는것이므로 -1 출력

특이사항

• 출발 지점부터 레버까지와 레버부터 도착 지점까지의 길이 중복되도 된다길래 어떻게 구현해야할지 생각하다가, 두번의 bfs를 돌리면 되겠다고 생각했다. → 하지만 이렇게 구현할 경우 낭비가 심하다고 생각. → 중간 지점인 레버를 기준으로 거리를 구하면 bfs를 한번만 돌릴 수 있다고 생각 후 구현

문제

코드

from collections import deque

def solution(s):
    q = deque()
    for i in range(len(s)):
        if(len(q)==0 or s[i]!=q[len(q)-1]):
            q.append(s[i])
        elif(s[i]==q[len(q)-1]):
            q.pop()
    return 1 if len(q)==0 else 0

풀이

• 문자열에서 연속으로 오는 문자를 제거할 때 전부 제거할 수 있는지를 확인한다.
• 스택의 개념을 사용하면 손쉽게 풀 수 있음

1. 스택 역할을 해주기 위해 deque 선언
2. s문자열을 for문으로 돌면서 문자 제거
   1. q가 비어있거나 q의 마지막 문자와 현재의 문자가 다르면 q에 넣어준다.
   2. 만약 q의 마지막 문자와 현재 문자가 같으면 q를 pop해준다.
3. 마지막에 q가 비어있을 경우 1을 아닐경우 0을 출력한다.

문제

코드

from functools import cmp_to_key

def cmpFile(a,b):
    if a[0].upper() > b[0].upper():
        return 1
    elif a[0].upper() < b[0].upper():
        return -1
    else:
        if int(a[1]) > int(b[1]):
            return 1
        elif int(a[1]) < int(b[1]):
            return -1
    return 0

def solution(files):
    answer = []
    res=[]
    for i in files:
        head=0
        number=0
        for j in range(len(i)):
            if head==0 and '0'<=i[j]<='9':
                head=j
            if head!=0 and number==0 and ('0'>i[j] or i[j]>'9'):
                number=j
        if(number==0):
            number=len(i)
        answer.append([i[:head],i[head:number],i[number:]])
    answer.sort(key=cmp_to_key(cmpFile))
    
    for head,number,tail in answer:
        res.append(head+number+tail)
    return res

풀이

• 파일명을 특정 기준을 따라 정렬해라

1. head, number, tail 구역으로 나눈다.
2. 나눈 파일명을 기준에 따라 정렬하기 위해 cmpFile함수를 작성하고 cmp_to_key를 사용해서 비교함수로 사용한다
3. 정렬한 파일명을 다시 합쳐서 리턴한다.

특이사항

• 람다와 정규식을 사용해서 풀면 이정도로 줄일 수 있단다…

import re

def solution(files):
    a = sorted(files, key=lambda file : int(re.findall('\\d+', file)[0]))
    b = sorted(a, key=lambda file : re.split('\\d+', file.lower())[0])
    return b

• 이게 파이썬이지…

문제

코드

import sys
sys.setrecursionlimit(1000000)

def dfs(land, i, j, m, n, check, patch_id):
    if i < 0 or i >= m or j < 0 or j >= n or check[i][j] != 0 or land[i][j] == 0:
        return 0
    check[i][j] = patch_id 
    size = 1  
    
    size += dfs(land, i + 1, j, m, n, check, patch_id)
    size += dfs(land, i - 1, j, m, n, check, patch_id)
    size += dfs(land, i, j + 1, m, n, check, patch_id)
    size += dfs(land, i, j - 1, m, n, check, patch_id)

    return size

def solution(land):
    m = len(land)
    n = len(land[0])
    check = [[0] * n for _ in range(m)]

    patch_sizes = {}
    patch_id = 1

    for i in range(m):
        for j in range(n):
            if land[i][j] == 1 and check[i][j] == 0:
                patch_size = dfs(land, i, j, m, n, check, patch_id)
                patch_sizes[patch_id] = patch_size
                patch_id += 1

    max_oil = 0
    for j in range(n):
        oil_in_column = set()
        for i in range(m):
            if check[i][j] != 0:
                oil_in_column.add(check[i][j])

        total_oil = sum(patch_sizes[pid] for pid in oil_in_column)
        max_oil = max(max_oil, total_oil)

    return max_oil

풀이

• 일자로 팠을 때 석유를 최대한 많이 얻는 경우는?

1. 우선 땅에 있는 모든 석유 웅덩이를 dfs로 확인하여 1,2,3 라벨과 넓이를 붙여준다.
2. 그 뒤 땅을 한번씩 돌면서 일자로 팠을 때 시추 가능한 양을 체크하면서 최대로 시추 가능한 곳의 양을 max_oil에 저장하고 리턴한다.

특이사항

• 우선 정확성은 전부 통과했는데 효율성에러 런타임 에러가 나서 왜그런가 하고 생각해봤는데, 파이썬의 재귀 제한 때문에 오류가 나는것을 파악해서 재귀 허용을 늘려주면 통과한다. (기본 재귀 1000번)
• import sys sys.setrecursionlimit(1000000)
• 원래는 매 시행때 dfs를 돌면서 계속 체크를 하려고 했다가 그렇게 되면 효율성을 통과하지 못할거라고 생각하고 미리 dfs로 모든 석유의 라벨링을 해주며 진행했다.

문제

코드

def solution(dirs):
    answer = 0
    num = {'U':(0,1),'D':(0,-1),'R':(1,0),'L':(-1,0)}
    res={}
    visited = set()
    x, y = 0, 0

    for i in dirs:
        nx, ny = x + num[i][0], y + num[i][1]
        if -5 <= nx <= 5 and -5 <= ny <= 5:
            if ((x, y), (nx, ny)) not in visited:
                answer += 1
                visited.add(((x, y), (nx, ny)))
                visited.add(((nx, ny), (x, y)))
            x, y = nx, ny

    return answer

풀이

• 중복을 제외하고 방문한 선분을 체크하기

1. 입력받는 문자열에 따라 이동하는 좌표값 딕셔너리를 구현.
2. 입력에 따라서 x,y를 움직인다. -5 ~ 5의 범위는 넘어가면 continue 해준다,
3. set()에 이동좌표를 넣어서 만약 그 좌표가 존재하지 않으면 answer+=1해주고, 존재하면 중복한 값이라고 판단하고 넘어간다.

문제

코드

def changeStrToInt(time):
        return int(time[0:2]) * 60 + int(time[3:])

def solution(book_time):
        sort_time = sorted([[changeStrToInt(i[0]), changeStrToInt(i[1]) + 10] for i in book_time])

    res = []

    for i in sort_time:
        if len(res)==0:
            res.append(i)
            continue
        for j in range(len(res)):
            if(i[0] >= res[j][1]):
                res[j] = res[j]+i
                break
        else:
            res.append(i)

    return len(res)

풀이

• 빈틈없이 예약해서 최소의 방 개수를 구하자

1. 문자열로 입력받은 시간을 분으로 그리고 int형으로 만들어주는 함수를 작성한다.
2. 그 다음 변환한 시간을 바탕으로 정렬해준다
3. 정렬한 시간을 바탕으로 res배열에 넣어준
   1. res배열이 비어 있으면 바로 넣어준다.
   2. res배열을 돌면서 각각의 res배열의 제일 마지막 시간이 현재 첫번째 시간보다 작으면 거기 넣어준다.
   3. 넣을 곳이 없으면 배열에 새롭게 추가한다.
4. 방의 개수를 리턴해준다.