코테에서 한 번쯤 봤을 법한 문제이다.
(())()()
))(()
()())(()
위처럼 있다고 할 때 괄호 쌍이 모두 있는지 판단하는 문제이다. 일단 안쪽부터 짝 맞추기를 해본다면 첫번째 입력만 맞다는 것을 알 수 있다. 괄호가 여러 종류일 때는 단순히 괄호 개수만으로 판별하기 어렵다.
({(){}})
이러한 유형은 스택을 사용한다면 빠른 시간복잡도로 풀어낼 수 있다.
양쪽 끝에서 삽입 삭제 전부 가능한 자료구조이다. Double Ended Queue라고 큐의 진화형 느낌이다.
다만 STL deque에서는 인덱스로 원소 접근이 가능하다.
const int MX=100005;
int dat[2*MX+1];
int head=MX, tail=MX;
void push_front(int x){
dat[--head]=x;
}
void push_back(int x){
dat[tail++]=x;
}
void pop_front(){
head++;
}
void pop_back(){
tail--;
}
int front(){
return dat[head];
}
int back(){
return dat[tail-1];
}
배열로 구현하자면 위와 같다. STL 덱은 아래 참고.
#include <bits/stdc++.h>
using namespace std;
int main(void){
deque<int> DQ;
DQ.push_front(10);
DQ.push_back(20);
DQ.size();
DQ.empty();
DQ.insert(DQ.begin()+1,33);
}
STL의 덱은 pop,push front, back 말고도 insert, erase도 가능하다. 원소 접근이 가능하다. vector와 비슷하게 느껴질 수 있으나 STL이 제공하는 Deque은 모든 원소들이 메모리상에 연속 배치되어 있지 않다(벡터는 연속 배치)
큐는 FIFO 바로 나와주면 된다.
추가 -rear 제거 -front 로 보통 나타낸다.
스택 어렵지 않았으니까 걍 내가 구현해보자.
const int MX = 100005;
int dat[MX];
int tail=0; // 추가
int head=0; // 제거
void push(int x){
dat[tail++]=x;
}
void pop(){
head++;
}
int front(){
return dat[head];
}
int back(){
return dat[tail-1];
}
제미나이한테 던졌더니 길이 제한 생각 안 하냐고 혼났다. 그치 대기큐 같은 병목 현상도 있지. 바킹독에서는 이를 다루고 있진 않다. 혹시 필요하다면 % 연산 기호로 원형 큐를 만들 수 있을 거 같다.
#include <bits/stdc++.h>
using namespace std;
int main(void){
queue<int> q;
q.push(10);
q.push(20);
cout<<q.size()<<'\n';
q.empty();
q.pop();
q.front();
q.back();
}
풀다가 연산자 우선순위 관련한 오류가 하나 나왔다.
#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int main(void){
int n;
cin>>n;
while(n--){
string inst;
cin>>inst;
if(inst=="push"){
int nor;
cin>>nor;
q.push(nor);
}
else if(inst=="front") cout<< (q.size()==0) ? -1 : q.front()<<'\n';
else if(inst=="back") cout<< (q.size()==0) ? -1 : q.back() << '\n';
else if(inst=="size") cout<<q.size()<<'\n';
else if(inst=="empty") cout<<q.empty()<<'\n';
else if(inst=="pop") {
cout<< (q.size()==0) ? -1 : q.front()<<'\n';
if(q.size()!=0) q.pop();
}
}
}
/*
❌ Test Case #1: Failed
--------------- Expected ---------------
1
2
2
0
1
2
-1
0
1
-1
0
3
---------------- Actual ----------------
002
0
0010
1
10
0
--------------- 채점 종료 ----------------
*/
자꾸 이런 오류가 뜨길래 제미나이한테 넘겼더니 연산 우선순위 때문이라고 한다.
// 작성하신 코드
cout << (q.size()==0) ? -1 : q.front() << '\n';
// 컴퓨터의 해석 (괄호 위치 주목!)
( cout << (q.size()==0) ) ? -1 : ( q.front() << '\n' );
위와 같이 삼항 연산자보다 출력 연산자가 우선순위가 높다고 한다.
위 키워드 보면 int 최댓값임을 바로 파악해야 한다.
스택은 LIFO이다. 큐, 덱, 스택 같은 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한된 자료구조를 Restricted Structure라고 부른다.
const int MX=1000005;
int dat[MX];
int pos=0;
일단 여기서 원소를 담은 큰 배열과 인덱스를 저장할 변수 한 개만 있으면 구현이 가능하다. pos는 원소의 개수이자 추가할 때 삽입해야 하는 인덱스를 의미한다.
#include <bits/stdc++.h>
using namespace std;
const int MX=1000005;
int dat[MX];
int pos=0;
void push(int x){
dat[pos]=x;
pos++; //dat[pos++]=x;로 한 줄로 표현도 가능, 전치 후치 차이에 대해 알고 있기
}
void pop(){
pos--; //여기까지만 써도 됨
/* 어차피 아래 코드들은 나중에 push할 때 덮어쓸 공간
cout<<dat[pos];
dat[pos]=0; */
}
void top(){
return dat[pos-1];
}
void test(){
}
int main(void){
test();
}
음 연결 리스트 하다가 얘 하니까 구현은 쉽다. 그래도 바킹독 강의에서는 STL을 권장한다. STL stack을 썼으면 최소 스택 쪽에는 문제 없다는 걸 알 수 있으니 로직 개선에 신경 쓸 수 있다.
#include <bits/stdc++.h>
using namespace std;
int main(void){
stack<int> s;
s.push(10);
s.push(20);
cout<<s.size()<<'\n'; // 2
s.empty(); // bool
s.pop(); //10만 남을 것
}
연결 리스트의 성질
struct NODE {
struct NODE *prev, *next;
int data;
};
원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 길이를 효율적으로 구하는 방법?
효율적으로 구하라 -> 시간복잡도와 공간복잡도를 생각해봐야 한다. 동일한 노드가 나올 때까지 계속 다음 노드로 가면 된다. O(1), O(N)
각 연결 포인터가 가리키는 주소가 같아지는 순간이 교차점인데 A,B의 길이가 다르니까 더 긴 길이를 차만큼 빼줘서 동시에 도달할 수 있도록 한다. O(A+B)로 전체 노드 길이를 알기위한 순회는 필요하다.
주어진 연결 리스트 안에 사이클이 있는지 판단하라. O(N)으로 주소 다 기록해놓고 이전에 나왔던 주소가 있는지 체킹하면 될 거 같은데.. 공간 복잡도 O(1) 방법이 있다고 한다. Floyd’s cycle-finding algorithm으로 한 칸씩 이동하는 slow pointer와 두 칸씩 이동하는 fast pointer를 두면 사이클 내에서 꼭 같은 노드에서 만나게 된다.
// http://boj.kr/5c97cb6a88324537a722e8de9169e2ab
#include <bits/stdc++.h>
using namespace std;
const int MX = 1000005;
char dat[MX];
int pre[MX];
int nxt[MX];
int unused = 1;
void insert(int addr, char num){
dat[unused] = num;
pre[unused] = addr;
nxt[unused] = nxt[addr];
if(nxt[addr] != -1) pre[nxt[addr]] = unused;
nxt[addr] = unused;
unused++;
}
void erase(int addr){
nxt[pre[addr]] = nxt[addr];
if(nxt[addr] != -1) pre[nxt[addr]] = pre[addr];
}
void traversal(){
int cur = nxt[0];
while(cur != -1){
cout << dat[cur];
cur = nxt[cur];
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
fill(pre,pre+MX,-1);
fill(nxt,nxt+MX,-1);
string init;
cin >> init;
int cursor = 0;
for(auto c : init){
insert(cursor, c);
cursor++;
}
int q;
cin >> q;
while (q--) {
char op;
cin >> op;
if (op == 'P') {
char add;
cin >> add;
insert(cursor, add);
cursor = nxt[cursor];
}
else if (op == 'L') {
if (pre[cursor] != -1) cursor = pre[cursor];
}
else if (op == 'D') {
if (nxt[cursor] != -1) cursor = nxt[cursor];
}
else { // 'B'
if (pre[cursor] != -1) {
erase(cursor);
cursor = pre[cursor];
}
}
}
traversal();
}