수학과의 개발자 도전기

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

Lv2 문제다!

문제 이해

• 삼각형에 맞는 구조로 answer를 설정한다
• 행, 열은 -1, 0으로 설정한다. (행은 처음 시작에 +1 되므로 indexerror를 방지하기 위해 -1이다)
• 각 위치에 해당하는 숫자는 num으로 표신한다 
• 방향은 수직 아래, 수평 오른쪽, 대각선 왼쪽으로 진행하므로 3가지 경우로 나누어서 진행한다.
  • 첫번째는 열은 고정이고 행을 +1 하면서 입력 숫자도 +1 하는 경우
  • 두번째는 행은 고정이고 열을 + 1하면서 입력 숫자도 +1 하는 경우
  • 세번째는 열,행을 모두 -1씩 하면서 입력 숫자도 +1 하는 경우
• answer의 각 행의 원소들을 추가해서 반환한다 

- 정답 풀이 : 

인덱스 먼저 이동한 다음에 값을 바꿔준다 

def solution(n):
    answer = [[0 for j in range(1, i + 1)] for i in range(1, n + 1)]
    
    x, y = -1, 0 #처음 시작은 아래로 내려가기 때문에 x = -1
    num = 1
    
    for i in range(n):
        for j in range(i, n):
            if i % 3 == 0:
                x += 1                
            elif i % 3 == 1:
                y += 1
            else:
                x -= 1
                y -= 1
                
            answer[x][y] = num
            num += 1
            
    return sum(answer, [])

- 시도해 본 풀이 :

인덱스 처리가 미흡해서 틀리게 나온 것 같다. 특히 왼쪽 대각선으로 움직이는게 잘 안된다 

위의 풀이를 참고해서 인덱스만 따로 바꾸고 행렬 값은 공통으로 바꾸는 쪽으로 한번 생각해 봐야겠다(그게 언제가 될지,,,)

def solution(n):
    result = [[-1] * n for _ in range(n)]
    
    temp = n
    count, cycle = 0, 0
    row, col = 0, 0
    number = 0
    while True:
    
        if count == n * (n + 1) // 2:
            break        
        if cycle % 3 == 0 :
            for i in range(temp):
                number += 1
                result[row + i][col] = number
            count += temp
            cycle += 1
            temp -= 1
            row += temp  
            
        if count == n * (n + 1) // 2:
            break
        col += 1   
        if cycle % 3 == 1:
            for i in range(temp):
                number += 1
                result[row][col + i] = number 
            count += temp
            cycle += 1
            temp -= 1
            col += temp
            
        if count == n * (n + 1) // 2:
            break
        if cycle % 3 == 2:
            for i in range(1, temp + 1):
                number += 1
                result[row - i][col - i] = number 
            count += temp
            cycle += 1
            temp -= 1
            row -= temp
            col -= temp
            
    answer = []
    for i in range(n):
        for j in range(i + 1):
            answer.append(result[i][j])
      
    return answer

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

Lv2 문제다!

숫자 3과 연관이 무조건 있다고 생각해 나름 로직을 생각했으나, 답까지는 작성 못했다.

그래서 풀이를 찾아봤는데, 모두 좋은 것 같아 기록해보려한다. 

124 나라의 특징은 다음과 같다.

• 1 = 1, 2=2, 3= 4이다.
• 4부터 자릿수가 늘어난다 4 = 11
• 7에서 앞자리 수가 바뀐다 7 = 21
• 10에서 앞자리 수가 2로 커진다 10 = 41

규칙 

• 3으로 나눠지지 않는 경우
  • 이 경우는 1,2가 가능한데, 이는 124 나라의 숫자이므로 사용가능한 숫자들이다
• 3으로 나눠지는 경우
  • 3진법에서 3으로 나누어 떨어지는 수는 일의 자리가 0이 된다. 124 나라에서는 이 일의 자리수를 4로 변경한다 
  • 3으로 나눈 몫에서 1을 뺀 값이 10의 자리 수 이상이다 
  • 여기에서 왜 다음 n을 n // 3이 아닌 n // 3 - 1로 했는지 이유를 찾아봤다. 

• 숫자 문자들을 오른쪽으로 추가했으므로, 원래 답과 반대 방향이라 역순으로 반환해주면 된다 

- 정답 풀이 1 : 

참고한 블로그

def solution(n):
    answer = ''
    
    while n:
        #3의 배수가 아닌 경우 -> 1,2
        if n % 3:
            answer += str(n % 3)
            n //= 3
        #3의 배수인 경우  
        else:
            answer += '4'
            n = n // 3 - 1
            
    return answer[ : : -1]

- 정답 풀이 2: 

3으로 나눴을 때 나머지가 

0일 때 -> 1 

1일 때 -> 2

