프로그래머스 풀이/Lv 2 (30) 썸네일형 리스트형 프로그래머스 - 짝지어 제거하기(C++) 문제 설명 처럼 2개 짝짓고 제거하면 시간초과로 풀 수 없다. 첫 풀이는 다음과 같았다. 먼저 abcc 이런식으로 a, b가 홀수개이면 절대 문장은 제거되지 않는다. 그렇기 때문에 먼저 원소들의 개수를 세는 작업을 했고 이 작업을 통과하였을 때 제거 연산을 해봤다. 그러나 별짓을 다 해도 저 3개의 효율 테스트를 통과할 수가 없었다... 결국 아이디어를 구하기 위해 질문하기를 보았는데 답은 "스택" 이었다. 최대 크기가 100만일 때 부터 알아봤어야하는데 나는 아직 멀었다. 85점까진 받았기 때문에 코테나 대회였다면 바로 넘겼을 문제이기는 하다. 스택을 사용한다. ex) dcaabbcd 가 들어왔을 때 1. d를 꺼내 c와 비교한다. 둘은 다르다! 그러므로 꺼낸 d를 또다른 서브 스택에 넣어둔다 . 현재.. 프로그래머스 - 귤 고르기(C++) 이번에도 빡구현문제다. 프로그래머스 구현문제들은 문제를 이해하긴 되게 쉬운데 막상 어떻게 하지? 생각하면 잘 안풀리는게 특징이다. * 문제풀이 * 1. 주어진 귤의 사이즈대로 map에 삽입한다. 2. 갯수가 큰 순서대로 sort 한다. 3. 1개씩 더하고 k 보다 크거나 같아지면 멈추고 지금까지 넣은 사이즈의 귤의 갯수를 리턴한다. 다른 사람들 풀이보니까 짧고 간단하게 했던데.. 봐도 이해도 안가고 모르겠다. 그리고 실행시간을 보니 그닥 좋은 풀이는 아닌 것 같다. #include #include #include #include #include using namespace std; bool compare(const int a, const int b){ return a > b; } int solution(.. 프로그래머스 - 할인 행사 (C++) 문제 자체는 이해하기 어렵지 않다. 또 주어지는 배열의 길이가 길지 않기 때문에 시간초과를 걱정할 필요가 없어 완전탐색 식으로 전부 비교해보며 풀었다. 문제 유형은 별다른 알고리즘을 요구하는 문제는 아니고 그냥 빡구현이다. - 문제풀이 먼저 주어진 want 와 number를 각 맵을 이용해 넣어둔다 apple : 2 banan : 3 이런식으로 넣어둔다. 그 다음 discount는 10개씩 탐색해야하므로 만약 14개의 discount 가 주어졌다면 0~9 1~10 2~11 3~12 4~13 이렇게 5번 탐색해야한다. 그러므로 discount.size() - 10 으로 범위를 잡아준다. 그리고 discount도 중복을 제외하고 맵에 넣어둔다 apple : 2 banana : 3 pork : 2 이런식으로,.. 프로그래머스 - 혼자 놀기의 달인 (C++) 그냥 미친 빡구현 문제다. 문제 해석이 가장 중요하다. 상자가 열려있는지 확인할 bool 배열한개, map으로 각 상자와 카드번호를 생성한다. 주의해야할 예외사항은 1. 그룹이 1개이면 무조건 0점이다. 2. 각 그룹의 값이 같을 수 있다. #include #include #include #include #include #define MAX 101 using namespace std; int solution(vector cards) { int answer = 0; bool open[MAX] = {false,}; vector group; map cardbox; for(int i = 0; i < cards.size(); i++){ cardbox.insert(make_pair(i + 1, cards[i]));.. 프로그래머스 - 멀리 뛰기(C++) 한칸 아니면 두칸 이동할 수 있다. 처음에는 여러가지 방법으로 한 곳으로 간다고 생각하고 백준 숨바꼭질 2를 떠올려 BFS로 구현했으나 #include #include #include using namespace std; bool visited[2001] = {false,}; queue Q; long long cnt = 0; void BFS(int n){ Q.push(0); while(!Q.empty()){ int X = Q.front(); Q.pop(); visited[X] = true; if(X == n){ cnt++; } if(X + 1 프로그래머스 - 점프와 순간이동 (C++) 처음엔 최소값을 구하는거고 백준에서 비슷한 워딩의 문제를 본 적이 있어서 BFS인 줄 알았다. 이 문제는 0에서 시작해서 걷거나 순간이동 두가지 조건이 있는것으로 보인다. 그러나 처음 몇 걸음을 걸어야할지 알수없다. 한발짝씩 가서 모든 조건을 새어보는 것은 불가능하다. 그러나 목적지 입장에서 생각해보면 이전의 수에서 x2 되었거나 +1 되었거나 둘중 하나이다. x2는 비용이 0이기 때문에 이왕이면 x2 를 많이 사용해야한다. 그러므로 n이 짝수이면 나누기2 홀수이면 빼기 1 하면서 0까지 얼마나 걸리나 계산하면 된다. #include using namespace std; int solution(int n) { int ans = 0; while(true){ if(n % 2 == 0){ n = n / 2; .. 이전 1 2 3 4 다음
