본문 바로가기

별걸다하는 IT/알고리즘 문제풀이

[프로그래머스 코딩테스트 연습 Level 1] 모의고사 문제 풀이(C++, JAVA) 다양한 해설

[프로그래머스 Level 1]

모의고사 

문제

수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다.

수포자는 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 return
[1,2,3,4,5] [1]
[1,3,2,4,2] [1,2,3]

 

기본 제공 틀

[C++]

#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> answers) {
    vector<int> answer;
    return answer;
}

[Java]

class Solution {
    public int[] solution(int[] answers) {
        int[] answer = {};
        return answer;
    }
}

 

ANSWER!!

[첫번째 방법]

1. [학생찍는 방법 정의하기]

일단 수포자의 찍는 방식은 고정이네요. 수포사의 찍는 방식을 보면 규칙이 있어요.

vector<int> stu1 = {1,2,3,4,5};
vector<int> stu2 = {2,1,2,3,2,4,2,5};
vector<int> stu3 = {3,3,1,1,2,2,4,4,5,5};

전역변수에 선언해줘도 되고, solution 함수 내부에 선언해줘도 상관 없습니다.

solution이 채점하는 방식(?)에 관한거라면 아무래도 전역에다가 정의해주는게 좋겠죠.

 

2. [총 문제 개수 알기]

이제 반복문으로 1번문제부터 마지막문제까지 학생들별로 하나하나채점을 해주면 되겠죠.

문제는 인자로 주어졌는데, 몇문제인지 알수 없으므로 answer.size()함수를 이용해 알아낸 후 변수에 저장해줍시다.

//총 문제 개수
int num = answers.size();

 

3. [학생별 점수내기]

이제 학생별 문제를 채점하는 코드를 작성해봅시다.

vector<int> score(3);
for(int i=0; i<num; i++)
{
	if(answers[i] == stu1[i%stu1.size()]) score[0]++;
	if(answers[i] == stu2[i%stu2.size()]) score[1]++;
	if(answers[i] == stu3[i%stu3.size()]) score[2]++;
}

문제의 답과 학생의 답이 같을 때 맞은 개수를 올려줘요. 학생의 답은 반복되기 때문에 모듈연산자를 사용했습니다.

 

4. [가장 큰 점수 알기 - max_element]

여기서 가장 큰 점수가 뭔지만 알면 그 값과 같은 점수를 가지고 있는 학생이 위너겠죠.

vector<int> solution(vector<int> answers) {
	...
	int max = *max_element(score.begin(), score.end());
	vector<int> winner;
	for(int i =0; i<score.size(); i++)
	{
		if(score[i] == max) winner.push_back(i+1);
	}
	...
}

아마 4번에서 사람들마다 풀이가 좀 갈릴듯한대, max_element안쓰고 우리가 자주사용하는 비교문으로 해주신 분도 있을거예요.

 

[가장 큰 점수 알기 - maximum (if를 이용한 사용자정의함수) ]

비교문을 이용해 maximum함수를 정의해줬어요.

int maximum(int a, int b)
{
    return a>b?a:b;
}
vector<int> solution(vector<int> answers) {
	...
	int max = maximum(maximum(score[0],score[1]),score[2]);
	vector<int> winner;
	for(int i=0; i<score.size(); i++)
  	{
  		if(score[i] == max) winner.push_back(i+1);
	}
	...
}

[소스코드 전체 C++]

#include <vector>
#include <string>
#include <algorithm>
using namespace std;
vector<int> stu1{ 1,2,3,4,5 };
vector<int> stu2{2,1,2,3,2,4,2,5};
vector<int> stu3{3,3,1,1,2,2,4,4,5,5};

vector<int> solution(vector<int> answers) {
    vector<int> winner;
	vector<int> score(3);
    int num = answers.size();
    for ( int i=0; i<num; i++)
    {
        if(answers[i]==stu1[i%stu1.size()]) score[0]++;
        if(answers[i]==stu2[i%stu2.size()]) score[1]++;
        if(answers[i]==stu3[i%stu3.size()]) score[2]++;
    }
	int max = *max_element(score.begin(), score.end());
	for(int i=0; i<score.size(); i++)
    {
        if(score[i] == max) winner.push_back(i+1);
    }
    return winner;
}

어렵지 않게 해결되었어요~~

 

[두번째 방법]

위의 경우 최고 숫자를 구한 뒤, 그 숫자와 일치하는 학생들을 뽑아줬잖아요. 그 외에 학생과 점수를 한 쌍으로 묶은 뒤, 학생들을 점수별로 줄세우기 하는거예요. 그럼 쌍으로 묶여 있으니 그 점수에 해당하는 학생이 누군지 알 수 있죠.

 

1번, 2번은 동일~

3. [학생과 점수 쌍짓고 점수 채점하기]

이제 학생별 문제를 채점하는 코드를 작성해봅시다.

vector<pair<int, int>> scores{{0, 1},{0, 2},{0,3}}; //{점수, 학생번호}
for ( int i=0; i<num; i++)
{
 	if(answers[i]==stu1[i%stu1.size()]) scores[0].first++;
 	if(answers[i]==stu2[i%stu2.size()]) scores[1].first++;
 	if(answers[i]==stu3[i%stu3.size()]) scores[2].first++;
}

pair<int,int> STL을 사용해줬습니다. 좀이따 줄세우기 하기 편하게, 처음을 점수, 두번째를 학생번호로 지정했어요.

특정 문제의 답이 맞았다면 점수에 해당하는 first값을 올려줍시다.

 

4. [점수별로 줄세우기 - sort]

