프로그래머스[Python] - 괄호 회전하기, 큰 수 만들기, 배달

괄호 회전하기

문제 url : https://programmers.co.kr/learn/courses/30/lessons/76502

코딩테스트 연습 - 괄호 회전하기

문제 내용 : '{}', '{()}' 와 같은 규칙을 지키는 올바른 괄호 문자열이 있을때, 이 문자열을 회전하려고 한다. 회전할 때마다 이것이 올바른 문자열인지 판단해야 한다. 그래서 올바른 문자열이 몇개인지 판단하라

알고리즘 : 단순 구현, 분할 정복, Stack을 이용한 문자열 비교

풀이과정 : 우선 문자열이 들어오면 list로 쪼갰다.(나는 보통 문자열이 들어오면 list화 시키는 것이 처리하기 편해서 습관적으로 한다.) 그 다음 인덱스마다 slicing해서 문자열을 회전시키고 회전시킨 문자열마다 cal 함수에서 올바른 문자열인지 판별해서 return 한다.

판별 : 우선 pair라는 쌍을 지정했다. 이유는 왼쪽, 오른쪽 문자열끼리 짝꿍을 이어주기 위함이었다. 들어온 문자열의 한 문자별로 left 기호라면 stack에 담아둔다. 그리고 righ 기호라면 스택에 가장 최근 괄호를 빼내어서 짝꿍이 맞는 지 확인한다. 그래서 짝꿍이 안맞으면 올바른 문자열이 아닐것이다. 또한 빈 stack에서 pop한다는 것은 왼쪽 괄호가 들어가지 않았는데 오른쪽 기호가 들어왔다는 것으로 바로 false를 리턴한다.

마지막은 '(' 와 같은 하나의 문자만 있을때, stack에 최종은 하나만 들어가있을 것인데, 올바른 문자열이라면 스택이 비어있을 것이기 때문에 이 또한 예외처리로 내보낸다.

큰 수 만들기

문제 url : https://programmers.co.kr/learn/courses/30/lessons/42883

코딩테스트 연습 - 큰 수 만들기

문제 내용 : k개의 갯수의 숫자를 빼서 가장 큰 수를 만들어라

알고리즘 : Greedy 알고리즘, Stack

풀이 : combination으로 k 개 뺀 나머지를 구해서 가장 큰것만 뽑으려 했는데, 역시나 길이를 보면 1000000자리이기 때문에 조합을 구할때 시간초과가 날 것이다.

그래서 가장 왼쪽부터 크기를 비교해 가면서 크기가 큰 수가 있다면 스택에서 빼버린다. 이때 Greedy하게 생각을 해야하는데, k개를 뺀다는 것은 앞에서 부터 숫자들 중에 len(number) - k 자리 문자열을 만들어야하고, [:k+1] 까지는 숫자들 중에 큰수만을 처리하도록 while을 돌리고 나머지는 그냥 이어 붙힌다. 왜냐면 앞자리가 클수록 큰 수이기 때문이다.

배달

문제 url : https://programmers.co.kr/learn/courses/30/lessons/12978

코딩테스트 연습 - 배달

문제 내용 : N개의 마을이 있고, 마을 사이에 이동하는 시간과 함께 연결되어 있다. 이때, 총 배달 시간보다 작게끔 배달을 해야한다. (K) 어느 장소에 배달할 수 있을까?

알고리즘 : BFS, 다익스트라 알고리즘

풀이과정 : 나는 BFS 같은 Search 알고리즘에 적용되는 visited 라는 리스트는 크게 2가지 종류가 있다고 생각한다. 해당 지역을 방문했는지, 안했는지 T, F 유형과 다익스트라 알고리즘 처럼 가중치가 있는 그래프에서 가중치들을 계산하기 위한 용도로 사용하는 유형

위 문제는 2번째 유형의 BFS이다. 우선 양방향 연결 그래프이기 때문에 들어온 input값을 조금 수정하여 양방향 그래프로 변환 시켰다. 그리고 출발하는 1번 마을부터 BFS를 적용한다.

BFS를 적용할때, 각 마을마다 배달 시간을 계산하는 용도로 Visited 리스트를 만들어 두었다. 우선 각 마을까지 sys.maxsize로 무한대로 값을 지정해 둔다. 1번 마을은 시작하는 용도이기 때문에 걸리는 시간은 0일 것이다.

Queue 자료구조를 사용하여 1번 마을과 연결되어 있는 마을들을 넣고 판단한다. 만일 이전 마을까지 걸린 배달 시간의 최소값(visited[start])에 현재 마을까지(time) 더한 것이 현재 마을에 계산된 걸린 시간보다 작을 경우 해당 값을 visited 로 넣어 둔다. 이로써 탐색을 할때, 가장 최소의 시간을 마을마다 적용할 수 있게 된다.

모든 마을을 탐색한 후, 각 마을들의 최소 배달 시간을 훑어서 K보다 작거나 같다면 갯수를 세어 출력한다.