아래 모든 문제들은 프로그래머스에서 제공 되는 문제를 이용하였습니다, 감사합니다.
- 2.순위검색 못풀었음..
1. 타겟 넘버
문제 설명
n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.
제한사항
- 주어지는 숫자의 개수는 2개 이상 20개 이하입니다.
- 각 숫자는 1 이상 50 이하인 자연수입니다.
- 타겟 넘버는 1 이상 1000 이하인 자연수입니다.
입출력 예
풀이
#include <string>
#include <vector>
using namespace std;
void dfs(vector<int> *numbers, int target, int *answer, int deep)
{
if (deep == numbers->size())
{
int sum = 0;
for (auto v : *numbers)
{
sum += v;
}
if (sum == target)
*answer += 1;
}
else if(deep != numbers->size())
{
(*numbers)[deep] *= -1;
dfs(numbers, target, answer, deep + 1);
(*numbers)[deep] *= -1;
dfs(numbers, target, answer, deep + 1);
}
}
int solution(vector<int> numbers, int target) {
int answer = 0;
int deep = 0;
dfs(&numbers, target, &answer, deep);
return answer;
}설명
- 1이 5개 주어졋을떄 이 1들이 +또는 -로 나열되어 나올수 있는 모든 조건을 구해주었다.
- 이 문제를 이해하기 dfs를 사용했다.
- dfs 는 저번 ai 부스트 캠프를 공부할떄 배웟었는데, 다시 풀려니 기억이 안나 인터넷 자료를 참고했다.
- solution에서 매게변수로, 값들을 넘겨준다.
- 그러다가, 5개의 1 조합이 완성되었을떄, 나올수 있는 조합의 모든 경우들중 하나씩 완성시켜 가며 타겟과 일치하는지 비교한다.
- 밑에서 다시 스왑을 해주는 이유는 numbers값을 주소값으로 넘겨주지 않으면, 배열을 계속 생성하면서 속도가 느려진다.
- 고로 numbers는 주소로 보내길 지향하며, 그로인해, 위치를 바꾼 numbers 의 값을 다시 제자리로 돌려놓아준다.
2. 순위검색
문제 설명
[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
카카오는 하반기 경력 개발자 공개채용을 진행 중에 있으며 현재 지원서 접수와 코딩테스트가 종료되었습니다. 이번 채용에서 지원자는 지원서 작성 시 아래와 같이 4가지 항목을 반드시 선택하도록 하였습니다.
코딩테스트 참여 개발언어 항목에 cpp, java, python 중 하나를 선택해야 합니다.
지원 직군 항목에 backend와 frontend 중 하나를 선택해야 합니다.
지원 경력구분 항목에 junior와 senior 중 하나를 선택해야 합니다.
선호하는 소울푸드로 chicken과 pizza 중 하나를 선택해야 합니다.
인재영입팀에 근무하고 있는 니니즈는 코딩테스트 결과를 분석하여 채용에 참여한 개발팀들에 제공하기 위해 지원자들의 지원 조건을 선택하면 해당 조건에 맞는 지원자가 몇 명인 지 쉽게 알 수 있는 도구를 만들고 있습니다.
예를 들어, 개발팀에서 궁금해하는 문의사항은 다음과 같은 형태가 될 수 있습니다.
코딩테스트에 java로 참여했으며, backend 직군을 선택했고, junior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 50점 이상 받은 지원자는 몇 명인가?
물론 이 외에도 각 개발팀의 상황에 따라 아래와 같이 다양한 형태의 문의가 있을 수 있습니다.
코딩테스트에 python으로 참여했으며, frontend 직군을 선택했고, senior 경력이면서, 소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
코딩테스트에 cpp로 참여했으며, senior 경력이면서, 소울푸드로 pizza를 선택한 사람 중 코딩테스트 점수를 100점 이상 받은 사람은 모두 몇 명인가?
backend 직군을 선택했고, senior 경력이면서 코딩테스트 점수를 200점 이상 받은 사람은 모두 몇 명인가?
소울푸드로 chicken을 선택한 사람 중 코딩테스트 점수를 250점 이상 받은 사람은 모두 몇 명인가?
코딩테스트 점수를 150점 이상 받은 사람은 모두 몇 명인가?
즉, 개발팀에서 궁금해하는 내용은 다음과 같은 형태를 갖습니다.
- [조건]을 만족하는 사람 중 코딩테스트 점수를 X점 이상 받은 사람은 모두 몇 명인가?
입출력 예
풀이 (못풀었다)
#include <string>
#include <vector>
#include <cstring>
#include <cctype>
#include <iostream>
using namespace std;
vector<int> solution(vector<string> info, vector<string> query) {
vector<int> answer;
vector<string> aa;
vector<vector<string>> query_ev;
string tmp;
for (int i = 0; i < query.size(); i++)
{
tmp = "";
for (int j = 0; j < query[i].size(); j++)
{
if(query[i][j] >= '0' && query[i][j] <= '9')
{
tmp += query[i][j];
}
else if(' ' != query[i][j])
{
tmp += query[i][j];
}
else
{
aa.push_back(tmp);
if(!query[i].compare(j + 1, 4, "and "))
{
j = j + 4;
tmp = "";
}
}
}
aa.push_back(tmp);
query_ev.push_back(aa);
}
for (int i = 0; i < query_ev[0].size(); i++)
{
cout << query_ev[0][i] << " ";
}
return answer;
}설명
- 못푼 문제.
- 구상한 로직, 입력한 info와 query를 split해서 배열로 따로 만들어준다.
- 만들어진 배열들이 모두 일치하는지 확인을 하고, 마지막에 붙은 숫자값 조건이 일치하는지 확인해 준다.
- C++ string 은 split이 없엇다..
- 손수 만들어 주다가 변수 명을 착각해서 한참이나 해메다가 시간안에 못 풀어서 포기햇다 ㅠ..ㅠ
- 다음 코테를 준비할 떄 풀도록!
- 아래 까지 배열 자르는거 구현해둠.
3. 쿼드압축 후 개수 세기
문제 설명
0과 1로 이루어진 2n x 2n 크기의 2차원 정수 배열 arr이 있습니다. 당신은 이 arr을 쿼드 트리와 같은 방식으로 압축하고자 합니다. 구체적인 방식은 다음과 같습니다.
당신이 압축하고자 하는 특정 영역을 S라고 정의합니다.
만약 S 내부에 있는 모든 수가 같은 값이라면, S를 해당 수 하나로 압축시킵니다.
그렇지 않다면, S를 정확히 4개의 균일한 정사각형 영역(입출력 예를 참고해주시기 바랍니다.)으로 쪼갠 뒤, 각 정사각형 영역에 대해 같은 방식의 압축을 시도합니다.
arr이 매개변수로 주어집니다. 위와 같은 방식으로 arr을 압축했을 때, 배열에 최종적으로 남는 0의 개수와 1의 개수를 배열에 담아서 return 하도록 solution 함수를 완성해주세요.
제한사항
- arr의 행의 개수는 1 이상 1024 이하이며, 2의 거듭 제곱수 형태를 하고 있습니다. 즉, arr의 행의 개수는 1, 2, 4, 8, ..., 1024 중 하나입니다.
- arr의 각 행의 길이는 arr의 행의 개수와 같습니다. 즉, arr은 정사각형 배열입니다.
- arr의 각 행에 있는 모든 값은 0 또는 1 입니다.
입출력 예
풀이
#include <string>
#include <vector>
using namespace std;
vector<int> ns(2,0);
void check(vector<vector<int>> *arr, int x, int y, int size)
{
int tmp = (*arr)[x][y];
bool flag = true;
for (int i = x; i < x + size && flag; i++)
{
for (int j = y; j < y + size && flag; j++)
{
if ((*arr)[i][j] != tmp)
flag = false;
}
}
if (flag == true)
ns[tmp]++;
else
{
size = size / 2;
check(arr, x, y, size);
check(arr, x, y+size, size);
check(arr, x+size, y, size);
check(arr, x+size, y+size, size);
}
}
vector<int> solution(vector<vector<int>> arr) {
check(&arr, 0,0,arr.size());
return ns;
}설명
- 이 문제는 풀면서 고생을 많이 했다 .
- 처음에는 size라는 변수에 나누어지는 정사각형의 크기를 만들어 주었고, 그 값으로 증가할수 있는 범위를 제한하고, 작은 정사각형의 오른쪽맨위, 맨아래오른쪽, 아무것에도 해당되지 않을떄 마다 세부 조건을 주어 인덱스를 제어 할려고 햇지만, 너무 번거로워 접근법을 바꾸었다.
- 그림을 보면, 사각형은 어차피 4개만 쪼개어 진다 .4개의 경우를 sizse와 초기 인덱스를 통해 다음 각각의 작은 정사각형의 인덱스를 정해주고,
or구문또한 size를 통해 범위를 저해주엇다.
4. 가장 큰 정사각형 찾기
문제 설명
1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)
예를 들어
1 2 3 4
0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0
가 있다면 가장 큰 정사각형은
1 2 3 4
0 1 1 1
1 1 1 1
1 1 1 1
0 0 1 0
가 되며 넓이는 9가 되므로 9를 반환해 주면 됩니다.
제한사항
- 표(board)는 2차원 배열로 주어집니다.
- 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
- 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
- 표(board)의 값은 1또는 0으로만 이루어져 있습니다.
입출력 예
풀이
첫 풀이 (효율성 실패)
#include <iostream>
#include<vector>
using namespace std;
int find_max(vector<vector<int>> &board, int i, int j, int mi, int mj, int &answer, int deep)
{
if (i + deep >= mi || j + deep >= mj)
{
return 0;
}
for(int x = i; x <= i + deep; x++)
{
if(board[x][j + deep] == 0)
return 0;
}
for(int y = j; y <= j + deep; y++)
{
if(board[i + deep][y] == 0)
return 0;
}
if(answer < deep + 1)
answer = deep + 1;
find_max(board, i, j, mi, mj, answer, deep + 1);
}
int solution(vector<vector<int>> board)
{
int answer = 0;
// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
for(int i = 0; i < board.size() && board.size() - i > answer; i++)
{
for (int j = 0; j < board[i].size() && board[i].size() - j > answer; j++)
{
if (board[i][j] == 1)
{
if(answer == 0)
answer = 1;
find_max(board, i, j, board.size(), board[0].size(), answer, 1);
}
}
}
return answer * answer;
}두 번째 풀이 (통과)
#include <iostream>
#include<vector>
using namespace std;
int solution(vector<vector<int>> board)
{
int answer = 0;
for(int i = 1; i < board.size(); i++)
{
for(int j = 1; j < board[i].size(); j++)
{
if(board[i][j] == 1)
board[i][j] += min(board[i-1][j], min(board[i][j-1], board[i-1][j-1]));
}
}
for(int i = 0; i < board.size(); i++)
{
for(int j = 0 ; j < board[i].size(); j++)
{
if(answer < board[i][j])
answer = board[i][j];
}
}
return answer * answer;
}설명
첫 풀이
- baord에 있는 1에 걸릴떄마다, 최대한으로 나올수 있는 정사각형의 크기를 검사하였다.
- 정사각형 모양이 안나올떄가지 깊이를 증가 시키며, 가로 세로의 값들을 확인하다.
- 문제는 모든 인덱스별로 검사를 하다 보니 속도가 안나왔다.
- 추가적으로, find_max로 넘겨주는 메게변수도 레퍼런스나 주소로 보내준게 아니라서 재귀를 탈떄마다 생성하기 떄문에 속도가 느려진거 같다.
두 번쨰 풀이
- 검사를 진행했던곳의 정보를 남겨두면, 뒤에서 검사했던곳을 다시 검사를 하지 않고 재활용할수 있다.
- 만약 2*2 이상 큰 정사각형이 나오면, 오른쪽 맨믿에 정사각형의 너비를 저장해둔다.
- board의 모든 인덱스를 돌면서 값이 1 일때, 위 왼쪽 왼쪽 대각선을 확인하고, 최소값 +1 의 값을 해당 인덱스에 저장한다.
