Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++에서 스택(Stack)을 활용해 숫자 뒤집기

정수 Num이 입력으로 주어졌을 때, 스택(Stack) 자료구조를 활용해 그 숫자를 뒤집은 값을 구하는 것이 이 글의 목표입니다.

스택(Stack)이란?

스택은 C++에서 데이터를 LIFO(Last In First Out, 후입선출) 방식으로 저장하는 자료구조입니다. 가장 나중에 넣은 데이터가 가장 먼저 나오는 구조이며, 주요 연산은 다음과 같습니다.

선언 방법: stack<int> stck; // stck가 스택 변수가 됩니다.

  • top() – 최상단 요소 확인: stck.top()은 스택의 가장 위에 있는 요소에 대한 참조를 반환합니다.

  • pop() – 최상단 요소 제거: 스택의 맨 위에 있는 요소를 제거합니다.

  • push() – 요소 추가: stck.push(value)는 값 value를 스택에 삽입합니다. value의 타입은 스택에 지정된 타입과 일치해야 합니다.

  • empty() – 빈 스택 확인: stck.empty()는 스택이 비어 있으면 true를 반환합니다.

예제

예제 1

입력 − Num = 33267

출력 − 숫자의 역순: 76233

설명 −

먼저 모든 자릿수를 스택에 push합니다.

7 - 6 - 2 - 3 - 3 ← top

꺼낸 자릿수에 자리값을 곱해 모두 더하면:

7 * 10000 + 6 * 1000 + 2 * 100 + 3 * 10 + 3 * 1
= 70000 + 6000 + 200 + 30 + 3
= 76233

예제 2

입력 − Num = 111000

출력 − 숫자의 역순: 111

설명 −

먼저 모든 자릿수를 스택에 push합니다.

0 - 0 - 0 - 1 - 1 - 1 ← top
0 * 100000 + 0 * 10000 + 0 * 1000 + 1 * 100 + 1 * 10 + 1 * 1
= 0 + 0 + 0 + 100 + 10 + 1
= 111

알고리즘 접근 방식

이 접근법에서는 입력 숫자를 10으로 나눈 나머지(일의 자릿수)를 스택에 push하고, 숫자를 10으로 나누며 0이 될 때까지 반복합니다. 이렇게 하면 스택의 top에 가장 높은 자릿수가 위치하게 되어, pop 순서대로 꺼내면 자연스럽게 뒤집힌 숫자가 완성됩니다.

단계별 과정

  1. 입력 숫자 Num을 받습니다.
  2. stack<int> stck;로 정수형 빈 스택을 선언합니다.
  3. 함수 pushDigts(int num1)는 num1을 받아 최상위 자릿수가 top에 오도록 스택을 채웁니다.
  4. 나머지를 저장할 변수 rem을 준비합니다.
  5. while 루프로 num1이 0이 아닌 동안 rem = num1 % 10을 계산합니다.
  6. rem을 스택에 push합니다.
  7. num1을 10으로 나누어 다음 자릿수를 처리합니다.
  8. revrseNum() 함수에서 스택의 요소들을 꺼내 역순 숫자를 조립합니다.
  9. 변수 revrs, topp, temp, i를 준비합니다.
  10. 스택이 비어 있지 않은 동안 반복합니다.
  11. topp = stck.top()으로 최상단 요소를 가져옵니다.
  12. stck.pop()으로 스택에서 요소를 제거합니다.
  13. temp = topp * i로 자리값을 곱합니다.
  14. temp를 revrs에 더합니다.
  15. i를 10배씩 증가시켜 다음 자릿수의 자리값을 만듭니다.
  16. 반복이 끝나면 입력 숫자의 역순 revrs를 반환합니다.
  17. main 함수에서 결과를 출력합니다.

구현 예시 (C++)

#include <bits/stdc++.h>
using namespace std;
stack <int> stck;
void pushDigts(int num1){
    int rem;
    while (num1 > 0){
        rem=num1 % 10;
        stck.push(rem);
        num1 = num1 / 10;
    }
}
int revrseNum(){
    int revrs = 0;
    int i = 1;
    int temp;
    int topp;
    while (!stck.empty()){
        topp=stck.top();
        stck.pop();
        temp=topp*i;
        revrs = revrs + temp;
        i *= 10;
    }
    return revrs;
}
int main(){
    int Num = 43556;
    pushDigts(Num);
    cout<<"Reverse of number is: "<<revrseNum();
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

Reverse of number is: 65534