Algorithm/programmers/level1/210611/10문제 (with python)

2021년 6월 11일

  • 프로그래머스에서 푼 level1 10문제 모음집입니다.
  • 문제 풀이에 대한 설명은 코드에 주석으로 표시하였습니다.

📖문제1 : 포켓몬

⌨ 코드

def solution(nums):
    # 포켓몬 종류의 수
    types = len(set(nums))
    # 가져갈 포켓몬의 수 
    N = len(nums)//2
    
    # 포켓몬 종류가 가져갈 포켓몬의 수보다 적으면 정답은 포켓몬 종류의 수
    if types <= N:
        return types
    # 포켓몬 종류가 가져갈 포켓몬의 수보다 많으면 가져갈 포켓몬의 수가 정답
    else:
        return N

📖문제2 : 신규 아이디 추천

  • 문제 푸는 데 좀 오래 걸렸다..ㅜㅜ

⌨ 코드

def solution(new_id):
    answer = ''
    special_char = ['-', '_', '.']
    # 1단계
    # 문자열에 포함된 알파벳들을 모두 소문자로 만든다.
    new_id = new_id.lower()

    # 2단계
    new_id = list(new_id)
    # new_id 원본 리스트로 for문을 돌게 되면 반복문 중간에 원본이 변경되기 때문에 원하지
    # 않은 결과를 불러올 수 있어서 for문을 돌리기 위한 list 생성
    tmp_new_id = new_id[:]
    for char in tmp_new_id:
        # 알파벳이나 숫자도 아니고, 허용되는 특수문자도 아닌 것은 삭제
        if not char.isalnum() and char not in special_char:
            new_id.remove(char)
            
    # 3단계
    if len(new_id) > 1 :
        # 중간에 new_id 원본이 변하기 때문에, 이에 영향받지 않기 위해서 마지막 인덱스부터 시작
        for i in range(len(new_id)-1, 1-1, -1):
            # 현재 문자가 '.'이면
            if new_id[i] == '.':
                # 이 문자 이전도 '.'인지 확인
                if new_id[i - 1] == '.':
                    new_id.pop(i)
                    
    # 4단계
    if new_id:
        # 첫 문자가 '.'인 경우 첫 문자 제거
        if new_id[0] == '.':
            new_id.pop(0)
    if new_id:
        # 마지막 문자가 '.'인 경우 마지막 문자 제거
        if new_id[len(new_id)-1] == '.': # 파이썬 인덱싱 특성을 이용해서 [-1]로 했으면 더 좋았을 것 같다.
            new_id.pop(len(new_id)-1)
            
    # 5단계
    # new_id가 비어있으면 'a' 리스트에 추가
    if not new_id:
        new_id.append('a')
        
    # 6단계
    # new_id의 글자수가 16자 이상이면 15번째 글자수까지 자르기
    if 16 <= len(new_id):
        new_id = new_id[0:15]
        # 자른 후에 마지막 문자가 '.'라면 마지막 문자 삭제
        if new_id[14] == '.': # 파이썬 인덱싱 특성을 이용해서 [-1]로 했으면 더 좋았을 것 같다.
            new_id.pop(14)
            
    # 7단계
    # new_id의 글자수가 3자 미만이라면
    if len(new_id) <= 2:
        # new_id의 글자수가 3자가 될 때까지 마지막 문자 추가
        while len(new_id) <= 2:
            new_id.append(new_id[len(new_id)-1])

    answer = ''.join(new_id)
    return answer
  • 정규 표현식으로 푸는 방법도 있고, new_id에서 필요없는 문자들을 빼는 방식이 아닌, answer에 한글자씩 추가하는 방법도 있더라.

📖문제3 :음양 더하기

⌨ 코드

def solution(absolutes, signs):
    answer=0
    # zip을 이용해서 absolutes와 signs를 같이 반복문을 돌린다.
    for absolute,sign in zip(absolutes,signs):
        # 부호가 양수이면 더하기
        if sign:
            answer+=absolute
        # 음수이면 빼기
        else:
            answer-=absolute
    return answer

📖문제4 : 소수 만들기

⌨ 코드

  • 에라토스테네스의 체를 사용했다.
  • 검사해야하는 수의 범위가 매우 크다면 공간복잡도, 시간복잡도 상으로 문제가 되겠지만 범위가 작아서 에라토스테네스의 체를 쓸 수 있었다.
def solution(nums):
    answer = 0
    
    # 에라토스테네스의 체를 위한 표 생성
    isPrime = [True] * 3001
    isPrime[0] = False
    isPrime[1] = False
    for i in range(2, 3001):
        # 해당 수가 소수라면
        if isPrime[i]:
            j = 2
            # 해당 수의 배수는 모두 소수가 아니다.
            while i*j <= 3000:
                isPrime[i*j] = False
                j += 1

    for i in range(0,len(nums)):
        l = nums[i]
        for j in range(i+1, len(nums)):
            m = nums[j]
            for k in range(j+1, len(nums)):
                n = nums[k]
                # 서로 다른 세 수의 합이 소수이면 정답+1
                if isPrime[l+m+n]:
                    answer += 1
    return answer

📖문제5 : 로또의 최고순위와 최저순위


⌨ 코드

