티스토리 뷰
#. Problem
* The copyright in this matter is in Inflearn
#. Resolution Process
1. Read and understand problem
2. Redefine the problem + abstract
3. Create solution plan (select Algorithm, Data structure)
4. Prove the plan (check performance time and usage memory)
5. Carry out the plan
6. Look back on the plan and find a way to improve it
#. Solve
1. 주어진 inversion sequence 을 활용하여 원래 수열을 구한다는 것이 포인트이다.
inversion sequence 는 문제에 잘 설명되어 있으므로..
5 3 4 0 2 1 1 0 이라는 inversion sequence 가 입력되었을 때,
앞에서부터 밀어준다는(?) 느낌으로 해주면 된다.
i = 1, up = 5 (1보다 큰 숫자가 5개)
0 0 0 0 0 1 0 0 (1을 앞에서부터 5번 밀어준다)
첫 번째, 0 1 0 0 0 0 0 0
두 번째, 0 0 1 0 0 0 0 0
세 번째, 0 0 0 1 0 0 0 0
네 번째, 0 0 0 0 1 0 0 0
다섯 번째, 0 0 0 0 0 1 0 0
i = 2, up = 3 (2보다 큰 숫자가 3개)
0 0 0 2 0 1 0 0
i = 3, up = 4 (3보다 큰 숫자가 4개)
0 0 0 2 0 1 3 0
여기서 생각을 좀 해야한다.
0이거나 0이 아니면 자신보다 큰 숫자면 up을 1씩 증가시켜주면서 up 이 4가 되었을 때,
그 다음 자리가 0인 곳에 i 를 넣어주면 될 것 같다.
i = 4, up = 0 (4보다 큰 숫자가 0개)
4 0 0 2 0 1 3 0
up이 0이면 첫 번째 자리에 그냥 넣어주면 된다.
i = 5, up = 2 (5보다 큰 숫자가 2개)
4 0 0 2 5 1 3 0
0이거나 0이 아니면 자신보다 큰 숫자자면 up++, up이 2가 되었을 때, 그 뒤에서 0인 자리를 찾아서 들어간다.
글로 설명하기가 쉽지 않지만..
이 과정을 코드로 옮겨보자!
2. 큰 숫자부터 처리하는게 포인트였다..
위 방법이 틀린것은 아니지만 더 효율적인 방법이 있었다리..
5 3 4 0 2 1 1 0 이라는 inversion sequence 가 입력되었을 때,
뒤에서부터 처리해보다
우선 index 8 자리에 그대로 들어간 후
0 0 0 0 0 0 0 8
8보다 큰 숫자는 0개 이므로, 0번 교환해주면 된다. 그럼 그대로겠죠?
original sequence 는 0 0 0 0 0 0 0 8
7도 마찬가지로 우선 index 7 자리에 그대로 들어간 후
0 0 0 0 0 0 7 8
7 보다 큰 숫자는 1개 이므로, 1번의 교환이 이루어진다.
original sequence 는 0 0 0 0 0 0 8 7
6도 우선 index 6 자리에 그대로 들어간 후
0 0 0 0 0 6 8 7
6 보다 큰 숫자는 1개 이므로, 1번의 교환이 이루어진다.
original sequence 는 0 0 0 0 0 8 6 7
5도 우선 index 5 자리에 그대로 들어간 후
0 0 0 0 5 8 6 7
5 보다 큰 숫자는 2개 이므로, 2번의 교환이 이루어진다.
original sequence 는 0 0 0 0 8 6 5 7
4도 우선 index 4 자리에 그대로 들어간 후
0 0 0 4 8 6 5 7
4 보다 큰 숫자는 0개 이므로, 0번의 교환이 이루어진다.
original sequence 는 0 0 0 4 8 6 5 7
3도 우선 index 3 자리에 그대로 들어간 후
0 0 3 4 8 6 5 7
3 보다 큰 숫자는 4개 이므로, 4번의 교환이 이루어진다.
original sequence 는 0 0 4 8 6 5 3 7
...
#. Code
1. 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 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; int main(void) { freopen("input.txt", "rt", stdin); int n, i, j, pos, tmp; scanf("%d", &n); vector<int> v(n + 1); vector<int> rst(n + 1); for (i = 1; i <= n; i++) scanf("%d", &v[i]); for (i = 1; i <= n; i++) { pos = 0; for (j = 1; j < n; j++) { if (rst[j] == 0 || rst[j] > i) { if (pos == v[i]) break; pos++; } } for (; j <= n; j++) { if (!rst[j]) { rst[j] = i; break; } } } for (i = 1; i <= n; i++) printf("%d ", rst[i]); return 0; } | cs |
계속 이상한 결과가 나와서..
디버깅하면서 계속 뜯어 고쳤는데 어찌되었건 solve 에서 설명한 과정대로 짜여진것 같긴 하다.
2. 8부터 처리
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 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; int main(void) { freopen("input.txt", "rt", stdin); int n, i, j, cnt; scanf("%d", &n); vector<int> is(n + 1); vector<int> os(n + 1); for (i = 1; i <= n; i++) scanf("%d", &is[i]); for (i = n; i >= 0; i--) { cnt = 0; os[i] = i; for (j = i; i < n; j++) { if (cnt == is[i]) { os[j] = i; break; } os[j] = os[j + 1]; cnt++; } } for (i = 1; i <= n; i++) printf("%d ", os[i]); return 0; } | cs |
확실히 정방향으로 짠 것보다 덜 복잡한 것 같다.
#. Other code
1. 8부터 처리
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 | #include<stdio.h> #include<vector> #include<algorithm> using namespace std; int main() { int n, i, j, pos; scanf("%d", &n); vector<int> is(n+1), os(n+1); for(i=1; i<=n; i++) scanf("%d", &is[i]); for(i=n; i>=1; i--){ pos=i; for(j=1; j<=is[i]; j++){ os[pos]=os[pos+1]; pos++; } os[pos]=i; } for(i=1; i<=n; i++) printf("%d ", os[i]); return 0; } | cs |
나는 count 를 사용하였고, 강사님은 position 을 사용하셨다.
결국은 같은 방법이긴 하지만, count 를 사용할 경우 계속 조건 연산을 해주어야 하므로 뭔가 position보다 비효율적인 것 같다.
position 은 딱 할만큼 하고 끝나는데 나는 계속 비교해주면서 true 일 경우 종료시키는 거니깐..
2. 정방향
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 | #include<bits/stdc++.h> using namespace std; int main(){ ios::sync_with_stdio(false); int n, tmp; cin>>n; vector<int> os(n); for(int i=0; i<n; i++){ cin>>tmp; for(int j=0; j<n; j++){ if(tmp==0 && os[j]==0){ os[j]=i+1; break; } else if(os[j]==0) tmp--; } } for(auto x : os) cout<<x<<" "; return 0; } | cs |
1부터 처리하는 경우도 내 코드보다 엄청 깔끔하다ㅠㅠ
또, inversion sequence vector를 따로 만들이 않고 입력과 동시에 처리해주고 있다.
line 17 을 보면 tmp 가 0이고 os[j] 도 0인 경우 os[j] 에 i+1; 을 입력해주고 반복문을 종료해주고 있다.
만일 os[j]가 0일 경우 tmp 를 1씩 줄여주고 그렇지 않을 경우는 pass 가 된다.
그래서 0이 아닌 다른 숫자가 있을 경우에는 tmp 값에 변화가 없다.
결국 0에는 자신보다 큰 숫자가 들어올 것이므로 0이 아닌 다른 숫자가 있을 경우 pass를 해준 것이다.
먼저 문제 이해를 제대로 하고 문제에 접근하는게 중요한 것 같다. . .
tmp = 5
0 0 0 0 0 1 0 0
tmp = 3
0 0 0 2 0 1 0 0
tmp = 4
0 0 0 2 0 1 3 0
tmp = 0
4 0 0 2 0 1 3 0
tmp = 2
4 0 0 2 5 1 3 0
...
#. Result
- Input --------------------------------------------------------
8
5 3 4 0 2 1 1 0
------------------------------------------------------------------
- Output --------------------------------------------------------
4 8 6 2 5 1 3 7
------------------------------------------------------------------
'PS > Problem_Solving' 카테고리의 다른 글
| [Inflearn] 연속된 자연수의 합 (0) | 2020.04.26 |
|---|---|
| [Inflearn] 두 배열 합치기 (0) | 2020.04.24 |
| [Inflearn] 3등의 성적은? (0) | 2020.04.23 |
| [Inflearn] 탄화수소 질량 (0) | 2020.04.23 |
| [Inflearn] 3의 개수는?(large) (0) | 2020.04.23 |