재원블로그 재원블로그

이 문제는 스택을 이용하여 풀었다. 이 문제의 핵심은 스택을 이용하여 괄호의 유효성을 체크하는 것과 문자열을 왼쪽으로 돌리는 방법을 구현하는 것이다. 괄호의 유효성을 체크하는 수도코드는 다음과 같다. 만약 비어있으면 push 안비어있으면 만약 여는 괄호 push 만약 닫는 괄호 top과 비교 같으면 pop 다르면 false 다 끝나고 비어있으면 true 안 비어있으면 false 전체 코드는 다음과 같다. #include #include #include #include using namespace std; bool correct(string& str) { stack st; for (char c : str) { if (st.empty()) { st.push(c); } else { if (c == '[' ||..

이 문제는 그리디로 풀었다. 문제에서 주어진 배열에서 k개의 귤을 고르는데, 종류가 다른 수를 최소화하는 문제였다. 처음에 배열을 순회하면서 해당 숫자의 cnt를 세고, cnt가 높은 순서로 배열을 정렬한다. 그 다음 k개를 선택하면서 종류가 달라졌을때 answer++을 하면 쉽게 풀 수 있다. #include #include #include #include using namespace std; map cnt; bool compare(int a, int b) { if (cnt[a] == cnt[b]) { return a > b; } return cnt[a] > cnt[b]; } int solution(int k, vector tangerine) { int answer = 0; // base case if..

이 문제는 다이나믹 프로그래밍을 이용한 문제이다. 입력이 최대 2000인 자연수이므로 배열로 선언하기 좋은 크기이고, 경우의 수가 매우 많아 완전 탐색으로는 중복된 경우가 많이 생기기 때문에 다이나믹 프로그래밍을 사용하면 좋다. 이 문제의 경우 점화식은 dp[1] = 1 dp[2] = 2 dp[k] = (dp[k - 1] + dp[k - 2]) % 1234567 (k >= 3) 이 된다. 헷갈렸던 점은 1칸 전까지 오면 1가지의 경우의 수 밖에 없지만, 2칸 전까지 오면 1 1 로 오는 것과 2 한번에 오는 두가지 경우가 있지 않나하는 것이었다. 그러나 이는 중복 경우를 셀 수 밖에 없는데, 전부 한칸씩 오는 경우가 dp[k - 1]과 dp[k - 2]에 모두 해당되어 있기 때문에 dp[k - 2] 에서..

이 문제는 유클리드 호제법을 이용한 문제이다. 나는 이 문제를 풀 때 처음에 주어진 배열 안 모든 숫자에 대한 최대공약수와 최소공배수를 구하려고 했다. 하지만 이렇게 풀면 정답이 나오지 않는다. 정확한 방법은 두 수씩 짝을 지어서 그 수에 대한 최소공배수를 얻고, 그 다음 수와 이전 결과로 나온 수를 짝짓는 식으로 해야 올바른 답이 나온다. 개념에 오류가 있어 헤맸던 문제였다. #include #include #include using namespace std; int gcd(int a, int b) { if (a < b) { swap(a, b); } if (b == 0) { return a; } return gcd(b, a % b); } int solution(vector arr) { unsigned ..

이 문제는 수학 문제이다. 어떤 사람의 수가 n이라고 할 때, n이 홀수인 경우 이겼을 때 다음 라운드에서의 번호는 n / 2 + 1이고, 짝수인 경우 n / 2 가 된다는 규칙을 찾았다. 또한 a, b 둘이 만났다면 둘이 경기를 하고 난 다음 라운드의 번호가 각각 같게 된다. 이를 이용해서 문제를 풀면 쉽게 풀 수 있다. #include using namespace std; int solution(int n, int a, int b) { int answer = 0; while (a != b) { if (a % 2 == 1) { a = a / 2 + 1; } else { a = a / 2; } if (b % 2 == 1) { b = b / 2 + 1; } else { b = b / 2; } answer+..

이 문제는 프로그래머스 level 2에 있는 문제이다. 이 문제를 풀기 위해 많은 노력을 기울였지만 풀지 못했다. 정답 횟수를 1부터 n / 2까지 돌리면서 해당 숫자로 n까지 갈 수 있는지로 풀어봤지만 이건 시간 초과가 발생하고 애초에 정답도 안 나온다. 다른 어떤 방법을 써도 완전 탐색과 같은 방향으로 시간 초과가 나지 않을 수는 없었다. 그래서 구글링을 통해 코드를 봤는데, n부터 시작해서 2로 나눈 나머지를 보고 1이면 점프 횟수를 추가하는 방식으로 하면 무조건 정답이 나올 것이라는 생각이 들었다. 그리디한 방식이었는데, 이렇게 간단한 방법을 생각하지 못해 아쉬웠다. #include using namespace std; int solution(int n) { int ans = 0; while (n..

이 문제는 구현 문제이다. 일단 words 를 기준으로 완전 탐색을 하는데 words의 최대 길이가 100밖에 안되므로 시간 초과 걱정은 없다. 또한 문제에서 나온 규칙에서 중요한 것은 3, 4인데, 5는 단어의 길이가 최소 2이므로 애초에 위반할 수 없기 때문이다. words에 대해 for문을 돌리고, 3번과 4번 규칙을 만족하지 않는 경우 바로 break하고 정답을 출력하면 쉽게 풀 수 있다. #include #include #include #include using namespace std; map mp; vector solution(int n, vector words) { vector answer; int wordIndex = 0; int turn = 1; int peopleIndex = 1; s..

이 문제는 스택을 이용하는 문제이다. 주어진 문자열을 순차 탐색하면서 스택에 push하거나 pop 하므로, O(n) 시간이 걸리는데 문자열의 최대 길이가 1,000,000 이므로 충분히 시간 안에 풀 수 있다. 스택을 이용했을 때 top과 비교해서 현재 문자가 같으면 pop, 다르면 push 하고, 전체 탐색이 끝난 후 스택에 문자가 남아있으면 0, 비어있으면 1을 리턴하면 정답이 나온다. #include #include #include using namespace std; int solution(string s) { int answer = -1; // base case if (s.size() == 1) { return 0; } stack st; for (char c : s) { if (st.empty(..