티스토리 뷰
#. Problem
* The copyright in this matter is in Inflearn
#. Resolution Process
1. Read and understand problem
2. Redefine the problem + abstract
- 10진수 N이 입력되면, K 진수루 변환하여 출력
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. N을 K로 나눈 나머지들을 쌓은 후 빼면서 출력하면 될 것 같다.
N=11, K=2 가 입력으로 주어졌을 때, 나머지를 stack에 쌓아준다
N%K = 1, N/2=5, stack[1]
N%K = 1, N/2=2, stack[1,1]
N%K = 0, N/2=1, 나머지가 0일 경우 몫을 먼저 stack에 쌓아준 후 나머지를 쌓아준다. stack[1,1,0,1]
이제 stack에서 하나씩 빼면서 출력해주면 된다.
단, 16진수일 경우에는 10 = A, 11 = B, 12 = C, 13 = D, 14 = E, 15 = F 로 치환해서 출력해주어야 한다.
#. Code
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 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; int main(void) { freopen("input.txt", "rt", stdin); int n, k, mod; scanf("%d %d", &n, &k); vector<int> vt; while (1) { mod = n % k; n /= k; vt.push_back(mod); if (n/k == 0) { vt.push_back(n); break; } } if (k == 16) { while (!vt.empty()) { int tmp = *(vt.end() - 1); if(tmp >= 10) printf("%c", tmp + 55); else printf("%d", tmp); vt.pop_back(); } } else { while (!vt.empty()) { printf("%d", *(vt.end() - 1)); vt.pop_back(); } } return 0; } | cs |
vector 를 사용해서 풀었고, 출력 부분에서 16진수일 경우만 따로 빼서 구현하였다.
모든 진수를 합쳐놓으면 16진수가 아님에도 계속 나머지가 10이상인지 비교해주어야 하기 때문이다.
--
강사님께서 stack을 직접구현해보라고 하셔서
다시 구현해보았다.
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 | #include <cstdio> #include <vector> #include <algorithm> using namespace std; int stack[1000]; int top; void push(int n) { stack[++top] = n; } int pop() { return stack[top--]; } int main(void) { freopen("input.txt", "rt", stdin); int n, k, mod; scanf("%d %d", &n, &k); top = -1; while (n) { mod = n % k; n /= k; push(mod); } if (k == 16) { while (top != -1) { int tmp = pop(); if (tmp >= 10) printf("%c", tmp + 55); else printf("%d", tmp); } } else { while (top != -1) printf("%d", pop()); } return 0; } | cs |
#. Other code
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 | #include<stdio.h> #include<vector> #include<algorithm> using namespace std; int stack[100], top=-1; void push(int x){ stack[++top]=x; } int pop(){ return stack[top--]; } int main(){ int n, k; char str[20]="0123456789ABCDEF"; scanf("%d %d", &n, &k); while(n>0){ push(n%k); n=n/k; } while(top!=-1){ printf("%c", str[pop()]); } return 0; } | cs |
우선 line 7) 전역변수에서 변수를 그냥 초기화했다.
나는 왜 굳이 main에서 따로 설정한거지..
그리고 line 19) char str 배열을 만드셔서 출력 시 나처럼 16진수일 경우와 아닐경우 따로 출력하는 일이 생기지 않도록 하셨다.
정말 좋은 방법이다. 훨씬 코드가 간결해졌다..
그리고 line 24) mod 변수도 따로 만들지 않고 나머지를 바로 push 처리해주었다.
나는 대체 어떻게 짠 거지.. 라는 생각이 들 정도로 띠용하다..
--
다음은 stack 으로 구현한 코드이다.
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 | #include<stdio.h> #include<vector> #include<stack> #include<algorithm> using namespace std; int main(){ int n, k; stack<int> s; char str[20]="0123456789ABCDEF"; scanf("%d %d", &n, &k); while(n>0){ s.push(n%k); n=n/k; } while(!s.empty()){ printf("%c", str[s.top()]); s.pop(); } return 0; } | cs |
직접 구현한 것과 비슷하지만 stack의 경우 pop() 함수가 제일 위에 있는 원소를 빼내기만할 뿐 참조를 해주지 않는다.
그래서 top() 함수로 stack의 제일 위에 있는 원소를 return 받고 pop() 함수로 빼내주면 된다.
#. Result
- Input --------------------------------------------------------
11 2
31 16
------------------------------------------------------------------
- Output --------------------------------------------------------
1011
1F
------------------------------------------------------------------
'PS > Problem_Solving' 카테고리의 다른 글
| [Inflearn] 기차운행 (0) | 2020.04.29 |
|---|---|
| [Inflearn] 올바른 괄호(stack) (0) | 2020.04.29 |
| [Inflearn] 블록의 최댓값 (0) | 2020.04.28 |
| [Inflearn] 각 행의 평균과 가장 가까운 값 (0) | 2020.04.28 |
| [Inflearn] 봉우리 (0) | 2020.04.28 |