[SW 정글 134일차] 알고리즘 문제 적응기

오늘은 어제 자기소개서 작성 마무리 작업으로 하루를 시작했다.

모든 질문에 대한 답변은 작성해놓은 상태였지만 다른 사람이 읽는데 어려움이 없는가?를 해결하기 위해 10번, 20번 다시 읽어보며 작은 부분들을 고쳐나갔다.

그리고 정글 1기를 수료하고 현업에서 개발자로 일하고 계신 분들에게 메일을 보내어 피드백을 부탁드렸다.

정말 너무 감사하게도 바쁘신데도 불구하고 좋은 말씀들에 대한 답장을 보내주셨다.

나의 이력서, 자기소개서를 읽어보며 세세하게 피드백을 주신 분도 있고 이력서, 자기소개서의 포괄적인 역할에 대해 말씀을 해주신 분들도 있었다.

 

하나하나 세세히 읽어보며 내가봐도 바꿔야하는 부분들을 수정을 진행했다.

 

자기소개서 작성은 어느정도 마무리를 하고 알고리즘 2문제를 풀었다.

오늘 알고리즘 2문제를 풀면서 느낀 것들이 많아서 풀이과정을 정리해보려고 한다.

 

 

<첫 번째 문제>

https://www.acmicpc.net/problem/2941

2941번: 크로아티아 알파벳

문제를 읽어보며 내가 가져갈 수 있는 힌트를 살펴봤다.

알파벳 소문자와 '-', '='로만 이루어져 있다.

구현(완전 탐색)으로 풀 수 있다는 것은 입력범위를 보고 알 수 있었고 특수문자로는 '-', '='만 있다는 것에 그러면 -, =가 나오면 앞에 문자만 확인해서 하나의 크로아티아 알파벳으로 변경되겠다는 것을 이용해야겠다는 생각을 했다.

 

나는 큐(queue)자료구조를 이용해서 입력문자를 큐에 넣어서 앞에 문자를 하나씩 빼며 확인하는 방식으로 접근했다.

이유는 크로아티아 알파벳으로 변경가능한 문자를 보면 c=, c-, dz=, d-, lj, nj, s=, z=로 맨 앞 알파벳이 제한되어 있기 때문에 하나씩 빼면서 조건문으로 판단하면 된다고 생각했기 때문이다.

 

풀이 코드는 아래와 같다.

import sys
from collections import deque

word = sys.stdin.readline().rstrip()

double_alphabet = set({"d", "l", "n"})
single_alphabet = set({"c", "s", "z"})
answer = 0

queue = deque(list(word))
while queue:
    alphabet = queue.popleft()

    if alphabet in single_alphabet:
        if len(queue) > 0 and (queue[0] == '=' or queue[0] == '-'):
            queue.popleft()
            
    elif alphabet in double_alphabet:
        if alphabet == 'd':
            if len(queue) > 1 and queue[0] == 'z' and queue[1] == '=':
                queue.popleft()
                queue.popleft()
            elif len(queue) > 0 and queue[0] == '-':
                queue.popleft()
        elif len(queue) > 0 and queue[0] == 'j':
            queue.popleft()

    answer += 1
print(answer)

 

풀고 나서 이전에 내가 풀었던 풀이를 봤는데 이렇게 조건문을 덕지덕지하지 않아도 쉽게 풀 수 있었던 문제였다...

import sys

T = sys.stdin.readline().rstrip()
dics = ["c=", "c-", "dz=", "d-", "lj", "nj", "s=", "z="]
for key in dics:
    T = T.replace(key, "_")
print(len(T))

다시 뇌가 말랑말랑해지도록 많이 풀어봐야겠다.

 

 

<두 번째 문제>

https://programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

두 번째 문제는 DFS/BFS 문제였다.

처음에는 BFS로 접근을 했는데 코드를 짜다보니 너비 우선 탐색을 해버리면 여행경로를 뽑아내는게 어렵다는 생각을 했다.

그래서 DFS로 풀어야겠다는 판단을 했고 다시 풀기 시작했다.

일단은 입력 예시를 보면 바로 깊이 우선 탐색을 하기에는 어려운 구조였다.

그래서 dictionary로 변경해주는 작업을 먼저 해주었다.

 

제한사항을 읽어보면 주어진 항공권은 모두 사용해야된다는 말과 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return하라고 나와있다.

다시 입력 예시를 확인해봤고 지역을 2번이상 들리는 곳도 있을 수 있다는 생각을 했고 중복체크는 불필요하다는 생각을 했다.

 

풀이코드는 다음과 같다.

from collections import defaultdict

def dfs(routes):
    stack = ["ICN"]
    path = []
    while stack:
        position = stack[-1]
        if position not in routes or len(routes[position]) == 0:
            path.append(stack.pop())
        else:
            stack.append(routes[position].pop(0))
    return path[::-1]

def solution(tickets):
    routes = defaultdict(list)
    for departure, arrival in tickets:
        routes[departure].append(arrival)
        
    for route in routes:
        routes[route].sort()
    
    answer = dfs(routes)
        
    return answer