1. 크레인 인형뽑기 게임,완주하지 못한 선수,모의고사,체육복,3진법 뒤집기,같은 숫자는 싫어,두 정수 사이의 합,문자열 내 p와 y의 개수,문자열 다루기 기본, 소수 찾기_(코테준비 day1)
프로그래머스
아래 모든 문제들은 프로그래머스에서 제공 되는 문제를 이용하였습니다, 감사합니다.
- 체육복 문제 틀림
- 나머지 정답
1. 크레인 인형뽑기 게임
문제
크레인을 작동하면 해당 라인의 가장 상위에 있는 인형이 무조건 뽑히고, (만약 해당 라인에 인형이 하나도 없으면 아무것도 뽑지 않는다)
뽑은 인형은 바구니에 담는다. 이 때 인형이 연속으로 같은 모양 2개 있으면 터져서 사라진다.
터져서 사라진 인형의 갯수를 구해야한다.
[제한사항]
board 배열은 2차원 배열로 크기는 "5 x 5" 이상 "30 x 30" 이하입니다.
board의 각 칸에는 0 이상 100 이하인 정수가 담겨있습니다.
0은 빈 칸을 나타냅니다.
1 ~ 100의 각 숫자는 각기 다른 인형의 모양을 의미하며 같은 숫자는 같은 모양의 인형을 나타냅니다.
moves 배열의 크기는 1 이상 1,000 이하입니다.
moves 배열 각 원소들의 값은 1 이상이며 board 배열의 가로 크기 이하인 자연수입니다.
입출력 예
board moves result
| board | moves | result |
|---|---|---|
| [[0,0,0,0,0],[0,0,1,0,3],[0,2,5,0,1],[4,2,4,4,2],[3,5,1,3,1]] | [1,5,3,5,1,2,1,4] | 4 |
#include
#include
#include
using namespace std;
int solution(vector> board, vector moves) {
vector basket;
int tmp = 0;
int answer = 0;
basket.push_back(0);
for(int i = 0; i < moves.size(); i++)
{
for(int j = 0; j < board.size(); j++)
{
if ((tmp = board[j][moves[i] - 1]) != 0)
{
if(basket.back() == tmp)
{
basket.pop_back();
answer += 2;
}
else
basket.push_back(tmp);
board[j][moves[i] - 1] = 0;
break;
}
}
}
return answer;
}설명
moves의를 통해 열이 주어지면, 해당 열에서 0 이 아닌 값이 나올떄 까지 for문을 돌리고, 만약 0이 아니라면,
해당 위치의 인형을 뽑는다. 그리고 뽑힌 인형을 바구니에 담아야 하는데, 이떄 담기전에, 마지막에 담은 인형이, 넣을려는 인형과 같은인형인지 확인하기 위해,
if(basket.back() == tmp) 확인하고, 같은 인형이면 카운트 해주고 다른 인형이면, 그냥 쌓아준다.
2. 완주하지 못한 선수
문제 설명
수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.
마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.
제한사항
마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.
completion의 길이는 participant의 길이보다 1 작습니다.
참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다.
참가자 중에는 동명이인이 있을 수 있습니다.
컴퓨터는 1억()을 넘어가면 시간 제한을 초과할 가능성이 있다.
풀이
#include
#include
#include
#include
using namespace std;
string solution(vector participant, vector completion) {
string answer = "";
sort(participant.begin(), participant.end());
sort(completion.begin(), completion.end());
int j;
for(j = 0; j < completion.size(); j++)
{
if(completion[j] != participant[j])
return participant[j];
}
return participant[j];
// for(int i = 0; i < participant.size(); i++)
// {
// for(int j = 0; j < completion.size(); j++)
// {
// if (participant[i] == completion[j])
// {
// completion.erase(completion.begin() + j);
// break;
// }
// if (j == (completion.size() - 1))
// {
// answer = participant[i];
// break;
// }
// }
// if(answer != "")
// break;
// }
return answer;
}설명
- 처음 접근할때, 주석 처리한 부분으로 풀어보았다.
- participant배열의 처음부터 끝까지, 완주자 명단에 있는지 확인하며 검사햇는데, 다풀고 나니, 100,000 * 100,000 의 접근 법이라 시간 초과가 발생했다.
- 새로운 접근법 : participant,completion 배열 정렬 후 비교
- 두 배열을 정렬하고, 비교를 하는 방법으로 문제를 풀었다.
3. 모의고사
문제 설명
찍는 방식이 세가지가 있다.
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] |
풀이
#include
#include
#include
#include
using namespace std;
vector solution(vector answers) {
vector> arr{
{1,2,3,4,5}, //5
{2,1,2,3,2,4,2,5}, //8
{3,3,1,1,2,2,4,4,5,5} //10
};
vector arr_size = {5,8,10};
vector save = {0,0,0};
for(int i = 0; i < answers.size(); i++)
{
for(int j = 0; j < 3; j ++)
{
if(answers[i] == arr[j][i % (arr_size[j])])
save[j] += 1;
}
}
int max = *max_element(save.begin(), save.end());
vector answer;
for(int j = 0; j < 3; j ++)
{
if (max == save[j])
answer.push_back(j + 1);
}
return answer;
}설명
- 수포자들이 푼 문제들과, 정답이 서로 맞는지 비교하는 배열을 만들었다.
- 정답을 0~마지막 까지 반복하는 for구문
- 그 안에, 정답마다, 수포자들이 찍은 정답이 맞는지 비교하는 for구문을 추가했다.
4. 체육복
문제 설명
점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다.
전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution 함수를 작성해주세요.
제한사항
전체 학생의 수는 2명 이상 30명 이하입니다.
체육복을 도난당한 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌의 체육복을 가져온 학생의 수는 1명 이상 n명 이하이고 중복되는 번호는 없습니다.
여벌 체육복이 있는 학생만 다른 학생에게 체육복을 빌려줄 수 있습니다.
여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
입출력 예
풀이
- 틀렸다.
#include #include
using namespace std;
int solution(int n, vector lost, vector reserve) {
int answer = 0;
vector arr;
int j = 0;
arr.push_back(1);
for(int i = 0; i < n; i++)
if(lost[j] - 1 == i){
arr.push_back(0);
j += 1;
}
else
arr.push_back(1);
arr.push_back(1);
for(int i = 0; i < reserve.size(); i++)
{
if(arr[reserve[i]] == 0)
arr[reserve[i]] = 1;
else if(arr[reserve[i] - 1] == 0)
{
arr[reserve[i] - 1] = 1;
}
else if(arr[reserve[i] + 1] == 0)
{
arr[reserve[i] + 1] = 1;
}
}
for (int i = 0; i < arr.size(); i++)
{
if (arr[i] == 1)
answer += 1;
}
return answer - 2;
}
- 틀렸지만, 코드 설명을 하면,
- n크기의 벡터 배열을 생성하는데, 잃어버린 학생들의 자리에는 0을 넣어 배열을 생성함.
- 여분의 체육복을 가진 학생들 자리에서, 왼쪽부터 오른쪽으로 빌려주는 식으로 모두 빌려주고, 체육복을 가진 학생 수를 헤아려서 리턴함.
5. 3진법 뒤집기
문제 설명
자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요.
제한사항
n은 1 이상 100,000,000 이하인 자연수입니다.
입출력 예
풀이
#include
#include
#include
using namespace std;
int solution(int n) {
vector s;
int answer = 0;
for (; n != 0; n = n / 3)
{
s.push_back(n % 3);
}
int tmp = 1;
for (int i = 0; i < s.size(); i++)
{
answer += s[s.size() - 1 - i] * tmp;
tmp = tmp * 3;
}
return answer;
}설명
- 10진수를 3진수로 변환 : 3으로 나누었을떄 나머지의 모음이 3진법
- 3진수를 10진법 변환 : 1의 자리수 부터, 3 씩 곱해주며 해당 자릿수와의 곱의 합
6. 같은 숫자는 싫어
-
arr = [1, 1, 3, 3, 0, 1, 1] 이면 [1, 3, 0, 1] 을 return 합니다.
-
arr = [4, 4, 4, 3, 3] 이면 [4, 3] 을 return 합니다.
-
붙어있는 같은 숫자를 제거한 배열 리턴
제한사항
- 배열 arr의 크기 : 1,000,000 이하의 자연수
- 배열 arr의 원소의 크기 : 0보다 크거나 같고 9보다 작거나 같은 정수
입출력 예
풀이
#include
#include
using namespace std;
vector solution(vector arr)
{
vector answer;
// if(arr.size() == 0)
// return answer;
answer.push_back(arr[0]);
for(int i = 1; i < arr.size(); i++)
if(answer.back() != arr[i])
answer.push_back(arr[i]);
return answer;
}7. 두정수 사이의 합
문제 설명
두 정수 a, b가 주어졌을 때 a와 b 사이에 속한 모든 정수의 합을 리턴하는 함수, solution을 완성하세요.
예를 들어 a = 3, b = 5인 경우, 3 + 4 + 5 = 12이므로 12를 리턴합니다.
제한 조건
a와 b가 같은 경우는 둘 중 아무 수나 리턴하세요.
a와 b는 -10,000,000 이상 10,000,000 이하인 정수입니다.
a와 b의 대소관계는 정해져있지 않습니다.
입출력 예
풀이
#include
#include
using namespace std;
long long solution(int a, int b) {
long long answer = 0;
for (int i = a < b ? a : b; i <= (a > b ? a : b); i++)
{
answer += i;
}
return answer;
}풀이
- a와 b중 뭐가 더 큰지 모름
- 삼항 연산자로 작은수를 i에 넣기
- a와 b중 큰수가 될떄까지 모든 값을 더함.
8. 문자열 내 p와 y의 개수
문제 설명
대문자와 소문자가 섞여있는 문자열 s가 주어집니다. s에 'p'의 개수와 'y'의 개수를 비교해 같으면 True, 다르면 False를 return 하는 solution를 완성하세요. 'p', 'y' 모두 하나도 없는 경우는 항상 True를 리턴합니다. 단, 개수를 비교할 때 대문자와 소문자는 구별하지 않습니다.
예를 들어 s가 "pPoooyY"면 true를 return하고 "Pyy"라면 false를 return합니다.
제한사항
문자열 s의 길이 : 50 이하의 자연수
문자열 s는 알파벳으로만 이루어져 있습니다.
입출력 예
풀이
#include
#include
#include
using namespace std;
bool solution(string s)
{
int tmp_p = 0;
int tmp_y = 0;
for(int i = 0; i < s.size(); i++)
{
if (s[i] == 'p' || s[i] == 'P')
tmp_p += 1;
else if(s[i] == 'y' || s[i] == 'Y')
tmp_y += 1;
}
if (tmp_p == tmp_y)
return true;
return false;
}9 .문자열 다루기 기본
문제 설명
문자열 s의 길이가 4 혹은 6이고, 숫자로만 구성돼있는지 확인해주는 함수, solution을 완성하세요. 예를 들어 s가 "a234"이면 False를 리턴하고 "1234"라면 True를 리턴하면 됩니다.
제한 사항
s는 길이 1 이상, 길이 8 이하인 문자열입니다.
입출력 예
풀이
#include
#include
#include
using namespace std;
bool solution(string s) {
int size = s.size();
for(int i = 0; i < size || (size != 4 && size != 6) ; i++)
if(0 == isdigit(s[i]))
return false;
return true;
}10. 소수 찾기
문제 설명
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다.
(1은 소수가 아닙니다.)
제한 조건
n은 2이상 1000000이하의 자연수입니다.
입출력 예
풀이
#include
#include
using namespace std;
int solution(int n) {
int answer = 0;
bool* PrimeArray = new bool[n + 1];
for (int i = 2; i <= n; i++)
PrimeArray[i] = true;
for (int i = 2; i * i <= n; i++)
{
if (PrimeArray[i])
for (int j = i * i; j <= n; j += i)
{
PrimeArray[j] = false;
}
}
for (int i = 2; i <= n; i++)
if(PrimeArray[i] == 1)
answer += 1;
// int flag =0;
// for (int i = 2; i <= n; i++)
// {
// flag = 0;
// for (int j = 2; (j * j) <= i; j++)
// if (i % j == 0){
// flag = 1;
// break;
// }
// if (flag == 0)
// answer += 1;
// }
return answer;
}설명
- 처음 접근은 주석 처리 한 부분 처럼 했다.
- 2부터 제곱 했을떄 보다 작은 범위에서 나누었을떄 하나라도 나누어 지면, 소수가 아니므로 소수를 판별했다.
- 시간초과 나옴.
- 에라토스테네스의 사용. (공식이라 이해만 하고 그냥 가져와서 사용했다. 굳이 외우고 짜볼 필요가 있을까?..)
- https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4
