Should I change my proposed solution for paper rejected because of lack of novelty or originality? From my understanding of the reviewers' comments, it means our proposed solution adds nothing new to the body of knowledge even if we get better results than the state-of-the-art work.

The reviewers believe our work is just an application of existing literature. While many published works do integration + per-existence method to enhance the result, we use pre-processing + per-existence method to do the same. We were rejected, while others were accepted.

Any advice is appreciated.
Lack of Novelty is an ill-defined statement. If you and your co-authors believe the manuscript has good contributions (compared to similar papers in the field) then probably the reviewers are just not expert in the area and thus thought of your work as marginal contribution. I would suggest addressing the reviewers comments to your best and submitting to a new venue.