[Programmers] #120863 - 다항식 더하기 [Java][C++][Python]

문제 링크

---

1. 아이디어

공백으로 토큰을 나누면 각 항은 x로 끝나는 일차항이거나 상수항 둘 중 하나다. 일차항의 계수와 상수항을 각각 누적한 뒤, 계수가 1이면 생략하고 상수항을 뒤에 두는 출력 규칙에 맞춰 문자열을 조립했다.

---

2. 복잡도

접근	시간	공간
풀이	$O(N)$	$O(N)$

($N$ = polynomial의 길이)

---

3. 코드

풀이 [Java][C++][Python]

import java.util.*;

class Solution {
    public String solution(String polynomial) {
        StringTokenizer st = new StringTokenizer(polynomial);
        int[] cnt = {0, 0};

        while (st.hasMoreTokens()) {
            String s = st.nextToken();
            if (s.equals("+")) continue;

            if (s.endsWith("x")) {
                if (s.length() == 1) {
                    cnt[0]++;
                } else {
                    cnt[0] += Integer.parseInt(s.substring(0, s.length() - 1));
                }
            } else {
                cnt[1] += Integer.parseInt(s);
            }
        }

        if (cnt[0] == 0) {
            return "" + cnt[1];
        } else if (cnt[1] == 0) {
            return (cnt[0] == 1 ? "" : cnt[0]) + "x";
        } else {
            return (cnt[0] == 1 ? "" : cnt[0]) + "x + " + cnt[1];
        }
    }
}

StringTokenizer를 활용해 공백을 기준으로 토큰을 나눈 후, +는 버리는 방식으로 필요한 토큰만 취했다.

#include <bits/stdc++.h>
using namespace std;

string solution(string polynomial) {
    stringstream ss(polynomial);
    string token;
    vector<int> cnt(2);

    while (ss >> token) {
        if (token == "+") continue;

        if (token.ends_with("x")) {
            if (token.size() == 1) {
                cnt[0]++;
            } else {
                cnt[0] += stoi(token.substr(0, token.size() - 1));
            }
        } else {
            cnt[1] += stoi(token);
        }
    }

    if (cnt[0] == 0) {
        return to_string(cnt[1]);
    } else if (cnt[1] == 0) {
        return (cnt[0] == 1 ? "" : to_string(cnt[0])) + "x";
    } else {
        return (cnt[0] == 1 ? "" : to_string(cnt[0])) + "x + " + to_string(cnt[1]);
    }
}

std::stringstream을 활용해 공백을 기준으로 토큰을 나눈 후, +는 버리는 방식으로 필요한 토큰만 취했다.

def solution(polynomial):
    cnt = [0, 0]
    for token in polynomial.split(" + "):
        if token.endswith("x"):
            cnt[0] += int(token[:-1] or 1)
        else:
            cnt[1] += int(token)

    res = []
    if cnt[0]:
        res.append("x" if cnt[0] == 1 else f"{cnt[0]}x")
    if cnt[1]:
        res.append(str(cnt[1]))

    return " + ".join(res)

split으로 각 항만 토큰으로 취했다.

---