def solution(lottos, win_nums):
    answer = []
    # index: 당첨 번호 개수, element: 순위
    rank = [6, 6, 5, 4, 3, 2, 1]
    
    wins = 0 # 맞는 번호
    zero = 0 # 모르겠는 번호
    
    for num in lottos:
        # 당첨번호에 있다면 wins+1
        if num in win_nums: 
            wins += 1
        # 모르는 번호라면 zero+1
        if num == 0:
            zero += 1
            
    # 모르겠는 번호가 모두 당첨번호인 경우 최고순위
    answer.append(rank[wins+zero])
    # 모르겠는 번호가 모두 당첨번호가 아닌 경우 최저순위
    answer.append(rank[wins])
    
    return answer
  • 0의 개수를 셀 때 리스트의 count()메서드를 썼으면 더 간편했을걸~!

📖문제6 : 크레인 인형뽑기 게임




⌨ 코드

def solution(board, moves):
    answer = 0
    # 바구니를 담는 스택
    basket = []
    for cur in moves:
        cur -= 1 # index 계산이 편하도록 -1
        for i in range(len(board)):
            # 현재 크레인 위치에 뽑을 인형이 있다면
            if board[i][cur] != 0:
                # 일단 현재 뽑을 인형의 종류를 알아두고
                doll = board[i][cur]
                # 크레인으로 인형 뽑기
                board[i][cur] = 0
                
                # 인형이 바구니에서 사라지는 경우
                if basket:
                    # 뽑은 인형의 종류와 바구니 맨 위에 있는 인형의 종류가 같다면
                    if basket[-1] == doll:
                        basket.pop()
                        answer += 2
                        break
                # 인형이 바구니 안으로 들어가는 경우
                basket.append(doll)
                break  
    return answer

📖문제7 : 실패율

  • 지금까지 풀었던 문제중에 제일 어렵게 풀었다...ㅜㅜ 넘 복잡하게 푼 듯!

⌨ 코드

def solution(N, stages):
    answer = []

    # stage[i] 
    # = [i번째 스테이지에 도달한 플레이어 수][i번째 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수]
    stage_info = dict()
    for i in range(1,N+2):
        stage_info[i] = [0,0]

    for stage in stages:
        # 각각 스테이지에 도달한 플레이어수를 구하기 위한 연산
        for i in range(stage, 1-1, -1):
            stage_info[i][0] += 1
        # 해당 스테이지에 도달했으나 아직 클리어하지 못한 플레이어 수를 구하기 위한 연산
        stage_info[stage][1] += 1

    tmp = []
    for stage in range(1, N+1):
        # 각각 스테이지의 실패율 구하기
        if stage_info[stage][0] != 0:
            x = stage_info[stage][1] / stage_info[stage][0]
        else:
            x = 0
        tmp.append([x, stage])

    # 실패율은 높은 순으로, 실패율이 같다면 앞스테이지 우선으로 정렬
    tmp = sorted(tmp, key = lambda x: (-x[0], x[1]))
    for t in tmp:
        answer.append(t[1])

    return answer

⌨ 다른 분의 코드

  • denominator에 일단 전체 게임 이용자를 담아두고
    스테이지 1부터 순차적으로 실패율을 구할 때
    (denominator) - (이전 스테이지들에 도달했지만 아직 클리어하지 못한 플레이어의 수)가 '현재 스테이지에 도달한 플레이어의 수'를 뜻한다는 성질을 이용해서 문제를 푸셨다. 똑똑하시다..
def solution(N, stages):
    result = {}
    denominator = len(stages)
    # 스테이지1부터 순차적으로 실패율 구하기
    for stage in range(1, N+1):
        if denominator != 0:
            count = stages.count(stage)
            result[stage] = count / denominator
            denominator -= count
        else:
            result[stage] = 0
    return sorted(result, key=lambda x : result[x], reverse=True)

📖문제8 : 약수의 개수와 덧셈

⌨ 코드

  • 시간복잡도가 O(N^2)이지만, left - right이 최대 1000이라서 제한시간 내로 풀 수 있어서 이렇게.....그만.....
def solution(left, right):
    answer = 0
    for i in range(left, right+1):
        x = 0
        for j in range(1, i+1):
            if i % j == 0:
                x += 1
        if x % 2 == 0:
            answer += i
        else:
            answer -=i
    return answer

⌨ 다른 분의 코드

  • 어떤 수의 약수의 개수가 홀수라는 것의 의미는 제곱수라는 것이다!!!를 이용하셨다.
def solution(left, right):
    answer = 0
    for i in range(left,right+1):
        if int(i**0.5)==i**0.5:
            answer -= i
        else:
            answer += i
    return answer

📖문제9 : 예산

⌨ 코드

def solution(d, budget):
    answer = 0
    # 예산이 적은 순으로 정렬
    d.sort()
   
    for _budget in d:
        # 부서가 신청한 금액만큼 모두 지원해주어야 하기 때문에
        # 남은 예산이 현재 부서가 신청한 금액보다 큰 경우에만
        if 0 <= budget - _budget:
            # 금액을 지원해준다.
            budget -= _budget
            answer += 1
    return answer

📖문제 10 : 3진법 뒤집기

⌨ 코드

def solution(n):
    answer = 0
    tmp = []
    
    # n을 3진수로 표현하기
    while n:
        tmp.append(n%3)
        n = n // 3
    
    # 3진수 뒤집기
    tmp.reverse()
    # 다시 10진수로 표현하기
    for idx, m in enumerate(tmp):
        answer += (3 ** idx) * m
    return answer

⌨ 다른 분의 코드

  • int(x, base = 10)인 것을 이용하셨다.
def solution(n):
    tmp = ''
    while n:
        tmp += str(n % 3)
        n = n // 3

    answer = int(tmp, 3)
    return answer

좋은 웹페이지 즐겨찾기