Jinho Tech

스택을 사용하면 쉽게 풀 수 있는 간단한 구현 문제이다.

뭔가를 차곡차곡 쌓고 마지막에 쌓은 것부터 처리해야 되는 식의 문제 -> 스택을 생각하자

풀이

1. 인형을 뽑을 때마다 인형을 스택에 추가

2. 스택의 길이가 2 이상일 때 맨 뒤에 있는 인형 2개가 같으면 제거해야 하므로 stack pop 2번 후 ans += 2를 해준다. 

def solution(board, moves):
    ans = 0
    stack = []
    for m in moves:
        for i in range(len(board)):       
            if board[i][m-1]:
                stack.append(board[i][m-1])
                board[i][m-1] = 0

                if len(stack) > 1:
                    if stack[-1] == stack[-2]:
                        stack.pop(); stack.pop()
                        ans += 2
                break
                
    return ans

풀이

파이썬 내장함수 replace를 사용하면 아주 쉽게 풀 수 있다.  

def solution(s):
    li = ['zero', 'one', 'two', 'three', 'four', 'five', 'six', 'seven', 'eight', 'nine']
    for i in range(10):
        s = s.replace(li[i], str(i))
    
    return int(s)

전에는 알고리즘 문제를 설렁설렁 어떻게든 풀기만 하는 느낌으로 넘어갔었는데, 이번에는 다시 공부한다는 생각으로

프로그래머스 문제들을 풀어보려고 한다.

클린코드도 복습하는 겸 나름 최대한 보기 좋게 짜보려고 한다.

풀이)

1. 거리를 구하기 위해서 우선 1: [0,0], 2:[0, 1] ... 9:[2, 2], 0:[3, 1]과 같이 숫자를 좌표로 변환해준다.

 2. 숫자와 왼손, 오른손과의 거리를 구한다.

3. 그 이후는 각 상황에 맞게 ans에 'L', 'R'을 더하고 왼손과 오른손의 위치를 업데이트해주면 된다.

1, 4, 7 -> 왼손, 3, 6, 9 -> 오른손, 2, 5, 8, 0 -> 왼손과 오른손 중 가까운 손

def get_idx(n):
    n = 10 if n == 0 else n-1
    
    return [n//3, n%3]

def get_distance(n1, n2):
    d1, d2 = get_idx(n1), get_idx(n2)
    d = abs(d1[0] - d2[0]) + abs(d1[1] - d2[1])

    return d
    
def get_nexthand(left, right, num, hand):
    if num in [1, 4, 7]:
        return 'left'
    elif num in [3, 6, 9]:
        return 'right'
    else:
        dl = get_distance(left, num)
        dr = get_distance(right, num)
        if dl < dr:
            return 'left'
        elif dl > dr:
            return 'right'
        elif dl == dr:
            return hand
    
def solution(numbers, hand):    
    left, right = 10, 12
    ans = ''
    
    for num in numbers:
        nexthand = get_nexthand(left, right, num, hand)
        if nexthand == "left":
            left = num
            ans += 'L'
        else:
            right = num
            ans += 'R'
    
    return ans

처음에는 아래와 같이 첫날부터 확인하는 방식으로 풀었다. 

N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
dp = [0 for _ in range(N+1)]

for i in range(N):
    for j in range(i + li[i][0], N+1):
        if dp[j] < dp[i] + li[i][1]:
            dp[j] = dp[i] + li[i][1]

print(dp[-1])

통과되긴 해도 일단 반복문이 2개라 아래 사진과 같이 무의미한 동작이 상당히 많다.

반복문 하나로 끝낼 방법이 없을까 하다가 그냥 마지막 날부터 확인하면 되겠다는 생각이 들어 아래와 같이 수정했다.

N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
dp = [0 for _ in range(N+1)]

for i in range(N-1, -1, -1):
    if i + li[i][0] > N:
        dp[i] = dp[i+1]
    else:
        dp[i] = max(dp[i+1], li[i][1] + dp[i + li[i][0]])
    
print(dp[0])

간단한 BFS 문제이다.

S에서 G로 가는 최단경로의 길이를 출력해주면 된다. 경로가 없다면 No Exit 출력

from collections import deque

def bfs(i, j):
    d = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    q = deque()
    q.append((i, j))
    check[i][j] = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < R) and (0 <= X < C) and graph[Y][X] != 'X' and check[Y][X] == -1:
                check[Y][X] = check[y][x] + 1
                if graph[Y][X] == 'G':
                    return check[Y][X]
                q.append((Y, X))
    return None

for _ in range(int(input())):
    R, C = map(int, input().split())
    graph = [input() for a in range(R)]
    check = [[-1]*C for b in range(R)]
    
    for i in range(R):
        for j in range(C):
            if graph[i][j] == 'S':
                ans = bfs(i, j)
                print(f"Shortest Path: {ans}" if ans else "No Exit")

