NAIAHD

출처: 프로그래머스 코딩 테스트 연습 문제

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다.

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...

1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한 조건

• 시험은 최대 10,000 문제로 구성되어있습니다.
• 문제의 정답은 1, 2, 3, 4, 5중 하나입니다.
• 가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬해주세요.

입출력 예

answersreturn

입출력 예 설명

입출력 예 #1

• 수포자 1은 모든 문제를 맞혔습니다.
• 수포자 2는 모든 문제를 틀렸습니다.
• 수포자 3은 모든 문제를 틀렸습니다.

따라서 가장 문제를 많이 맞힌 사람은 수포자 1입니다.

입출력 예 #2

• 모든 사람이 2문제씩을 맞췄습니다.

문제를 보고 좀 고민하게 되었다. 

힌트는 아래의 것이다. 

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 

def solution(answers):
    answer = []
    students = [[1, 2, 3, 4, 5],[2, 1, 2, 3, 2, 4, 2, 5],[3, 3, 1, 1, 2, 2, 4, 4, 5, 5]]
    scores = [0 for i in range(0,3)] 

    for i in range(len(answers)):
        for j,val in enumerate(students):
            if answers[i] == val[i%len(val)]:
                scores[j] += 1
    answer = [i+1 for i in  range(3) if scores[i] == max(scores)]
    return answer

answers= [1,3,2,4,2]
solution(answers)

출처: 프로그래머스 코딩 테스트 연습 문제

문제 설명

자연수 n이 매개변수로 주어집니다. n을 x로 나눈 나머지가 1이 되도록 하는 가장 작은 자연수 x를 return 하도록 solution 함수를 완성해주세요. 답이 항상 존재함은 증명될 수 있습니다.

제한사항

• 3 ≤ n ≤ 1,000,000

입출력 예

nresult

입출력 예 설명

입출력 예 #1

• 10을 3으로 나눈 나머지가 1이고, 3보다 작은 자연수 중에서 문제의 조건을 만족하는 수가 없으므로, 3을 return 해야 합니다.

입출력 예 #2

• 12를 11로 나눈 나머지가 1이고, 11보다 작은 자연수 중에서 문제의 조건을 만족하는 수가 없으므로, 11을 return 해야 합니다.

def solution(n):
    answer = min([i for i in range(1,n) if n %i ==1])
    return answer

n = 12
solution(n)

출처: 프로그래머스 코딩 테스트 연습 문제

점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.

전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.

제한사항

• 전체 학생의 수는 2명 이상 30명 이하입니다.
• 체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
• 여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
• 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.

입출력 예

nlostreservereturn

입출력 예 설명

예제 #1
1번 학생이 2번 학생에게 체육복을 빌려주고, 3번 학생이나 5번 학생이 4번 학생에게 체육복을 빌려주면 학생 5명이 체육수업을 들을 수 있습니다.

예제 #2
3번 학생이 2번 학생이나 4번 학생에게 체육복을 빌려주면 학생 4명이 체육수업을 들을 수 있습니다.

출처

※ 공지 - 2019년 2월 18일 지문이 리뉴얼되었습니다.
※ 공지 - 2019년 2월 27일, 28일 테스트케이스가 추가되었습니다.
※ 공지 - 2021년 7월 28일 테스트케이스가 추가되었습니다.
※ 공지 - 2021년 8월 30일 테스트케이스가 추가되었습니다.

힌트 : 

1. 정렬

2. 같은 것 제거

3. 한번만 빌려줄 수 있기 

아래는 풀이 과정이다. 틀린 부분 까지 포함

def solution(n, lost, reserve):
    answer = n - len(lost)
    for i in range(len(lost)):
        _list = list(set([abs(i-j) for j in range(len(reserve))]))
        if 1 in _list:
            answer += 1

    return answer

n = 5
lost = [2, 4]
reserve = [1,3,5]
solution(n, lost, reserve)

일단 실패를 하였다.

