[프로그래머스] 완전탐색 1. 모의고사

문제

출처: 프로그래머스

---

풀이

이건 전체 탐색을 진행할 수 밖에 없는 문제였다. 애초에 카테고리가 완전탐색임

c++으로는 예전에 풀어놨길래 이번엔 python으로 풀어봤다. 전체적인 알고리즘은 동일하다.

answers을 반복문으로 1회 돌며 주어진 패턴과 비교한다. 정답수를 저장하고 오름차순으로 배열에 넣어 반환한다.

 

c++

#include <string>
#include <vector>
#include <iostream>

using namespace std;

vector<int> solution(vector<int> answers) {
    vector<int> winners;
    vector<int> correct{0, 0, 0};
    int arrayFor2[4] = {1, 3, 4, 5};
    int arrayFor3[5] = {3, 1, 2, 4, 5};
    
    for (int i = 0; i < answers.size(); i++) {
        if (answers[i] == (i) % 5 + 1) {
           correct[0] ++;
        }
        
        if ((i % 2 == 0) && answers[i] == 2) {
           correct[1] ++;
        }
        if ((i % 2 == 1) && arrayFor2[(i / 2) % 4] == answers[i]) {
           correct[1] ++;
        }
        
        if (answers[i] == arrayFor3[(i % 10) / 2]) {
           correct[2] ++;
        }
    }
    
    int max = 0;
    for (int i = 0; i < 3; i++) {
        if (max == correct[i]) {
            winners.push_back(i + 1);
        }
        if (max < correct[i]) {
            winners.clear();
            max = correct[i];
            winners.push_back(i + 1);
        }
    }
    
    return winners;
}

 

python3

def solution(answers):
    first = [1,2,3,4,5]
    second = [2,1,2,3,2,4,2,5]
    third = [3,3,1,1,2,2,4,4,5,5]
    
    answer = {1: 0, 2: 0, 3: 0}
    for index, value in enumerate(answers):
        answer[1] += 1 if first[index%len(first)] == value else 0
        answer[2] += 1 if second[index%len(second)] == value else 0
        answer[3] += 1 if third[index%len(third)] == value else 0

    max = 0
    winners = []
    for key, value in answer.items():
        if value > max:
            max = value
            winners.clear()
            winners.append(key)
        elif value == max:
            winners.append(key)

    return winners

---

시간, 공간 사용

좌: c++, 우: python

이번건 파이썬이 훨씬 느리게 나왔다. c++버전과 달리 len()을 반복문 안에서 매번 호출한 것 때문이라는 생각이 들어 숫자로 변경해봤다.

python 수정 후

조금 나아졌지만 거기서 거기다. 그냥 언어별로 어느 정도 차이가 있는듯