[프로그래머스 C++] 소수 찾기
·
알고리즘/Programmers
문자 배열이 주어지면 각 자릿수로 만들 수 있는 모든 경우의 수를 따져서 소수가 되는 수가 몇 개인지 따져보는 문제다. 소수는 에라토스테네스의 체로 쉽게 구할 수 있지만 문제는 '어떻게 모든 경우의 수를 따지는가'이다. 우리는 두 가지 경우로 풀 수 있다. dfs로 풀던가 next_permutation으로 풀던가 둘 중 하나로 풀면 된다. 나는 next_permutation으로 풀었다. #include #include #include #include using namespace std; vector sieve; void era(int n) { sieve.resize(n + 1, true); sieve[0] = sieve[1] = false; for (int i = 2; i * i
[프로그래머스 C++] 두 개 뽑아서 더하기
·
알고리즘/Programmers
1차원 배열이 주어지면 그 수에서 두 개를 뽑아서 더해주면 된다. 단 중복을 허용하지 않고 오름차순으로 정렬해야 한다. 제한 사항을 보면 numbers의 길이가 100 이하이다. 따라서 이중 포문으로 해줘도 \(O(N^2)\)의 시간복잡도를 가지기에 중복을 방지하는 stl set을 사용해서 자기 자신인 i == j 인 경우를 제외하고 전부 넣어준다. 이후에 반복문을 모두 돌았다면 answer에 삽입해주면 된다. 1234567891011121314151617181920#include #include #include using namespace std; vector solution(vector numbers) { vector answer; set s; int n = numbers.size(); for (in..
[프로그래머스 C++] 크레인 인형뽑기 게임
·
알고리즘/Programmers
N * N 행렬에 각각 캐릭터의 번호가 주어지면 Stack에 넣어서 같은 번호가 나오면 pop 하고 아니면 push 하는 쉬운 문제였다. #include #include #include using namespace std; int pick(vector& board, int col) { for (int i = 0; i < board.size(); i++) { if (board[i][col] == 0) continue; int ret = board[i][col]; board[i][col] = 0; return ret; } return 0; } int solution(vector board, vector moves) { int answer = 0; stack s; for (int i = 0; i < moves..