def solution(n, lost, reserve):
    lost = sorted(lost)
    reserve = sorted(reserve)
    reserve1= reserve[:]
    lost1 = lost[:]
    for i in lost:
        for j in reserve:
            if i == j:
                reserve1.remove(j)
                lost1.remove(i)

    answer = n - len(lost1)
    for i in range(len(lost1)):
        _list = list(set([abs(i-j) for j in range(len(reserve1))]))
        if 1 in _list:
            answer += 1

    return answer

채점을 시작합니다.

정확성 테스트

채점 결과

정확성: 70.0

합계: 70.0 / 100.0

또 수정해봤습니다 .

def solution(n, lost, reserve):
    lost.sort()
    reserve.sort()

    reserve1= reserve[:]
    lost1 = lost[:]

    for i in lost:
        for j in reserve:
            if i == j:
                reserve1.remove(j)
                lost1.remove(i)

    answer = n - len(lost1)
    for i in lost1:
        _list = list(set([abs(i-j) for j in reserve1]))
        if 1 in _list:
            answer += 1
            if i+1 in reserve1:
                reserve1.remove(i+1)
            if i-1 in reserve1:
                reserve1.remove(i-1)

    return answer

채점 결과

정확성: 80.0

합계: 80.0 / 100.0

또 털렸죠 ㅠㅠ 17,18,19,20 이 틀리는 것이 바꿔졌습니다. 

def solution(n, lost, reserve):
    lost.sort()
    reserve.sort()

    reserve1= reserve[:]
    lost1 = lost[:]

    for i in lost:
        for j in reserve:
            if i == j:
                reserve1.remove(j)
                lost1.remove(i)

    answer = n - len(lost1)
    for i in lost1:
        _list = list(set([abs(i-j) for j in reserve1]))
        if 1 in _list:
            answer += 1
            isCon = False
            if (i-1 in reserve1) :
                reserve1.remove(i-1)
                isCon = True 
            if (i+1 in reserve1) and not isCon:
                reserve1.remove(i+1)

    return answer

n = 5
lost =  [3, 5]
reserve = [2, 4]
solution(n, lost, reserve)

우여곡절 후에 드디어 풀었습니다. 

17,18,19,20 한번 대여한 것은 빌려 줄 수 없다. 

그래서 remove하였더니 정답 성공하였습니다. 

출처: 프로그래머스 코딩 테스트 연습 문제

당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다.
홍 박사님 연구실의 폰켓몬은 종류에 따라 번호를 붙여 구분합니다. 따라서 같은 종류의 폰켓몬은 같은 번호를 가지고 있습니다. 예를 들어 연구실에 총 4마리의 폰켓몬이 있고, 각 폰켓몬의 종류 번호가 [3번, 1번, 2번, 3번]이라면 이는 3번 폰켓몬 두 마리, 1번 폰켓몬 한 마리, 2번 폰켓몬 한 마리가 있음을 나타냅니다. 이때, 4마리의 폰켓몬 중 2마리를 고르는 방법은 다음과 같이 6가지가 있습니다.

1. 첫 번째(3번), 두 번째(1번) 폰켓몬을 선택
2. 첫 번째(3번), 세 번째(2번) 폰켓몬을 선택
3. 첫 번째(3번), 네 번째(3번) 폰켓몬을 선택
4. 두 번째(1번), 세 번째(2번) 폰켓몬을 선택
5. 두 번째(1번), 네 번째(3번) 폰켓몬을 선택
6. 세 번째(2번), 네 번째(3번) 폰켓몬을 선택