pythonanywhere 사이트에서 flask로 만든 사이트를 쉽게 배포할 수 있다.

1 https://www.pythonanywhere.com에 접속하여 회원가입 후 로그인

2 소스파일을 압축한 다음 아래 그림과 같이 업로드하고, Open Bash console here를 클릭

3 압축 해제 -> 가상 환경 생성 -> 가상 환경에 필요한 라이브러리를 설치

4 Web으로 넘어가 Add a new web app -> Next -> Manual configuration -> Python 3.7 -> Next 순으로 진행

5 그러면 설정이 가능해지는데 소스 코드, 가상 환경 경로를 수정해준다

6 WSGI configuration file을 클릭

괄호 친 코드를 주석 처리

맨 아래 FLASK 부분 아래와 같이 수정하고 Save

7 Web으로 넘어와 Reload를 클릭하면 끝이다!

잘 접속되는 것을 확인할 수 있다!!

github: https://github.com/kimjinho1/flask-study/tree/master/pythonanywhere

기본적인 그리디 알고리즘 문제이다. 

for _ in range(int(input())):
    j, N = map(int, input().split())
    li = []
    for i in range(N):
        r, c = map(int, input().split())
        li.append(r*c)
    li.sort(reverse=True)
    cnt = 0
    while j > 0:
        j -= li[cnt]
        cnt += 1
    print(cnt)

기본적인 그래프 탐색 문제이다. 최단거리를 찾는 문제이므로 BFS로 풀었다.

from collections import deque

def bfs():
    q = deque()
    q.append((0))
    while q:
        node = q.popleft()
        n = li[node]
        if check[n] == 0 and node != n:
            q.append(n)
            check[n] = check[node] + 1
            if n == K:
                return ;
    
N, K = map(int, input().split())
li = [int(input()) for _ in range(N)]
check = [0]*N
bfs()
print(check[K] if check[K] else -1)

기본적인 BFS, DFS 문제이다. (N, N) 좌표에 도착할 수 있는지를 확인해주면 된다.

BFS 풀이

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x, li[y][x]))
    while q:
        y, x, d = q.popleft()
        for i, j in [(1, 0), (0, 1)]:
            Y, X = y + d*i, x+ d*j
            if 0 <= Y < N and 0 <= X < N and d != 0:
                if Y == X == N-1:
                    return True
                q.append((Y, X, li[Y][X]))
    return False
        
N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]    
print("HaruHaru" if bfs(0, 0) else "Hing")

DFS 풀이

import sys
sys.setrecursionlimit(10000)

def dfs(y, x):
    global ok
    d = li[y][x]
    for i, j in [(1, 0), (0, 1)]:
        Y, X = y + d*i, x+ d*j
        if 0 <= Y < N and 0 <= X < N and d != 0:
            if Y == X == N-1:
                ok = 1
                return ;
            dfs(Y, X)
        
N = int(input())
li = [list(map(int, input().split())) for _ in range(N)]
ok = 0
dfs(0, 0)
print("HaruHaru" if ok else "Hing")

기본적인 그래프 탐색 문제이다. 

각 노드별로 몇 명의 사람을 만날 수 있는지 확인하고, 최댓값의 인덱스를 출력해주면 된다 -> res.index(max(res))

def dfs(node, cnt):
    check[node] = 1
    n = graph[node][0]
    if check[n] == 0:
        cnt = dfs(n, cnt+1)
    return cnt

N = int(input())
graph = [[] for _ in range(N+1)]
res = [0]*(N+1)
for u in range(1, N+1):
    v = int(input())
    graph[u].append(v)
for i in range(1, N+1):
    check = [0]*(N+1)
    res[i] = dfs(i, 1)
print(res.index(max(res)))

브루트포스 알고리즘 & 백트래킹 문제이다.

나누기 처리를 할 때 int(n1 / n2) 또는 -(-n1 / n2) 같은 방식으로 나눠야 하는데,

처음에 이걸 몰라서 계속 틀렸다.

def dfs(res, i, add, sub, mul, div):
    global N
    if i == N:
        res_li.append(res)
    else:
        if add:
            dfs(res + nums[i], i+1, add-1, sub, mul, div)            
        if sub:
            dfs(res - nums[i], i+1, add, sub-1, mul, div)
        if mul:
            dfs(res * nums[i], i+1, add, sub, mul-1, div)
        if div:
            dfs(int(res / nums[i]), i+1, add, sub, mul, div-1)          
    
N = int(input())
nums = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())
res_li = []

dfs(nums[0], 1, add, sub, mul, div)
print(max(res_li))
print(min(res_li))

begin에서 target으로 가는 최단경로의 길이를 찾는 문제이다.

두 단어의 차이가 한 글자면 이동 가능하다. 이동 가능한지 판별하는 부분은 아래의 조건문같이 구현했다.