sort(scores.begin(), scores.end());
int max = scores[scores.size() -1].first; //오름차순이라 맨 마지막 값이 가장 높은 점수가 됨
int i= scores.size()-1;
do
{
	if(max == scores[i].first) winner.push_back(scores[i].second);
	else break;
}while(i--);
//sort가 오름차순이라 for문을 뒤에서부터 해줘서 winner를 다시 재정렬해줘야함
sort(winner.begin(), winner.end());

 

오름차순 말고 내림차순으로 하고 싶었는데,,, ㅠ greater<int>()가 왠지 모르게 안돼서.. 그냥 오름차순으로... ㅠㅠ

내림차순으로 했으면 winner때 다시 sort할 필요도 없고, for문을 굳이 뒤에서부터 안내려와도 되어서 소스가 훨 간결해졌을텐데 ㅠ 왜 여기선 #include <functional>을 헤더파일에 넣었는데도 불구하고 greater를 인식하지 못할까요..! 

 

아, 어차피 winner는 순서만 바꿔주는거기 때문에 sort대신 reverse를 해줘도 됩니다.

reverse(winner.begin(), winner.end());

 

[소스코드 전체 C++]

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
vector<int> stu1{ 1,2,3,4,5 };
vector<int> stu2{2,1,2,3,2,4,2,5};
vector<int> stu3{3,3,1,1,2,2,4,4,5,5};

vector<int> solution(vector<int> answers) {
    vector<pair<int, int>> scores{{0, 1},{0, 2},{0,3}}; //{점수, 학생번호} 
    vector<int> winner;
    int num = answers.size();
    for ( int i=0; i<num; i++)
    {
        if(answers[i]==stu1[i%stu1.size()]) scores[0].first++;
        if(answers[i]==stu2[i%stu2.size()]) scores[1].first++;
        if(answers[i]==stu3[i%stu3.size()]) scores[2].first++;
    }
    sort(scores.begin(), scores.end());
    int i= scores.size()-1;
    int max = scores[scores.size() -1].first;
    do
    {
        if(max == scores[i].first) winner.push_back(scores[i].second);
        else break;
        
    }while(i--);
    sort(winner.begin(), winner.end());
    return winner;
}

자바의 경우

어차피 vector가 배열이니, 자바에서 ArrayList를 사용해주면 됩니다.

1. [학생찍는 방법 정의하기]

(언어만 다를 뿐 결국 C++ 첫번째 방법이랑 알고리즘은 동일, 일단 C++안읽고 바로 자바로 가신 분들을 위해 복붙)

일단 수포자의 찍는 방식은 고정이네요. 수포사의 찍는 방식을 보면 규칙이 있어요. 

vector<int> stu1 = {1,2,3,4,5};
vector<int> stu2 = {2,1,2,3,2,4,2,5};
vector<int> stu3 = {3,3,1,1,2,2,4,4,5,5};

Solution 클래스 내부에 선언하던, solution 메서드 내부 하던 상관 없습니다.

solution이 채점하는 방식(?)에 관한거라면 아무래도 메서드 내부보단 클래스 멤버변수로 정의해주는게 좋겠죠.

 

2. [학생별 점수내기]

자바의 경우 문제 길이는 배열, length 로 쉽게 알 수 있으니,, 이제 학생별 문제를 채점하는 코드를 작성해봅시다.

for(int i=0; i<answer.length; i++) {
            if(answer[i] == a[i%a.length]) {score[0]++;}
            if(answer[i] == b[i%b.length]) {score[1]++;}
            if(answer[i] == c[i%c.length]) {score[2]++;}
}

3. [가장 큰 점수 알기]

자바 Math클래스는 max기능을 지원합니다.

int maxScore = Math.max(score[0], Math.max(score[1], score[2]));

아님 뭐 단순하게 

int maxScore = score[0];
max = max < score[1]? score[1]: max;
max = max < score[2]? score[2]: max;

 

4. [가장 많은 문제를 맞힌 학생들 고르기]

이제 가장 큰 점수를 알았으니 해당 점수를 가지고 있는 학생들을 찾으면 되겠죠~

ArrayList<Integer> winner = new ArrayList<>();
for(int i=0; i< score.length; i++){
     if(max == score[i]) {winner.add(i+1);}
}

사실 뭐 세개밖에 없으니까 반복문 안쓰고

ArrayList<Integer> list = new ArrayList<>();
if(maxScore == score[0]) {list.add(1);}
if(maxScore == score[1]) {list.add(2);}
if(maxScore == score[2]) {list.add(3);}

이렇게 걍 붙여줘도 돼요. 타입은 ArrayList인데 반환타입은 배열이니 타입변환해주기

 

[소스코드 전체 JAVA]

import java.util.ArrayList;
class Solution {
    int[] a = {1, 2, 3, 4, 5};
    int[] b = {2, 1, 2, 3, 2, 4, 2, 5};
    int[] c = {3, 3, 1, 1, 2, 2, 4, 4, 5, 5};
    public int[] solution(int[] answer) {
        int[] score = new int[3];
        for(int i=0; i<answer.length; i++) {
            if(answer[i] == a[i%a.length]) {score[0]++;}
            if(answer[i] == b[i%b.length]) {score[1]++;}
            if(answer[i] == c[i%c.length]) {score[2]++;}
        }
        int maxScore = Math.max(score[0], Math.max(score[1], score[2]));
        ArrayList<Integer> winner = new ArrayList<>();
        for(int i=0; i< score.length; i++){
            if(max == score[i]) {winner.add(i+1);}
        }
        return winner.stream().mapToInt(i->i.intValue()).toArray();
    }
}

오늘은 여기까지입니다! 모두 수고하셨어요.

도움이 되셨다면 공감/댓글/광고보답 중 하나는 어떤가요?? 정보공유에 큰 기쁨이됩니다 :) 

다음 포스팅에서 봐요.