숫자를 연결 리스트(Linked List)로 표현할 때는 리스트의 각 노드가 숫자의 한 자릿수를 담당하도록 구성합니다. 이때 첫 번째 노드에는 가장 큰 자릿수(최상위 자릿수)가 저장되고, 마지막 노드에는 가장 작은 자릿수(최하위 자릿수)가 저장됩니다. 예를 들어 숫자 202345는 연결 리스트로 (2→0→2→3→4→5)와 같이 표현됩니다.
이렇게 표현된 숫자에 1을 더하려면 가장 마지막 노드, 즉 최하위 자릿수부터 확인해야 합니다. 해당 값이 9보다 작다면 그대로 1만 더해주면 되지만, 9라면 올림(carry)이 발생하여 앞쪽 자릿수까지 차례대로 처리해야 합니다.
예를 들어 1999는 (1→9→9→9)로 표현되며, 여기에 1을 더하면 (2→0→0→0)이 되어야 합니다.
입력: 1999 출력: 2000
알고리즘 설명
연결 리스트로 표현된 숫자에 1을 더하는 과정은 다음 세 단계로 진행됩니다.
- 연결 리스트 뒤집기: 먼저 연결 리스트의 순서를 뒤집어 최하위 자릿수를 맨 앞으로 보냅니다. 예를 들어 1→9→9→9는 9→9→9→1로 변환됩니다.
- 올림 처리하며 1 더하기: 뒤집힌 리스트를 처음부터 순회하면서 맨 앞 노드에 1을 더합니다. 만약 해당 노드의 값이 9였다면 합이 10이 되므로 일의 자리는 0으로 바꾸고, 올림 1을 다음 노드로 전달합니다. 이 과정은 올림이 존재하는 동안 계속 반복됩니다.
- 다시 원래 순서로 뒤집기: 모든 계산이 끝나면 리스트를 다시 뒤집어 원래 형태로 복원한 뒤, 헤드(head) 노드를 반환하여 결과를 출력합니다.
C++ 구현 예제
아래는 위 알고리즘을 C++로 구현한 전체 코드입니다.
#include <iostream>
using namespace std;
// n=다음 노드 ; d=데이터 ; p=이전 노드; h=헤드 노드; c=현재 노드
class Node {
public:
int d;
Node* n;
};
Node *newNode(int d) {
Node *new_node = new Node;
new_node->d = d;
new_node->n = NULL;
return new_node;
}
Node *reverse(Node *h) {
Node * p = NULL;
Node * c = h;
Node * n;
while (c != NULL) {
n = c->n;
c->n = p;
p = c;
c = n;
}
return p;
}
Node *addOneUtil(Node *h) {
Node* res = h;
Node *temp, *p = NULL;
int carry = 1, sum;
while (h != NULL) {
sum = carry + h->d;
carry = (sum >= 10)? 1 : 0;
sum = sum % 10;
h->d = sum;
temp = h;
h = h->n;
}
if (carry > 0)
temp->n = newNode(carry);
return res;
}
Node* addOne(Node *h) {
h = reverse(h);
h = addOneUtil(h);
return reverse(h);
}
int main() {
Node *h = newNode(1);
h->n = newNode(9);
h->n->n = newNode(9);
h->n->n->n = newNode(9);
h = addOne(h);
while (h != NULL) {
cout << h->d;
h = h->n;
}
cout<<endl;
return 0;
}코드 동작 방식
addOne() 함수가 전체 흐름을 제어합니다. 먼저 reverse()로 리스트를 뒤집은 후, addOneUtil()에서 초기 올림 값을 1로 설정하고 각 노드를 순회하며 자릿수 합을 계산합니다. 모든 자릿수가 9여서 올림이 마지막까지 남아 있는 경우(예: 999 → 1000), 새로운 노드를 추가하여 자릿수를 확장합니다. 마지막으로 다시 한번 reverse()를 호출해 원래 순서를 복원합니다.
이 알고리즘의 시간 복잡도는 리스트를 최대 세 번 순회하므로 O(n)이며, 추가 공간 없이 노드 포인터만 조작하므로 공간 복잡도는 O(1)입니다.