if len([1 for i in range(N) if node[i] != n[i]]) != 1:

dfs를 사용해서 이동 가능한 모든 경로를 다 돌아보고 현재 node가 target이라면

res리스트에 지나왔던 경로의 길이를 append해준다. 마지막에 min(res)를 반환해주면 끝이다.

def solution(begin, target, words):
    def dfs(cnt, node, li, route):
        if node == target:
            res.append(cnt)
        for i, n in enumerate(li):
            if len([1 for i in range(N) if node[i] != n[i]]) != 1:
                continue
            li.pop(i)
            dfs(cnt+1, n, li, route+[n])
            li.insert(i, n)
            
    if target not in words:
        return 0
    
    N = len(begin)
    res = []
    dfs(0, begin, words, [begin])
    
    return min(res) if res else 0

간단한 그래프 탐색 문제이다. 반복문을 돌면서 체크가 안된 노드가 있다면 ans += 1을 하고

그 노드부터 시작하여 dfs 또는 bfs를 돌려서 갈 수 있는 길을 다 체크해주면 된다.

check[i] = 0 -> i 노드 들린 적 없음 -> 탐색 시작

check[i] = 1 -> i 노드 들린 적 있음 -> 탐색 X 

보아하니 백준 실버 4 ~ 실버 2 정도가 프로그래머스 Level 3이랑 비슷한 것 같다.

DFS 풀이

def solution(n, computers):
    def dfs(node):
        if graph[node] and check[node] == 0:
            check[node] = 1
            for n in graph[node]:
                dfs(n)
    
    graph = [[]]
    for i in range(n):
        graph.append([j+1 for j in range(n) if computers[i][j] == 1 and i != j])
    
    check = [0]*(n+1)
    ans = 0
    for i in range(1, n+1):
        if check[i] == 0:
            dfs(i)
            ans += 1

    return ans

BFS 풀이

from collections import deque

def solution(n, computers):
    def bfs(node):
        q = deque([node])
        while q:
            node = q.popleft()
            if graph[node] and check[node] == 0:
                check[node] = 1
                for n in graph[node]:
                    q.append(n)
    
    graph = [[]]
    for i in range(n):
        graph.append([j+1 for j in range(n) if computers[i][j] == 1 and i != j])
    
    check = [0]*(n+1)
    ans = 0
    for i in range(1, n+1):
        if check[i] == 0:
            bfs(i)
            ans += 1

    return ans

리스트가 아닌 딕셔너리로 그래프를 구현해서 풀어야되는 문제이다.

올바른 경로를 찾을 때까지 뺑뺑이를 돌려줘야 되는 문제라 dfs로 풀었다. 

핵심은 dfs 함수를 재귀로 넘기기 전에 딕셔너리의 value값을 삭제하고 재귀후에 다시 추가해주는 부분같다.

처음에 이 부분을 잘못 생각해서 푸는데 오래걸렸다... 

from collections import defaultdict

def dfs(N, graph, route, node):
    if len(route) == N+1:
        return route
    for i, n in enumerate(graph[node]):
        graph[node].pop(i)
        ret = dfs(N, graph, route+[n], n)
        graph[node].insert(i, n)
        if ret:
            return ret
        
def solution(tickets):
    N = len(tickets)
    graph = defaultdict(list)
    for s, e in tickets:
        graph[s].append(e)
    for k in graph:
        graph[k].sort()
    
    route = dfs(N, graph, ["ICN"], "ICN") 
    return route

추가로 defaultdict라는 친구에 대해 알게되었다.

여태까지 딕셔너리에 값을 채울 때나 키값이 있는지 조건문으로 확인할 때 get을 사용해서 따로 처리하곤

했었는데, defaultdict를 사용하면 오류 걱정없이 그냥 넣어주고 확인하면 된다! 

순위를 정확하게 매길 수 있는 사람이 몇 명인지 찾는 문제이다.

플로이드 와샬 알고리즘을 모른다면 풀기 조금 힘들 것 같은 문제이다. 

플로이드 와샬을 사용해서 최단경로가 아닌 승패를 확인해주면 된다.  

EX)

graph[0][1] = 1 -> 1가 2를 이김

graph[4][3] = -1 -> 4가 5를 이김

graph[1][2] = 0 -> 2와 3의 승패를 알 수 없음 

def solution(n, results):
    graph = [[0]*n for i in range(n)]
    for a, b in results:
        graph[a-1][b-1] = 1
        graph[b-1][a-1] = -1
        
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if graph[i][k] == 1 and graph[k][j] == 1:
                    graph[i][j] = 1
                if graph[i][k] == -1 and graph[k][j] == -1:
                    graph[i][j] = -1
    
    ans = 0
    for li in graph:
        if li.count(0) == 1:
            ans += 1
    return ans