이때, 첫 번째(3번) 폰켓몬과 네 번째(3번) 폰켓몬을 선택하는 방법은 한 종류(3번 폰켓몬 두 마리)의 폰켓몬만 가질 수 있지만, 다른 방법들은 모두 두 종류의 폰켓몬을 가질 수 있습니다. 따라서 위 예시에서 가질 수 있는 폰켓몬 종류 수의 최댓값은 2가 됩니다.
당신은 최대한 다양한 종류의 폰켓몬을 가지길 원하기 때문에, 최대한 많은 종류의 폰켓몬을 포함해서 N/2마리를 선택하려 합니다. N마리 폰켓몬의 종류 번호가 담긴 배열 nums가 매개변수로 주어질 때, N/2마리의 폰켓몬을 선택하는 방법 중, 가장 많은 종류의 폰켓몬을 선택하는 방법을 찾아, 그때의 폰켓몬 종류 번호의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums는 폰켓몬의 종류 번호가 담긴 1차원 배열입니다.
• nums의 길이(N)는 1 이상 10,000 이하의 자연수이며, 항상 짝수로 주어집니다.
• 폰켓몬의 종류 번호는 1 이상 200,000 이하의 자연수로 나타냅니다.
• 가장 많은 종류의 폰켓몬을 선택하는 방법이 여러 가지인 경우에도, 선택할 수 있는 폰켓몬 종류 개수의 최댓값 하나만 return 하면 됩니다.

입출력 예

numsresult

입출력 예 설명

입출력 예 #1
문제의 예시와 같습니다.

입출력 예 #2
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리, 2번 폰켓몬 한 마리, 4번 폰켓몬 한 마리를 고르면 되며, 따라서 3을 return 합니다.

입출력 예 #3
6마리의 폰켓몬이 있으므로, 3마리의 폰켓몬을 골라야 합니다.
가장 많은 종류의 폰켓몬을 고르기 위해서는 3번 폰켓몬 한 마리와 2번 폰켓몬 두 마리를 고르거나, 혹은 3번 폰켓몬 두 마리와 2번 폰켓몬 한 마리를 고르면 됩니다. 따라서 최대 고를 수 있는 폰켓몬 종류의 수는 2입니다.

1. [3,1,2,3] 길이에서 2를 나눈 것이 몇 마리의 폰켓몬을 고를 수 있는지 알 수 있다.

2. set를 해서 중복 된 것을 삭제하고 

2. 길이를 비교한다. 

def solution(nums):
    answer = 0
    nums_1 = len(nums) // 2
    set_nums = len(list(set(nums)))
    answer = nums_1 if nums_1 <= set_nums  else set_nums
    return answer

nums= [3,3,3,2,2,4]
solution(nums)

다른 사람 풀이 확인 하니깐

min이 있었다. 

min 이런 것을 많이 사용해야 겠다.

출처: 프로그래머스 코딩 테스트 연습 문제

문제 설명

실패율

슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다.

이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직은 쉽게 구현했지만, 실패율을 구하는 부분에서 위기에 빠지고 말았다. 오렐리를 위해 실패율을 구하는 코드를 완성하라.

• 실패율은 다음과 같이 정의한다.
  • 스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수

전체 스테이지의 개수 N, 게임을 이용하는 사용자가 현재 멈춰있는 스테이지의 번호가 담긴 배열 stages가 매개변수로 주어질 때, 실패율이 높은 스테이지부터 내림차순으로 스테이지의 번호가 담겨있는 배열을 return 하도록 solution 함수를 완성하라.

제한사항

• 스테이지의 개수 N은 1 이상 500 이하의 자연수이다.
• stages의 길이는 1 이상 200,000 이하이다.
• stages에는 1 이상 N + 1 이하의 자연수가 담겨있다.
  • 각 자연수는 사용자가 현재 도전 중인 스테이지의 번호를 나타낸다.
  • 단, N + 1 은 마지막 스테이지(N 번째 스테이지) 까지 클리어 한 사용자를 나타낸다.
• 만약 실패율이 같은 스테이지가 있다면 작은 번호의 스테이지가 먼저 오도록 하면 된다.
• 스테이지에 도달한 유저가 없는 경우 해당 스테이지의 실패율은 0 으로 정의한다.

입출력 예

Nstagesresult

입출력 예 설명

입출력 예 #1
1번 스테이지에는 총 8명의 사용자가 도전했으며, 이 중 1명의 사용자가 아직 클리어하지 못했다. 따라서 1번 스테이지의 실패율은 다음과 같다.

