baekjoon 9019:DSLR
9019번 DSLR
접근
D, S, L, R연산 함수로 따로 만들어서 진행. 처음에는 vector에 계속 D, S, L, R연산한 결과를 추가해서 4k+i꼴로 full 4-ary tree를 만들 생각했음. 이렇게 하면 index계산만으로 문자열 뽑아낼 수 있다는 이점 생각함. 하지만 이렇게 하면 중복된 결과가 나와서 제외해야 할 때는 tree구조 무너짐. 그래서 pair을 이용해서 계속 처음부터 vector 다 돌면서 중복검사 하고 중복 아니면 추가하면서 pair의 두번째 인자 자리에 문자열붙여가는 방식으로 바꿈. 이렇게 하니까 문자열 붙여가는 연산이 시간이 오래걸려서 시간초과 뜸. 그래서 두번째 인자에 parent의 index 넣고 나중에 따로 문자열 뽑고 stack으로 뒤집기로 함. 그래도 시간초과 떠서 visited 배열 만들고 추가할 때 1표시하는 방식으로 중복 검사 빠르게함. –> 성공
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <iostream>
#include <vector>
#include <stack>
#include <array>
#include <string>
using namespace std;
short calcuD(short n);
short calcuS(short n);
short calcuL(short n);
short calcuR(short n);
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
for(int i = 0; i < t; i++){
short a, b;
cin >> a >> b;
vector<pair<short, short>> tree;
array<int, 10000> visited{};
tree.push_back(make_pair(a, -1));
visited[a] = 1;
int j = 0;
while(true){
pair<short, short> target = tree[j];
if(target.first == b) break;
if(!visited[calcuD(target.first)]){
tree.push_back(make_pair(calcuD(target.first), j));
visited[calcuD(target.first)] = 1;
}
if(!visited[calcuS(target.first)]){
tree.push_back(make_pair(calcuS(target.first), j));
visited[calcuS(target.first)] = 1;
}
if(!visited[calcuL(target.first)]){
tree.push_back(make_pair(calcuL(target.first), j));
visited[calcuL(target.first)] = 1;
}
if(!visited[calcuR(target.first)]){
tree.push_back(make_pair(calcuR(target.first), j));
visited[calcuR(target.first)] = 1;
}
j++;
}
stack<char> st;
pair<short, short> target = tree[j];
while(target.second != -1){
pair<short, short> parent = tree[target.second];
if(target.first == calcuD(parent.first)){
st.push('D');
}
else if (target.first == calcuS(parent.first)){
st.push('S');
}
else if (target.first == calcuL(parent.first)){
st.push('L');
}
else if (target.first == calcuR(parent.first)){
st.push('R');
}
target = parent;
}
while(!st.empty()){
cout << st.top();
st.pop();
}
tree.clear();
tree.shrink_to_fit();
if (i != t-1) cout << "\n";
}
return 0;
}
short calcuD(short n){
return n * 2 % 10000;
}
short calcuS(short n){
return n - 1 < 0 ? 9999 : n - 1;
}
short calcuL(short n){
return (n*10) % 10000 + n / 1000;
}
short calcuR(short n){
return n / 10 + (n % 10) * 1000;
}
다른 접근
queue를 이용한 풀이도 꽤 봤다. 처음에는 queue에서 중복검사를 하려면 처음부터 다 pop시켜야한다고 생각했는데 visited 배열 쓸거면 그렇게 안해도 되고 좋은거 같다. 그런데 queue를 이용한 풀이도 결국은 저장용으로 queue를 쓰지는 않고 작업큐느낌으로 queue를 쓰는 것 같다.
배운 점
전체 시간복잡도를 생각해봐야한다. 처음 봤을 때는 4배씩 계속 늘거라 생각했지만 결국 O(10000)이 한계다. 물론 그렇기 때문에 중복 계산을 해야하는거고 중복 계산은 매번 배열 돌지말고 따로 배열 만들어서 표시하면서 해야한다. (똑같은 일 또 하지마라, dp의 교훈)