[programmers] 프로그래머스 모의고사(C++)

(주)그렙

[programmers] 프로그래머스 모의고사

(C++)

(글쓴날 : 2020.06.06)

 

---

* programmers, 프로그래머스 문제 C++ 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 모의고사

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42840

코딩테스트 연습 - 모의고사

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

특정 주기를 반복하는 수열이 3개 주어질 때, 답으로 주어지는 수열과 비교하여 가장 일치하는 수열을 구하는 문제입니다.

일치하는 수열이 여러 개일 경우 수열의 번호를 오름차순으로 반환해야 합니다.

 

저의 경우, C++을 사용했습니다.

3개의 수열에서 반복되는 일정 주기를 찾아 각각 vector에 초기화해놓은 뒤, 답으로 주어지는 수열과 비교하였습니다.

이 문제의 핵심은 반복되는 주기가 각 수열마다 다르다는 것인데, % 모듈러 연산을 통해 각 수열마다 달라지는 인덱스를 구하여 문제를 해결했습니다.

---

3) 코드

 

* C++ 코드

#include <string>
#include <vector>
#include <algorithm>
#include <utility>
 
using namespace std;
 
vector<int> solution(vector<int> answers)
{
    vector<int> answer;
 
    vector<vector<int>> person{
        {1, 2, 3, 4, 5},
        {2, 1, 2, 3, 2, 4, 2, 5},
        {3, 3, 1, 1, 2, 2, 4, 4, 5, 5}};
 
    int p1 = 0, p2 = 0, p3 = 0;
    pair<int, int> score[3] = {{0, 1}, {0, 2}, {0, 3}};
    for (int i = 0; i < answers.size(); i++)
    {
        p1 = i % 5;
        p2 = i % 8;
        p3 = i % 10;
 
        if (answers[i] == person[0][p1])
            score[0].first++;
        if (answers[i] == person[1][p2])
            score[1].first++;
        if (answers[i] == person[2][p3])
            score[2].first++;
    }
 
    sort(score, score + 3, greater<pair<int, int>>());
 
    for (int i = 0; i < 3; i++)
    {
        if (!i)
        {
            answer.push_back(score[0].second);
            continue;
        }
        if (score[i].first == score[i - 1].first)
            answer.push_back(score[i].second);
        else
            break;
    }
 
    sort(answer.begin(), answer.end());
 
    return answer;
}

---