• 1 번 스테이지 실패율 : 1/8

2번 스테이지에는 총 7명의 사용자가 도전했으며, 이 중 3명의 사용자가 아직 클리어하지 못했다. 따라서 2번 스테이지의 실패율은 다음과 같다.

• 2 번 스테이지 실패율 : 3/7

마찬가지로 나머지 스테이지의 실패율은 다음과 같다.

• 3 번 스테이지 실패율 : 2/4
• 4번 스테이지 실패율 : 1/2
• 5번 스테이지 실패율 : 0/1

각 스테이지의 번호를 실패율의 내림차순으로 정렬하면 다음과 같다.

• [3,4,2,1,5]

입출력 예 #2

모든 사용자가 마지막 스테이지에 있으므로 4번 스테이지의 실패율은 1이며 나머지 스테이지의 실패율은 0이다.

• [4,1,2,3]

해결방법:

1. 스테이지를 list에 저장한다.
2. 스테이지에 있는 list를 stages에서 count로 계산한다.

처음에는 이렇게 해봤다. 

def solution(N, stages):
    answer = []
    my_list = [i for i in range(1,N+1)]
    for i in my_list:
        cnt_1 = 0
        cnt = len(stages)
        for j in stages:
            if i == j :
                cnt_1 += 1
        while i in stages:    
	        stages.remove(i)      
        answer.append((cnt_1/cnt,i))
    answer.sort(key = lambda x:(x[0]), reverse = True)
    return [x[1] for x in answer ]

결과는 :

수정했더니 

def solution(N, stages):
    answer = []
    my_list = [i for i in range(1,N+1)]
    for i in my_list:
        cnt_1 = 0
        cnt = len(stages)
        for j in stages:
            if i == j :
                cnt_1 += 1
        while i in stages:    
	        stages.remove(i)      
        answer.append((0 if cnt == 0 else cnt_1/cnt,i))
    answer.sort(key = lambda x:(x[0]), reverse = True)
    return [x[1] for x in answer ]

def solution(N, stages):
    answer = {}
    my_list = [i for i in range(1,N+1)]
    cnt = len(stages)
    for i in my_list:
        cnt_1 = stages.count(i)
        if cnt == 0:
            answer[i] = 0
        else:
            answer[i]= cnt_1 /cnt
        cnt -= cnt_1 
    
    return sorted(answer, key = (lambda x:-answer[x]))

시간 초과가 나올 경우에는 최대한 for 문 등을 없어야 한다. 

출처: 프로그래머스 코딩 테스트 연습 문제

문제 설명

S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다.

물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 1,000원을 신청한 부서에는 정확히 1,000원을 지원해야 하며, 1,000원보다 적은 금액을 지원해 줄 수는 없습니다.

부서별로 신청한 금액이 들어있는 배열 d와 예산 budget이 매개변수로 주어질 때, 최대 몇 개의 부서에 물품을 지원할 수 있는지 return 하도록 solution 함수를 완성해주세요.

제한사항

• d는 부서별로 신청한 금액이 들어있는 배열이며, 길이(전체 부서의 개수)는 1 이상 100 이하입니다.
• d의 각 원소는 부서별로 신청한 금액을 나타내며, 부서별 신청 금액은 1 이상 100,000 이하의 자연수입니다.
• budget은 예산을 나타내며, 1 이상 10,000,000 이하의 자연수입니다.

입출력 예

dbudgetresult

입출력 예 설명

입출력 예 #1
각 부서에서 [1원, 3원, 2원, 5원, 4원]만큼의 금액을 신청했습니다. 만약에, 1원, 2원, 4원을 신청한 부서의 물품을 구매해주면 예산 9원에서 7원이 소비되어 2원이 남습니다. 항상 정확히 신청한 금액만큼 지원해 줘야 하므로 남은 2원으로 나머지 부서를 지원해 주지 않습니다. 위 방법 외에 3개 부서를 지원해 줄 방법들은 다음과 같습니다.

