[Programmers] 최댓값과 최솟값 (C++) with 문자열 파싱 (토큰 분리)

https://school.programmers.co.kr/learn/courses/30/lessons/12939

프로그래머스

걸린 시간 : 8분 29초

---

문자열 파싱을 위한 split 함수를 공부하기 위해 푼 문제이다.

C++은 Python이나 Java와 같이 다른 언어와 달리 토큰분리를 간단하게 할 수 있는 라이브러리 함수를 제공하지 않아 스스로 만들어서 쓰면 좋다.

알고리즘

#include <sstream>을 해준 후, 문자열에서 stringstream을 생성해 getline 함수로 토큰분리를 한다. 밑의 함수를 통째로 외우는 것도 좋을 것 같다.

vector<string> split (string input, char delimeter) {
    vector<string> answer;
    stringstream ss(input);
    string tmp;
    while (getline(ss, tmp, delimeter)) {
        answer.push_back(tmp);
    }
    return answer;
}

• 선언 3개와 while문 1개이다. while문의 getline 에는 파라미터로 source, target, delimeter가 들어간다고 생각하면 된다.

 

그리고 나는 코드에서 정렬을 한 후 첫 원소와 마지막 원소를 빼서 썼지만, 이는 O(NlogN)의 시간 복잡도를 가진다. 최댓값 최솟값만을 구하는 코드를 작성하면 O(N)에 해결된다. 시간적으로 좋지 않은 코드이지만 효율성 테스트가 없어 간단하게 작성했다.

정답 코드

#include <string>
#include <vector>
#include <sstream>
#include <algorithm>
 
using namespace std;
 
vector<string> split (string input, char delimeter) {
    vector<string> answer;
    stringstream ss(input);
    string tmp;
    while (getline(ss, tmp, delimeter)) {
        answer.push_back(tmp);
    }
    return answer;
}
 
string solution(string s) {
    vector<string> stringarr = split(s, ' ');
    vector<int> intarr;
    for (string str : stringarr) {
        intarr.push_back(stoi(str));
    }
    sort(intarr.begin(), intarr.end());
    string answer = to_string(intarr.front()) + " " + to_string(intarr.back());
    return answer;
}