Category: 자료구조

2021
0
Programming프로그래머스

프로그래머스 - 표 편집 (Cpp)

https://programmers.co.kr/learn/courses/30/lessons/81303 문제 해설자료구조 Set에 대한 확실한 이해가 있어야 해결할 수 있는 문제,Set의 다양한 함수를 사용할 수 있는 좋은 문제다. 전체 소스 코드#include <bits/stdc++.h>using namespace std;bool check[1000010];set<int> arr;stack<int> deletedData;int executeCmd(int point, string cmd) { char commond = cmd[0]; auto iter = arr.find(point); string str; int value; if (commond == 'U' || commond == 'D') { for (int i = 2; i < cmd.size(); i++) { str += cmd[i]; } value = stoi(str); } if (commond == 'U') { for (int i = 0; i < value; i++) { iter--; } } if (commond == 'D') { for (int i = 0; i < value; i++) { iter++; } } if (commond == 'C') { deletedData.push(*iter); iter = arr.erase(iter); if (iter == arr.end()) { iter--; } } if (commond == 'Z') { if (!deletedData.empty()) { int value = deletedData.top(); deletedData.pop(); arr.insert(value); } } return *iter;}void insertNumber(int n) { for (int i = 0; i < n; i++) { arr.insert(i); }}void scanSet() { for (auto iter = arr.begin(); iter != arr.end(); iter++) { int index = *iter; check[index] = true; }}string solution(int n, int k, vector<string> cmd) { string answer = ""; insertNumber(n); int point = k; for (int i = 0; i < cmd.size(); i++) { point = executeCmd(point, cmd[i]); } scanSet(); for (int i = 0; i < n; i++) { if (check[i]) { answer += 'O'; } else { answer += 'X'; } } return answer;}

0
Programming프로그래머스

프로그래머스 - 수식 최대화 (Cpp)

https://programmers.co.kr/learn/courses/30/lessons/67257 문제 해설경우의 수 문제이다. 모든 경우의 연산자 우선순위를 만들어 해당 연산자 우선순위를 이용해 연산을 진행하면 된다. 중위표기식으로 나타난 식을 후위 표기식으로 바꿔서 문제를 해결 했다. 경우의 수 만들기만들 수 있는 모든 연산자 우선순위를 만들어줘야 한다. DFS를 이용해 모든 경우의 수를 만들어 줬다. void makeAllCase(int depth) { if (depth == 3) { allCase.push_back(cntCase); } for (int i = 0; i < 3; i++) { int cntOper = operation[i]; if (check[i] == false) { check[i] = true; cntCase[depth] = cntOper; makeAllCase(depth + 1); check[i] = false; } }} 연산자 우선순위를 가반으로 한 연산 가장 높은 우선순위의 연산자가 들어왔을 때 Stack을 확인해 같은 먼저 들어온 같은 우선순위의 연산자가 있는지 확인한다. 같은 우선순위의 연산자가 Stack에 있는 경우 pop 해서 해당 연산을 진행한 후 지금 들어온 연산자를 push한다. 없는 경우에는 Stack에 push 한다. 두번째 우선 순위가 연산자가 들어온 경우 Stack을 확인해 우선순위가 같거나 큰 연산자가 없어질 때까지 연산을 진행한 후 pop 한다. Stack에 우선순위가 같거나 큰 연산자가 없을 경우에는 Stack에 push 한다. 세번째 우선 순위의 연산자가 들어온 경우 Stack을 확인해 우선순위가 같거나 큰 연산자가 없어질 때까지 연산을 진행한 후 pop 한다. Stack에 우선순위가 같거나 큰 연산자가 없을 경우에는 Stack에 push 한다.