• 1원, 2원, 3원을 신청한 부서의 물품을 구매해주려면 6원이 필요합니다.
• 1원, 2원, 5원을 신청한 부서의 물품을 구매해주려면 8원이 필요합니다.
• 1원, 3원, 4원을 신청한 부서의 물품을 구매해주려면 8원이 필요합니다.
• 1원, 3원, 5원을 신청한 부서의 물품을 구매해주려면 9원이 필요합니다.

3개 부서보다 더 많은 부서의 물품을 구매해 줄 수는 없으므로 최대 3개 부서의 물품을 구매해 줄 수 있습니다.

입출력 예 #2
모든 부서의 물품을 구매해주면 10원이 됩니다. 따라서 최대 4개 부서의 물품을 구매해 줄 수 있습니다.

1. sort한다.

2. 각 부서와 전의 부서의 합을 다 더하여 list를 넣었다.

3. list를 순회하면서 합이 클 경우 idx를 그냥 리턴하고 , 작거나 같을 경우 idx를 return 하였다. 

def solution(d, budget):
    answer = 0
    d.sort()
    sum_list= []
    sum_= 0
    for idx,val in enumerate(d):
        sum_ += val
        sum_list.append(sum_)
  
    for idx, val in enumerate(sum_list):
        if val > budget:
            answer = idx
            break
        else:
            answer = idx+1
    return answer

하지만 .... 

다른 사람의 풀이를 확인 해본 결과 :

훨씬 짧고 간결하게 작성하였네요 ㅠ

def solution(d, budget):
    d.sort()
    while budget < sum(d):
        d.pop()
    return len(d)

sum -> 시작 복잡도가 O(n^2)가 되네요 .. 

출처: 프로그래머스 코딩 테스트 연습 문제

문제 설명

두 정수 left와 right가 매개변수로 주어집니다. left부터 right까지의 모든 수들 중에서, 약수의 개수가 짝수인 수는 더하고, 약수의 개수가 홀수인 수는 뺀 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ left ≤ right ≤ 1,000

입출력 예

leftrightresult

입출력 예 설명

입출력 예 #1

• 다음 표는 13부터 17까지의 수들의 약수를 모두 나타낸 것입니다.

수약수약수의 개수

• 따라서, 13 + 14 + 15 - 16 + 17 = 43을 return 해야 합니다.

입출력 예 #2

• 다음 표는 24부터 27까지의 수들의 약수를 모두 나타낸 것입니다.

수약수약수의 개수

• 따라서, 24 - 25 + 26 + 27 = 52를 return 해야 합니다.

def solution(left, right):
    answer = 0
    dict_ ={}

    for i in range(left, right+1):
        _list2 = []
        for j in range(1, i):
            if i % j == 0:
                _list2.append(j)
        dict_[i] = _list2
    for key, value in dict_.items():
        answer += (key* -1 if len(value) % 2 == 0 else key)
    return answer

다른 사람 풀이를 확인 하였는데 

int(i**0.5)==i**0.5 

이 방법이 소수 , 약수에서 많이 쓰이는 것 같다.

출처: 프로그래머스 코딩 테스트 연습 문제

문제 설명

자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• n은 1 이상 100,000,000 이하인 자연수입니다.

입출력 예 설명

입출력 예 #1

• 답을 도출하는 과정은 다음과 같습니다.

n (10진법)n (3진법)앞뒤 반전(3진법)10진법으로 표현

• 따라서 7을 return 해야 합니다.

입출력 예 #2

• 답을 도출하는 과정은 다음과 같습니다.

n (10진법)n (3진법)앞뒤 반전(3진법)10진법으로 표현

• 따라서 229를 return 해야 합니다.

def solution(n):
    answer= ''
    while n>0:
        n, mod = divmod(n, 3)
        answer+= str(mod)
    return int(answer,3)
n = 45
solution(n)

****int(answer,3)

다른 진수의 문자열 -> 숫자형으로 변환하기