연결 리스트로 표현된 숫자에 1 더하기
이 글에서는 연결 리스트(Linked List)에 저장된 숫자에 1을 더하는 방법을 살펴보겠습니다. 연결 리스트에서는 숫자의 각 자릿수가 개별 노드에 저장됩니다. 예를 들어 숫자가 512라면 다음과 같은 형태로 표현됩니다.
512 = (5)-->(1)-->(2)-->NULL
증가(increment) 함수에 리스트를 전달하면, 함수는 1을 더한 결과를 담은 새로운 리스트를 반환합니다. 여기서는 C++ STL의 list 컨테이너를 사용하여 구현합니다. 동작 원리를 더 명확히 이해하기 위해 먼저 알고리즘부터 확인해 보겠습니다.
알고리즘
incrementList(l1)
시작
carry := 1 // 더할 값 1을 받아올림 변수로 초기화
res := 빈 리스트 생성
l1의 각 노드 n을 뒤에서 앞으로 스캔하며 반복:
item := (n의 값 + carry) mod 10
item을 res의 맨 앞에 삽입
carry := (n의 값 + carry) / 10
반복 종료
만약 carry가 0이 아니라면:
carry를 res의 맨 앞에 추가
조건문 종료
res 반환
끝
핵심 아이디어는 간단합니다. 리스트를 뒤에서부터(일의 자리부터) 순회하면서 각 자릿수에 받아올림(carry)을 더하고, 10으로 나눈 나머지를 결과 리스트의 앞쪽에 삽입합니다. 이 과정에서 발생하는 몫은 다음 자릿수로 넘어가는 받아올림이 됩니다. 모든 자릿수를 처리한 후에도 받아올림이 남아 있다면, 그 값을 결과 리스트의 맨 앞에 추가합니다.
C++ 구현 예제
#include<iostream>
#include<list>
using namespace std;
list<int> incListNum(list<int> l1){
list<int>::reverse_iterator it1 = l1.rbegin();
list<int> result;
int carry = 1; // 더할 값 1
while(it1 != l1.rend()){
result.push_front((*it1 + carry) % 10);
carry = (*it1 + carry) / 10;
it1++;
}
if(carry != 0){
result.push_front(carry);
}
return result;
}
list<int> numToList(int n){
list<int> numList;
while(n != 0){
numList.push_front(n % 10);
n /= 10;
}
return numList;
}
void displayListNum(list<int> numList){
for(list<int>::iterator it = numList.begin(); it != numList.end();
it++){
cout<<*it;
}
cout << endl;
}
int main() {
int n1 = 9999;
list<int> n1_list = numToList(n1);
list<int> res = incListNum(n1_list);
cout << "The number: "; displayListNum(n1_list);
cout << "Result: "; displayListNum(res);
}
위 코드에서 incListNum() 함수는 역방향 반복자(rbegin, rend)를 사용해 일의 자리부터 순차적으로 처리하며, push_front()를 통해 결과를 올바른 자릿수 순서로 유지합니다. 또한 numToList() 함수는 정수를 연결 리스트로 변환하고, displayListNum() 함수는 리스트에 저장된 숫자를 출력합니다.
실행 결과
The number: 9999
Result: 10000
실행 결과에서 볼 수 있듯이, 9999에 1을 더하면 모든 자릿수에서 받아올림이 연쇄적으로 발생하여 최종적으로 10000이 됩니다. 이처럼 가장 높은 자릿수에서도 받아올림이 남는 경우, 알고리즘의 마지막 단계에서 해당 값을 리스트 맨 앞에 추가함으로써 올바른 결과를 얻을 수 있습니다.