완전탐색_Lv1_모의고사

Eugenius1st·2022년 8월 3일

Programmers_Python

목록 보기

20/32

BruteForce

영어로 brute는 "짐승 같은, 난폭한"이라는 뜻이고, brute-force는 "난폭한 힘, 폭력"이라는 뜻이다. 오래 걸리는 데다 자원이 엄청나게 들어서 얼핏 보면 무식하다고 생각할 수도 있겠지만, 항상 정확도 100%를 보장한다는 점에서 암호 해독법 중 가장 확실하고 무서운 방법이다.

브루트 포스(brute force), 키 전수조사(exhaustive key search) 또는 무차별 대입(無差別代入)은 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 흔히 암호학에서 연구되나, 다른 알고리즘 분야에서도 사용되고 있다.

문제

문제 설명
수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 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하는 값을 오름차순 정렬해주세요.

풀이

answers 배열과 바보1, 바보2, 바보3 배열값 일일히 대조
바보들은 idx가 반복되므로, for문에서 idx의 전체 길이로 나눈 나머지를 활용하여 계속 배열값을 확인한다.
시간초과 잡기가 힘들었다.

코드

시간초과

def solution(answers):
    # 문제를 가장 많이 맞춘 사람이 누구인지! 
    # answer배열에 담아  return
    answer = []
    babo1 = [1,2,3,4,5] 
    babo2 = [2,1,2,3,2,4,2,5]
    babo3 = [3,3,1,1,2,2,4,4,5,5] 

    babo1Len = len(babo1); #.length
    babo2Len = len(babo2);
    babo3Len = len(babo3);

    babo1Score = 0;
    babo2Score = 0;
    babo3Score = 0;

    for i in range(len(answers)):
        # 바보들이 답을 맞혔는지 확인
        if answers[i] == babo1[i%babo1Len]:
            babo1Score += 1
        if answers[i] == babo2[i%babo2Len]:
            babo2Score += 1
        if answers[i] == babo3[i%babo3Len]:
            babo3Score += 1
    print(babo1Score,babo2Score,babo3Score)
    
    # 가장 많이 맞춘 바보를 answer에 추가, 만약 중복있다면 sort
    maxScore = max(babo1Score,babo2Score,babo3Score);
    if maxScore == babo1Score:
        answer.append(1)
    if maxScore == babo2Score:
        answer.append(2)
    if maxScore == babo2Score:
        answer.append(3)
    answer = sorted(answer)
    return answer

정답코드

def solution(answers):
    # 문제를 가장 많이 맞춘 사람이 누구인지! 
    # answer배열에 담아  return
    answer = []
    babo1 = [1,2,3,4,5] 
    babo2 = [2,1,2,3,2,4,2,5]
    babo3 = [3,3,1,1,2,2,4,4,5,5] 

    babo1Len = len(babo1); #.length
    babo2Len = len(babo2);
    babo3Len = len(babo3);

    babo1Score = 0;
    babo2Score = 0;
    babo3Score = 0;

    for i in range(len(answers)):
        # 바보들이 답을 맞혔는지 확인
        if answers[i] == babo1[i%babo1Len]:
            babo1Score += 1
        if answers[i] == babo2[i%babo2Len]:
            babo2Score += 1
        if answers[i] == babo3[i%babo3Len]:
            babo3Score += 1
    rank = [babo1Score,babo2Score,babo3Score]
    
    # 가장 많이 맞춘 바보를 answer에 추가, 만약 중복있다면 sort
    temp = max(rank)                  # 같은 갯수의 문제를 맞췄으면 함께 출력
    for i in range(len(rank)):
        if rank[i] == temp:
            answer.append(i+1)
    return answer