프로그래머스[Python] - 이진 변환 반복하기, 점프와 순간 이동, 스킬트리

이진 변환 반복하기

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

코딩테스트 연습 - 이진 변환 반복하기

문제 내용 : 이진수로 되어있는 문자열이 들어올때, 2가지 조건을 만족시키면서 '1' 하나만 남을때까지 몇번 처리했는지? 0은 몇개 지웠는지 판단한다.

조건

1. x의 모든 0 제거
2. 제거하고 난 후 x의 길이를 c라고 하면, x 를 c의 2진법으로 표현한 문자열로 바꾼다.

알고리즘 : 단순 구현, 문자열, 이진수

점프와 순간 이동

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

코딩테스트 연습 - 점프와 순간 이동

문제 내용 : 어느 연구소에서 수트를 만드는데, 2가지로 갈 수 있다.

1. K칸 앞으로 점프(단, K만큼 연료가 든다.)
2. (현재까지 거리) * 2 에 순간이동 (연료가 안든다.)

연료를 최소로해서 N까지 가려고 할때, 얼마의 연료가 들겠는가?

(숫자 N: 1 이상 10억 이하의 자연수)

알고리즘 : Greedy(탐욕 알고리즘), 단순 구현

풀이과정 : 처음에 1~7까지 경우에 수만 따져보니 단순한 규칙이 나왔다. 거리가 1이라면 반드시 1칸은 뛰어야하고 1이라는 연료는 무조건 든다. 그 다음 짝수일 경우는 이전 절반과 동일한 만큼 순간이동 하면되기 때문에 그 값을 그대로 가져오면 된다. 홀수일때는 이전 수의 + 1만 해주면 된다.

입력이 10억 까지라서 해시를 사용해서 dp 를 이용하면 되겠다고 생각했는데(사실 Dynamic Programming의 정의에 맞지 않지만 그렇게 생각했다..ㅋㅋ) 어째뜬, 그렇게 해시맵을 이용해서 속도를 최적화하면 되겠다고 문제를 풀었는데 시간초과가 났다. 이건 탐색 자체를 하면 안되고 더 Greedy 하게 문제를 풀어야겠다고 생각했다.

가만 생각해보니 / 2 할때 마다 짝수일 경우와 홀수일 경우 나눠서 계산하면 되겠다고 생각이 들어 N 부터 나눠가면서 최적의 수를 계산했다. 아주 빠른 성능을 낼 것이고, O(N)보다 더 빠른 O(logN)의 시간이 걸렸을 것이다. 그래서 해결!

스킬 트리

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

코딩테스트 연습 - 스킬트리

문제 내용 : skill이 하나 있고, skill_tree들이 있을때, skill_tree에 있는 것들 중에서 skill에 맞게 짜여진 skill_tree가 몇개인가?

알고리즘 : Queue, 단순 구현

회고 : 이 문제 몇달 전에 몇시간을 고민해도 풀리지 않았던 문제였다. 과거 코드가 그대로 남아있었다. 걱정이었지만, 10분도 안되어서 문제를 해결하게 되었다. 매일 매일 코딩 문제를 푸니까 조금씩 늘어가는 것 같아서 기분은 좋다.

풀이과정 : 예전 코드를 보니 문제를 제대로 안읽었던 것 같다. skill들 종류가 여러가지인 줄알아서 그거에 맞게 따져줘야하는 줄 알았는데, 다시 제대로 읽어보니 string 하나였다.ㅋㅋ.. 그럼 그냥 이 스킬 순서에 맞게(Queue이용) 순서대로 꺼내주면서 skill_tree가 순서의 규칙을 잘 지켰는지 판단만 해주면 된다.

skill에 없는 스킬같은 경우 조건 만족과 상관없기 때문에 그냥 continue로 올려보낸다.(없어도 되는 코드) 만일 skill에 있는 스킬이라면 가장 앞에 것부터 비교해서 다르면 규칙이 어긋난 것일 것이다. 같다면 문제가 없기 때문에 skill에 앞에 있는 스킬부터 빼버린다. 문제가 생기면 break 로 끊어버린다.