수학과의 개발자 도전기

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

Lv2 문제고, 스스로 푼 문제다!

문제 이해

최종 목적지까지 최소한의 건전지로 가려면 순간이동을 최대한 많이 활용해야 한다.

목적지부터 거슬러 올라가면 짝수인 수는 짝수 // 2인 수에서 순간이동을 하면 되므로 상관 없고, 문제는 홀수인 지점에서는 홀수 - 1까지는 순간이동하고 홀수 - 1에서 한칸만 이동하면된다 

1. n이 짝수라면 n을 n // 2로 이동시키면 된다

2. n이 홀수라면 n -= 1을 한 다음 사용한 건전지를 count에 +1해주면 된다

3. n == 1일 때는 0에서 한칸 움직이면 되므로 count += 1을 해주고 break한다 

- 정답 풀이 :

def solution(n):
    count = 0
    while True:        
        if n == 1:
            count += 1
            break
        if n % 2 == 1:
            count += 1
            n-= 1
        else:
            n //= 2
            
    return count

- 시도한 풀이 

정확성은 다 맞았는데, 효율성에서는 다 틀린 문제다 (1억 이상의 수에 대해서는 시간초과가 발생하는 것 같다)

이전에 계산한 걸 다시 사용하는 것 같아 dp로 풀었는데 큰 수에 대해서는 시간초과가 발생하는 풀이인 것 같다

def solution(n):
    dp = [0, 1, 1]
    
    for i in range(3, n + 1):
        if i % 2 == 0:
            dp.append(min(dp[i // 2], dp[i - 1] + 1))
            
        else:
            dp.append(dp[i - 1] + 1)

    return dp[n]

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12985

Lv2 문제이고, 스스로 푼 문제다!

문제 이해 

a와 b 선수가 계속 이기다가 둘이 붙게되는 라운드 숫자를 반환한다 

처음에는 일일이 순서를 저장하고 두 숫자가 만날 때 라운드를 반환해야 하나 싶었지만 그렇게 하면 시간이 너무 오래 걸리고 구현도 번거로울 것 같아서 다른 방법을 생각해봤다 

그래서 생각한게 a 와 b의 숫자로 정답을 구할 수 있지 않을까 싶었다 

a와 b는 계속 이기니까 결국 (각각의 번호 + 1 // 2)가 해당 라운드에서 각 선수들의 순서인 것을 찾았다 

위 식은 예제에서 알아냈는데, 2라운드에서 4번은 두번째, 7번은 4번째이므로 (4 + 1) // 2 == 2, (7 + 1) // 2 == 4임을 알 수 있다

이렇게 했을 때 90퍼센트만 맞았는데 틀린 거를 생각해보니 

a, b = 2, 3인 경우 둘의 차이는 1이지만 실제로 둘이 마주치는 라운드는 2라운드이다. 

그래서 정답을 반환하는 경우는 차이가 1이면서 가장 작은 수가 홀수인 경우라고 생각해 코드를 작성하니 정답이 떴다 

- 정답 풀이 : 

def solution(n,a,b):
    x, y = min(a, b), max(a, b)
    current = 1
    
    while True: 
        if abs(x - y) == 1 and (x % 2 == 1):
            return current
        x = (x + 1) // 2
        y = (y + 1) // 2
        current += 1
        
    return current

- 시도해본 풀이 : 

2 3 인 경우 차이는 1이지만, 2라운드에서 붙는다 

하지만 이 풀이라면 3 -2 == 1이므로 1을 출력한다 

 둘 중 최솟값이 홀수이고, 두 수의 차이가 1일 때 같은 라운드에서 붙는다고 생각해 코드를 정답 풀이와 같이 수정했고, 정답이 떴다 

def solution(n,a,b):
    x, y = min(a, b), max(a, b)
    current = 1
    
    while True: 
        if abs(x - y) == 1:
            return current
        x = (x + 1) // 2
        y = (y + 1) // 2
        current += 1
        
    return current

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12953

문제 이해 

주어진 배열의 원소들의 최소 공배수를 구하는 것이다

풀이 이해

0 인덱스와 1 인덱스의 최소 공배수를 구한 다음 arr에 추가하고

마지막에 원소 하나가 남았을 때 그게 정답이므로 반환해준다 

처음에는 각 원소들을 전체의 최대공약수로 나눈 다음 다 곱하고, 마지막에 최대 공약수를 곱하는 방법을 생각했다. 

예제에서는 다 정답이 떴지만 테스트에서는 다 실패했다 

예외를 생각해보니 [6,12,36]인 경우 정답은 36이지만, 위 풀이대로 라면 72가 출력돼 틀린다 

그래서 모든 원소의 최소 공배수를 한번에 구하려고 하기보다 두개의 최소 공배수들을 누적해가면 정답이 나오는 걸 배웠다

- 정답 풀이 :

from math import gcd

def lcm(x,y):
    return x * y // gcd(x,y)

def solution(arr):
    while True:
        arr.append(lcm(arr.pop(), arr.pop()))
        if len(arr) == 1:
            return arr[0]

- 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12973

Lv2. 문제다!

문제 이해 

반복되는 두개의 문자를 지워가면서 문자열이 다 지워지면 1을 출력하고, 그렇지 않으면 0을 출력한다 

stack 리스트에 s의 문자들을 삽입하는데, 만약 추가하는 문자와 -1 인덱스의 문자가 같다면 문제의 조건을 만족하므로 

pop()으로 -1 인덱스를 꺼낸다 

아니라면 그냥 추가만한다 

s의 문자가 모두 없어졌으면 1을, 아직 남은 문자가 있다면 0을 출력한다 

- 정답 풀이 : 

def solution(s):
    stack = []
    
    for c in s:
        if not stack:
            stack.append(c)
        else:
            if stack[-1] == c:
                stack.pop()
            else:
                stack.append(c)
                
    if stack:
        return 0
    return 1

- 시도해본 풀이 :

이렇게 하면 30%만 맞는다

같은 문자 두개 반복되는 경우는 어떻게 식별할 수 있는데 이제 0이 출력되는 경우는 어떻게 판별해야하나 아이디어가 떠오르지 않았다. 

그러다가 나도 stack을 이용하는 걸 생각했었는데 아직 다루는 방법이 미숙한 것 같다 

def solution(s):    
    s= list(s)
    i = 1
    flag = True
    n = len(s)
    while True :
        if i == n // 2:
            flag = False
            break
        if len(s) == 0:
            break            
        if s[i - 1] == s[i]:
            s = s[ : i - 1] + s[i + 1 :]
            i = 1
        else:
            i += 1
            
    if not flag:
        return 0 
    else: 
        return 1