2일 때 -> 4 

인 것을 num의 인덱스로 활용한 풀이다. 

def change124(n):
    num = ['1','2','4']
    answer = ""


    while n > 0:
        n -= 1
        answer = num[n % 3] + answer
        n //= 3

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

Level2 문제이다! 

물건 종류와 갯수를 따로 주고, 이를 가지고 진행해야하므로 해쉬를 사용해야한다고 생각했다. 

10개 단위로 딕셔너리를 만들어서 진행하면 시간 복잡도가 걸릴 것 같아서 그렇게 안 했는데, 그렇게 했어야 하는 문제다. 

정답으로는 처음으로 할인 받는 날을 반환하는 것이 아닌 원하는 제품을 모두 할인 받을 수 있는 회원등록 날짜의 총 일수이다. 

풀이 로직

discount 가장 마지막에서 10개의 단위가 끝나야 하므로 discount는 0인덱스 부터 len(discount) - 10 인덱스까지 탐색한다

오른쪽으로 한칸씩 이동할 때마다 temp _dict 딕셔너리를 생성해 10개만큼 진행한다

탐색한 10개의 물품과 갯수를 temp_dict에 저장한 후 이게 want_dict와 같다면 days += 1을 해준다

마지막에 days를 반환한다 

배운 것 

딕셔너리끼리는 == 으로 일치 여부를 확인할 수 있다 

- 정답 풀이 :

def solution(want, number, discount):
    answer = 0
    x, y = sum(number), len(discount)
    want_dict = {want[i] : number[i] for i in range(len(want))}
    
    days = 0
    for i in range(y - x + 1):
        temp_dict = {}
        for j in range(i, i + x):
            if discount[j] in temp.keys():
                temp_dict[discount[j]] += 1
            else:
                temp_dict[discount[j]] = 1
                
        if temp == want_dict :
            days += 1
            
    return days

- 시도해본 풀이 :

음,,, 너무 장황한 것 같다 

먼저 discount의 10개를 확인한 다음 그게 answer와 같은지 확인하고, 아니라면 오른쪽으로 하나씩 추가하고 왼쪽으로 하나씩 삭제하면서 answer와 일치하는지 확인하는 건데 적절한 풀이는 아닌 것 같다 

매번 해쉬맵을 만들면 시간 복잡도에 걸릴 것 같아서 기존의 해쉬맵을 유지하는 방향으로 갔는데, 매번 만들어도 괜찮은 것 같다 

def solution(want, number, discount):
    days = 0
    stuff = {}
    for i in range(10):
        if discount[i] not in stuff : 
            stuff[discount[i]] = 1
        else:
            stuff[discount[i]] += 1
            
    answer = {}
    for i in range(len(want)):
        answer[want[i]] = number[i]
        
    
    flag = True
    for i in stuff.keys():
        if i not in answer or stuff[i] != number[i]:
            flag = False
            break
      
    if flag : 
        return days + 1

    else : 
        x = 0
        count = 0
        for i in range(10, len(discount)):
            if discount[i] not in stuff:
                stuff[discount[i]] = 1
            else : 
                stuff[discount[i]] += 1
            
            stuff[discount[x]] -= 1
            days += 1
            x += 1
            #stuff와 answer이 같은지 확인 
            for i in answer.keys():
                if i in stuff and stuff[i] == answer[i]:
                    count += answer[i]
                
                          
            if count == 10:
                return days + 1
            else:
                count = 0
                
        if count != 10 :
            return 0

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

Lv2 문제이다!

처음엔 dp나 어떤 규칙이 있어야 풀릴 것 같아서 찾다가 안돼서 결국 풀이 찾아본 문제이다

코드 참고한 블로그

이해하는데 도움이 된 블로그

생각보다 규칙은 간단했다

숫자가 짝수라면 오른쪽 끝이 무조건 0이므로 이를 1로 바꿔주면 된다.

숫자가 홀수라면 가장 오른쪽에 있는 0을 1로 바꿔주고, 그 오른쪽에 있는 값을 0으로 바꿔준다(01 -> 10) 이렇게 하면 더 큰 수로 비트 두 개를 변경할 수 있다. 

연산을 마친 2진수 숫자는 10진수 숫자로 변경한 다음 answer에 추가해준다

- 정답 풀이 :

def solution(numbers):
    answer = []
    
    for number in numbers:
        bin_number = list('0' + bin(number)[2 : ])
        index = ''.join(bin_number).rfind('0') #가장 오른쪽에 있는 0의 인덱스
        bin_number[index] = '1'
        
        if number % 2 == 1:
            bin_number[index + 1] = '0'
        
        #2진수를 10진수로 변환해서 추가
        answer.append(int(''.join(bin_number), 2))
        
    return answer