본문 바로가기

algorithm

 (69)
백준 3986번 좋은 단어 https://www.acmicpc.net/problem/3986 아이디어:1. string tmp로 입력받고 for (auto x : tmp)로 순회한다.2. stack3. 스택이 비어있지않고 x와 top()이 같은 글자라면 pop()4. 그렇지 않다면 push()5. 마지막에 스택이 비어있으면 ans++ #include #include using namespace std;int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, ans = 0; cin >> N; while (N--) { string tmp; stack S; cin >> tmp; for (auto x : tmp) { if (!S.empty() && S.top(..
백준 4949번 균형잡힌 세상 https://www.acmicpc.net/problem/4949 아이디어:1. 입력받을 때 string tmp; getline(cin, tmp);로 한줄 입력 받고 각 글자에 auto i로 접근하여 괄호 문자인지 체크2. tmp == "." 이면 반복문 종료3. 닫는 괄호가 나왔을 때, 여는 괄호가 없어 pop() 할 수 없다면 그냥 스택에 넣고 마지막에 스택 비어있는지만 체크 if문 사용하는 정갈한 코드#include #include using namespace std;int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); string str; while (1) { getline(cin, str); if (str == ".") break; ..
백준 11003번 최솟값 찾기 - 덱 정렬 https://www.acmicpc.net/problem/11003 아이디어:1. 슬라이딩 윈도우라고 생각했을 때, 범위가 i - L + 1 부터 1까지 => 슬라이딩 윈도우의 사이즈가 L2. 덱을 사용해서 덱 내부 정렬하듯이 구현3. (값, 인덱스)로 구성된 Node 사용4. 새 노드가 추가될 때, 덱에서 새 노드의 숫자보다 큰 숫자의 노드는 전부 삭제 (= 모노톤 스택)5. 새 값 추가. 새 값은 무조건 추가된다.6. 덱 안에 있는 노드의 인덱스 범위가 슬라이딩 윈도우의 크기를 벗어나면 (ex. L = 4인데, 덱에 있는 인덱스는 2~6인 경우) 덱의 앞에서부터 노드 제거 덱의 정렬은 모노톤 스택과 동일한 방식이다. pair 사용하는 정갈한 풀이#include #include using namespa..
백준 5430번 AC https://www.acmicpc.net/problem/5430 아이디어:1. [1,2,3,4]의 형태로 입력됐을 때, 덱 안에 1 2 3 4를 순서대로 push_back() 해주는 parse() 함수를 따로 작성int dat라는 임시 값에 char형 숫자가 들어올 때 이전값 * 10을 하고 들어온 숫자에서 48 ('0'에 해당)을 뺀 수를 더한다.2. 덱 안의 값을 [1, 2, 3, 4]의 형태로 출력하는 print() 함수를 따로 작성3. 'R'이 나올 때마다 reverse()를 하면 시간초과에 걸린다. 'R'은 토글 스위치처럼 0 과 1로 처리한다.4. 'R'이 1이면 reverse()된 상태이므로 pop_front()가 아닌 pop_back() 한다.'R'이 0이면 원래대로 pop_front()..
백준 1021번 회전하는 큐 https://www.acmicpc.net/problem/1021 아이디어:1. 덱에 1~n까지 push_back2. 덱에서 tmp의 위치를 찾는게 중요int idx = find(DQ.begin(), DQ.end(), tmp) - DQ.begin()으로 위치를 찾는다.tmp를 가리키는 반복자에서 시작을 가리키는 반복자인 DQ.begin()을 빼서 구한다.3. idx가 DQ의 가운데(DQ.size() / 2)보다 작거나 같다면 앞쪽에 위치하니까 front()를 뒤로 보내준다.4. 아니라면 뒤쪽에 위치하니까 back()을 앞으로 보내준다.5. 이동 할 때마다 ans++ 해서 마지막에 출력 주의사항:이 문제에는 해당하지 않지만1. tmp가 DQ에 없으면 find()는 DQ.end()를 가리키므로 idx가 DQ..

티스토리툴바