프로그래머스 문제 풀이 모의고사
문제 URL 모의고사
Contents
- 문제 지문 파악하기
- 구르미의 알고리즘 풀이
문제 지문 파악하기
먼저, 문제를 파악해봅시다. 3명의 수포자는 다음 패턴으로 문제를 찍습니다.
// 각 패턴은 다음 배열의 반복입니다.
1번 학생 = [1, 2, 3, 4, 5]
2번 학생 = [2, 1, 2, 3, 2, 4, 2, 5]
3번 학생 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
첫 번째 입력을 살펴봅시다.
입력:
answers = [1, 2, 3, 4, 5]
이 경우, 1번 학생은 5문제 다 맞히게 됩니다.
answers = [1, 2, 3, 4, 5]
1번 학생 = [1, 2, 3, 4, 5]
score = 5 //각 인덱스의 원소가 모두 같다.
2번 학생은 0개를 맞춥니다.
answers = [1, 2, 3, 4, 5]
2번 학생 = [2, 1, 2, 3, 2] // 4, 2, 5]
score = 0
3번 학생은 0개를 맞춥니다.
answers = [1, 2, 3, 4, 5]
3번 학생 = [3, 3, 1, 1, 2] // 2, 4, 4, 5, 5]
score = 0
즉 3명의 학생 중 1번 학생이 5문제로, 제일 많이 맞추게 됩니다. 답은 다음과 같습니다.
answer = [1]
이번엔 다음 입력이 있다고 합시다.
입력:
answers = [1, 3, 2, 4, 2, 2, 4, 3, 2, 1]
이제 1, 2, 3번 학생 패턴대로 했을 때, 각 점수를 파악해봅시다.
answers = [1, 3, 2, 4, 2, 2, 4, 3, 2, 1]
1번 학생 = [1, 2, 3, 4, 5, 1, 2, 3, 4, 5] //부족한 길이만큼 반복
score = 3
answers = [1, 3, 2, 4, 2, 2, 4, 3, 2, 1]
2번 학생 = [2, 1, 2, 3, 2, 4, 2, 5, 2, 1] //, 2, 3, 2, 4, 2, 5 ] 부족한 길이만큼 반복
score = 4
answers = [1, 3, 2, 4, 2, 2, 4, 3, 2, 1]
3번 학생 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
score = 4
이제 최대로 맞힌 점수는 4이며, 2번 3번 학생이 이 점수를 얻었습니다. 따라서 답은 이렇게 됩니다.
answer = [2, 3]
어떻게 프로그래밍적으로 풀 수 있을까요? 첫 번째 입력이 들어왔다고 가정하고, 문제를 풀어봅시다. 우리는 먼저 각 학생들의 pattern을 저장하는 2차원 배열을 만들어줍니다.
answers = [1, 2, 3, 4, 5]
patterns = [
[1, 2, 3, 4, 5], //1번 학생 패턴
[2, 1, 2, 3, 2, 4, 2, 5], //2번 학생 패턴
[3, 3, 1, 1, 2, 2, 4, 4, 5, 5] //3번 학생 패턴
]
이제 각 학생들의 점수를 저장하는 배열 scores를 생성해둡니다.
answers = [1, 2, 3, 4, 5]
patterns = [
[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, 0, 0]
이제 answers를 0부터 answer의 길이까지 다음과 같이 순회합니다.
i = 0
answers[i] = 1
patterns[0][i] = 1
scores[0] = 1
patterns[1][i] = 2
scores[1] = 0
patterns[2][i] = 3
scores[2] = 0
이 때, patterns 역시, j에 대해서 0부터 3까지 순회하는 것이죠.
i = 0 answers[i] = 1
j = 0 patterns[j][i] = 1 scores[j] = 1
j = 1 patterns[j][i] = 2 scores[j] = 0
j = 2 patterns[j][i] = 3 scores[j] = 0
i = 1
answers[i] = 2
j = 0 patterns[j][i] = 2 scores[j] = 2
j = 1 patterns[j][i] = 1 scores[j] = 0
j = 2 patterns[j][i] = 3 scores[j] = 0
i = 2
answers[i] = 3
j = 0 patterns[j][i] = 3 scores[j] = 3
j = 1 patterns[j][i] = 2 scores[j] = 0
j = 2 patterns[j][i] = 1 scores[j] = 0
i = 3
answers[i] = 4
j = 0 patterns[j][i] = 4 scores[j] = 4
j = 1 patterns[j][i] = 3 scores[j] = 0
j = 2 patterns[j][i] = 1 scores[j] = 0
i = 4
answers[i] = 5
j = 0 patterns[j][i] = 5 scores[j] = 5
j = 1 patterns[j][i] = 2 scores[j] = 0
j = 2 patterns[j][i] = 2 scores[j] = 0
그래서 scores는 다음과 같이 저장됩니다.
scores = [5, 0, 0]
여기서, 최대 점수를 구합니다.
scores = [5, 0, 0]
max_score = 5
이제 scores를 0부터 scores의 길이까지 순회하면서, 최대 점수가 같으면, 해당 인덱스+1을 answer에 저장하면 됩니다. 즉 답은 다음과 같아집니다.
answer = [1]
여기서 중요한 것은, 각 패턴은, answers의 길이보다 작을 수 있습니다. 반복해서 순회하기 위해서, patterns를 접근할 때 다음 수식을 쓰세요.
if answers[i] == patterns[j][i % len(patterns[j])]:
pass
나머지 연산으로, i가 각 패턴의 길이를 넘어가더라도, 다시, 0부터 시작하게 되는 것이죠. 이렇게 하면, 이 문제를 풀 수 있습니다.
구르미의 알고리즘 풀이
"문제 지문 파악하기"를 토대로 세운 알고리즘을 순서대로 나열하면 다음과 같습니다.
- 각 패턴을 만듭니다.
- 3명에 대한 스코어 배열을 만듭니다.
- i를 0부터 answers의 길이까지 순회합니다.
- j를 0부터 patterns를 길이까지 순회합니다.
- answer[i]와 patters[j][i% len(patterns[j])]와 같으면, scores[j] 1 올려줍니다.
- j를 0부터 patterns를 길이까지 순회합니다.
- scores에서 최고점을 구합니다.
- 최고점과 같은 점수를 받은 학생 번호(i+1)를 answer에 서장합니다.
이를 코드로 표현하면 다음과 같습니다. 다음은 PYTHON 코드입니다.
PYTHON 코드
def solution(answers):
# 1. 각 패턴을 만듭니다.
patterns = [
[1, 2, 3, 4, 5],
[2, 1, 2, 3, 2, 4, 2, 5],
[3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
]
# 2. 3명에 대한 스코어 배열을 만듭니다.
scores = [0] * 3
# 3. i를 0부터 answers의 길이까지 순회합니다.
# 3-1. j를 0부터 patterns를 길이까지 순회합니다.
# 3-1-1. answer[i]와 patters[j][i% len(patterns[j])]와 같으면, scores[j] 1 올려줍니다.
for i in range(len(answers)):
for j, pattern in enumerate(patterns):
if answers[i] == pattern[i % len(pattern)]:
scores[j] += 1
# 4. scores에서 최고점을 구합니다.
max_score = max(scores)
# 5. 최고점과 같은 점수를 받은 학생 번호를 answer에 서장합니다.
answer = [ i + 1 for (i, x) in enumerate(scores) if x == max_score ]
return answer
이번엔 CPP 코드입니다. 알고리즘은 동일하고, 언어만 바뀐 것입니다.
CPP 코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> solution(vector<int> answers) {
vector< vector<int>> patterns = {
{1,2,3,4,5},
{2,1,2,3,2,4,2,5},
{3,3,1,1,2,2,4,4,5,5}
};
vector<int> scores = { 0, 0, 0 };
for(int i=0; i<answers.size(); i++) {
int idx = 0;
for (const auto & pattern : patterns) {
if (answers[i] == pattern[i % pattern.size()]) {
scores[idx] += 1;
}
idx += 1;
}
}
vector<int> answer;
const auto & max_socre = *max_element(scores.begin(), scores.end());
for(int i = 0; i<3; i++) {
if(scores[i] == max_socre) {
answer.push_back(i+1);
}
}
return answer;
}
또한, 파이썬의 경우, zip()를 이용하면, 다음과 같이 코드를 짤 수 있습니다. 파이썬 짱짱...
PYTHON 코드
def solution(answers):
n = len(answers)
patterns = [
([1, 2, 3, 4, 5]*n)[:n],
([2, 1, 2, 3, 2, 4, 2, 5]*n)[:n],
([3, 3, 1, 1, 2, 2, 4, 4, 5, 5]*n)[:n]
]
results = [ len([ x for (x, y) in zip(pattern, answers) if x == y ]) for pattern in patterns ]
answer = [idx + 1 for (idx, x) in enumerate(results) if x == max(results)]
return answer
이 코드에서 중요한 것은 각 pattern을 answers 길이를 맞춰주는데 있습니다. 어떻게 이 코드가 동작하는지 한 번 스스로 생각해보세요.