알고리즘 따라가기가 너무 벅차서 다른 스터디원과 자료구조? 기본기에 대해서 따로 공부를 한다.
이번에는 스택과 큐를 라이브러리 없이 직접 구현해보고, 스택, 큐를 이용한 문제풀이를 했당.
이번 주 숙제는 이렇게 6문제!
완전 기본문제라서 호다닥 끝낼 수 있을 지 알았는데 생각보다 어려워서 당황했다.
1-3번 세문제 푸는 데 8시에 시작한 거 같은데 지금 벌써 새벽 1시 30분이다.
python ver
import sys
input = sys.stdin.readline
c_list = []
def push(num) :
c_list.append(int(num))
def pop():
if len(c_list) == 0:
print("-1")
else :
ans = c_list.pop()
print(ans)
def size():
print(len(c_list))
def empty():
if len(c_list) == 0 :
print("1")
else:
print("0")
def top():
if len(c_list) == 0:
print('-1')
else:
print(c_list[-1])
def main():
N = int(input())
for i in range(N) :
command = input()
temp = command.split()
if temp[0] == 'push' :
push(temp[1])
elif temp[0] == 'top':
top()
elif temp[0] == 'size' :
size()
elif temp[0] == 'empty':
empty()
elif temp[0] == 'pop':
pop()
main()
c++ ver
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
stack <int> arr;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string order;
cin >> order;
if (order == "push") {
int num;
cin >> num;
arr.push(num);
}
if (order == "empty") cout << arr.empty() << endl;
if (order == "size") cout << arr.size() << endl;
if (order == "top") {
if (arr.empty()) cout << -1 << endl;
else cout << arr.top() << endl;
}
if (order == "pop") {
if (arr.empty()) cout << -1 << endl;
else {
cout << arr.top() << endl;
arr.pop(); }
}
}
}
c++ 잘못된 버전
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
int main() {
int test;
scanf("%d", &test);
for (int i = 0; i < test; i++) {
stack<int>Parenthesis;
Parenthesis.push(0);
while () {
string input;
int vps;
cin >> input;
if (input == "\n") break;
if (input == "(") vps = -1;
else vps = 1;
if (Parenthesis.top() + vps == 0) Parenthesis.pop();
else Parenthesis.push(vps);
}
if (!Parenthesis.top()) cout << "YES" << "\n";
else cout << "NO" << "\n";
}
}맨 처음 짰던 코드인데 잘못된 점이 너무 많다 ㅜㅜ
1. cin 을 이용해서 (())() 를 받으려고 했다.
cin을 이용해서 ( , ( ,) 개별적으로 받으려고했는데 , 그렇게 구별할 수가 없다.....ㅜㅜ
무한루프에 빠져버린다.
그냥 string으로 통째로 한 줄을 받아들인 후 , string[i]로 하나하나 구별해서 파악해야한다.
2. ( = -1 , ) = 1 로 치환하고 ( , ) 순서대로 입력이 들어오면 합이 0이 된다고 생각했다.
그러면 ) , ( 순서대로 들어와도 순서쌍은 안되면서 합이 0이 되니까 잘못된 생각이었다,,,,ㅜㅜ
c++ 정답 버전
#include<iostream>
#include<algorithm>
#include<stack>
using namespace std;
int main() {
int test;
scanf("%d", &test);
for (int i = 0; i < test; i++) {
stack<int>Parenthesis;
Parenthesis.push(0);
string total;
cin >> total;
for (int j=0; j<total.size(); j++){
int vps;
char input = total[j];
if (input == '(') vps = -1;
else vps = 1;
if (vps == 1) {
if (Parenthesis.top() == -1) Parenthesis.pop();
else Parenthesis.push(vps);
}
else Parenthesis.push(vps);
}
if (!Parenthesis.top()) cout << "YES" << "\n";
else cout << "NO" << "\n";
}
}주된 idea는 stack에 하나하나 집어넣으며 괄호쌍이 되면 pop으로 빼내버리는 것이다.
1. ( 는 stack에 집어넣는다.
2. ) 가 스캔되면 stack의 맨 윗부분 top이 무엇이냐에 따라 달라진다.
top 이 ( 인 경우 괄호쌍을 만들 수 있기때문에 맨 위에 있는 녀석 top을 pop으로 끄집어낸다.
top아 ) 인 경우 괄호쌍을 만들지 못하므로 새로 입력받은 ) 을 stack에 push한다.
맨 처음 ) 를 스택에 집어넣을 때, 스택의 top을 불러와야되는데 스택이 비어있어서 오류가 난다.
이 점을 방지하고자 12번째 줄에 stack에 0을 미리 넣어놨다.
그 후 맨 마지막 if문은 top이 0이라면 즉, 모든 괄호쌍이 만들어져서 stack에 아무것도 남아있지 않다는 뜻이므로 yes를 출력하고 , top이 0이 아니라면 괄호쌍이 되지 않은 괄호들이 남아있다는 뜻이므로 no를 출력한다.
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<stack>
using namespace std;
stack <int> arr;
vector<string> answer; //no할 때 애매해서 answer에 담아놓고 마지막에 빵!
vector<int>visited; //확인!
int main() {
int n;
bool sequence = false;
scanf("%d", &n);
visited.resize(n+1);
arr.push(0); //우선 0으로 비어진 상태를 만들지말자
int max_number = 0;
for (int j = 0; j < n; j++) {
int input;
scanf("%d", &input);
if (visited[input]) {
sequence = true;
}
else {
if (input > arr.top()) {
bool stop = false;
while (!stop) {
max_number = max_number + 1;
arr.push(max_number);
answer.push_back("+");
if (max_number == input) stop = true;
}
visited[arr.top()] = 1;
arr.pop();
answer.push_back("-");
}
if (input == arr.top()) {
visited[arr.top()] = 1;
arr.pop();
answer.push_back("-");
}
if (input < arr.top()) {
bool stop = false;
while (!stop) {
visited[arr.top()] = 1;
arr.pop();
answer.push_back("-");
if (input == arr.top()) stop = true;
}
visited[arr.top()] = 1;
arr.pop();
answer.push_back("-");
}
}
}
if (sequence) printf("NO\n");
else for (int i = 0; i < answer.size(); i++) cout << answer[i]<<"\n";
}이건 문제 이해부터 안가서 굉장히 애를 먹었다 ㅜㅜ..... 손으로 하나하나 썼더니 이해가 됐다.
주어진 수열을 만들 수 있냐의 문제인데. 4 3 6 8 7 5 2 1 이라는 수열을 stack으로 어떻게 만들거냐는거다.
stack에 입력은 오름차순밖에 안되므로 해결할 수 있다.
맨 처음 push를 통해서 4까지 넣어준다.
| 1 | 2 | 3 | 4 |
그 후 pop을 이용해서 4를 출력한다.
| 1 | 2 | 3 |
또 pop을 이용해서 3을 출력한다.
| 1 | 2 |
여기가 좀 헷갈리는데 지금 4를 stack에 넣었었다. 그러면 무조건 4 이후의 숫자만 다시 stack에 넣을 수 있다.
| 1 | 2 | 5 |
| 1 | 2 | 5 | 6 |
요러켕! 이렇게 손으로 하나하나 그리고 이해함 ㅎㅎ
그리고 수열을 못만드는 경우는 주어진 스택 안에서 321수열을 만드려고한다.
| 1 | 4 | 3 | 2 |
그러면 pop을 2번 해서 3을 빼내야된다.
| 1 | 4 |
그 다음 2를 구해야되는데 다시 추가를 할 수가 없다 이럴 경우 수열을 만들지 못하는거다.
즉 , stack에서 이미 빼낸 숫자에 대해 수열을 만드는 게 불가능한거다.
핵심 idea는
1) 현재 stack의 top 보다 만들어야할 수열의 수 즉, input으로 들어온 숫자가 더 크다면
그 숫자가 될 때 까지 , 계속 stack에 push를 해준다.
여기서 주의해야할 점이 난 top부터 input이라는 숫자까지 push를 해야하는 식으로 코드를 짰었는데
top부터가 아니라 최근 stack에 들어왔던 가장 큰 수 부터 push를 해줘야하는 거다.
위의 예제 같이 4까지 stack에 들어온 상황에서 3,4 를 빼낸 후 다시 stack에 push를 하려면 top인 2가 아니라 5부터 시작해야한다.
그래서 계속 push를 할 때마다 max_number를 업데이트해서 1) 상황이 생겼을 때 max_number부터 input넘버까지 push를 해주었다. 그 후 input과 같은 숫자까지 stack을 해주면 반복문에서 나온 후 pop을 해준다.
2) top == input 그냥 pop으로 빼준다.
3) top > input input이 현재 top보다 훨씬 작은 경우
stack에는 무조건 오름차순으로 숫자가 들어가기 때문에 input이 현재 top보다 작다면, 계속 빼면 된다.
그래서 top이 input과 같아질때까지 계속 pop으로 뺸다.
4) 스택에서 i라는 숫자를 pop으로 빼낼때마다 해당 숫자를 들렸다는 표시로 visited[i]를 체크해준다.
그러면 1,4,3,2 라는 스택에서 32라는 수열을 만들어내려면
2를 pop으로 빼낸 후, visited [2] 를 체크하고 3을 pop으로 빼낸 후 visited[3]을 체크한다.
이후 2라는 수열을 만들려면 visited[2]가 체크 즉 이미 pop으로 스택에서 빠져나갔기때문에 이 수열은 만들지못하는 것을 확인할 수있다.
그래서 input에 해당하는 visited가 이미 체크가 되어있다면 이 경우 no를 출력하게 만들어준다.
9번째 줄에 있는 answer 벡터는 + , - 와 같은 결과물들을 저장한다.
왜 그렇냐면 처음에는 그냥 push, pop을 할 때마다 바로바로 +나 - 를 출력하게 코드를 짰는데 그러면 중간에서 no인걸 확인하면 +++--no 이런식으로 출력이 되어버린다.
그래서 push, pop을 할 떄마다 answer에 넣어놓고서 맨 마지막까지 이게 표현 가능한 수열인지 확인 후 answer에 담겨있는 +, - 를 출력하는 형식으로 짰다.
python 정답 버전
import sys
input = sys.stdin.readline
que = []
def push(num):
que.append(num)
def pop():
if len(que) == 0:
print("-1")
else :
print(que.pop(0))
def size():
print(len(que))
def empty():
if len(que) == 0:
print("1")
else:
print("0")
def front():
if len(que) == 0:
print("-1")
else:
print(que[0])
def back():
if len(que) == 0:
print("-1")
else:
print(que[-1])
def main():
N = int(input())
for i in range(N) :
command = input()
temp = command.split()
if temp[0] == 'push' :
push(temp[1])
elif temp[0] == 'pop':
pop()
elif temp[0] == 'size' :
size()
elif temp[0] == 'empty':
empty()
elif temp[0] == 'front':
front()
elif temp[0] == 'back':
back()
main()
c++ 정답 버전
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
queue <int> arr;
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
string order;
cin >> order;
if (order == "push") {
int num;
cin >> num;
arr.push(num);
}
if (order == "empty") cout << arr.empty() << endl;
if (order == "size") cout << arr.size() << endl;
if (order == "front") {
if (arr.empty()) cout << -1 << endl;
else cout << arr.front() << endl;
}
if (order == "back") {
if (arr.empty()) cout << -1 << endl;
else cout << arr.back() << endl;
}
if (order == "pop") {
if (arr.empty()) cout << -1 << endl;
else {
cout << arr.front() << endl;
arr.pop(); }
}
}
}
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
queue<int> people;
vector<int>permute;
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i < n+1; i++) {
people.push(i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m-1; j++) {
people.push(people.front());
people.pop();
}
permute.push_back(people.front());
people.pop();
}
cout << "<";
for (int i = 0; i < n - 1; i++)cout << permute[i] << ", ";
cout << permute[n-1]<<">";
}매번 m번째인 사람의 순서를 골라내는 문제이다.
핵심 idea는 1번부터 m-1번의 사람들을 맨 마지막으로 계속 옮긴다.
그러면 m번째 사람이 맨 앞 front에 올 때, 빼낸다.
이런식으로 반복하다보면 총 n명의 사람들 중 m번째에 빠지는 사람들의 순서를 알 수 있다.
people이라는 큐에 인덱스와 사람들의 번호가 같게 초기화를 해준다.
그리고 나서 people에 대해서 사람들을 뒤로 옮기며 m번째 사람을 찾는다.
m번째 사람은 people 큐에서 pop으로 빠지고 , permute라는 순서를 저장하는 배열에 집어넣어진다.
모든 사람의 순서를 알면 permute를 출력해 m번째인 사람 n명의 순서를 쭈욱 나열해준다.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
int main() {
int testcase;
scanf("%d", &testcase);
for (int k = 0; k < testcase; k++) {
queue<int>importance;
queue<int>idx;
vector<int>rank_arr;
int n, m;
scanf("%d %d", &n, &m);
rank_arr.resize(n, 0);
for (int i = 0; i < n; i++) {
int imp;
scanf("%d", &imp);
rank_arr[i] = imp;
importance.push(imp);
idx.push(i);
}
sort(rank_arr.begin(), rank_arr.end());
int max = rank_arr[n - 1];
int temp, idx_temp, i = 1, cnt = 0;
while (1) {
if (max == importance.front()) {
cnt++; //몇번째로 출력되는지
temp = importance.front();
importance.pop();
idx_temp = idx.front();
idx.pop();
if (idx_temp == m) break;
max = rank_arr[n - 1 - i];
i++; //최댓값 갱신
}
else {
temp = importance.front();
importance.pop();
importance.push(temp);
idx_temp = idx.front();
idx.pop();
idx.push(idx_temp);
}
}
cout << cnt << endl;
}
}이것도 꽤나 고민많이했던 문제인데 다른 블로그들을 참고하니까 우선순위 큐를 이용해서 풀더라,,,
하지만 아직 우선순위 큐는 모르니까 0_<! 그냥 노가다로 품
핵심 아이디어는
1) 맨 처음 입력된 인덱스 - 중요도 는 큐가 값이 들어오고 빠져나가면서 중요도에 해당하는 인덱스가 바뀌게 된다.
그래서 맨 처음 입력된 인덱스 - 중요도를 기억하기 위해서 idx라는 인덱스 배열을 따로 만들어 주어 중요도가 들어가있는 importacne 배열이 pop, push를 반복할떄마다 idx도 같이 pop,push를 반복하게 만들어주었다.
2) queue에서 중요도가 제일 큰 값이 pop 될 때마다 중요도의 최댓값을 계속 계산하고 싶지 않아, 처음 입력값을 rank_arr이라는 배열에 저장 후 sort를 통해 정렬한 후 역방향 n-1부터 1순으로 최댓값으로 이용했다.
파이썬이었으면 reverse 썼을텐데 ㅠ힝
3) max 값과 큐의 front 값이 같다면, 즉 현재 큐에 남아있는 값 중 중요도가 가장 크므로 출력이 되어야한다는 뜻이다.
front를 기억해놓은 후 , pop을 통해 빼내고 기억해놨던 front 값을 출력해줬다
그 후 max값을 나머지 중요도 중 가장 큰 max 값으로 rank_arr를 이용해 업데이트 해주었다.
이 때 만약 중요도가 제일 크기에 출력된 값의 인덱스가 우리가 몇번째인지 궁금해하는 m과 같다면 우리의 목적을 달성한거므로 반복문을 멈춘다.
4) max 값과 front값이 다르다면, front 값을 pop한 후 그대로 다시 맨 뒤로 push 해준다.
오늘 뭔가 알차다.
쉽다고 생각했지만 어려워서 머리를 엄청 썼던 거 같다.
역시 실버수준의 문제들이지만 도전해서 정답을 맞출 수 있는 수준인 거 같다 킼킼키
'알고리즘 > 자료구조 & 알고리즘 개념정리' 카테고리의 다른 글
| 3주차 자료구조 스터디 - 삽입정렬(insert_sort) (0) | 2020.12.15 |
|---|---|
| 2주차 자료구조 - 이진트리 삽입,탐색,삭제,순회 (0) | 2020.12.12 |
| 4주차 알고리즘 스터디 - 배낭 알고리즘 (0) | 2020.12.04 |
| c++ 알고리즘 스터디 2주차 - 크루스칼 알고리즘 (0) | 2020.11.26 |
| c++ 알고리즘 스터디 2주차 - 유니온파인드 (0) | 2020.11.26 |