강의

멘토링

커뮤니티

Cộng đồng Hỏi & Đáp của Inflearn

Hình ảnh hồ sơ của spqjdl68338908
spqjdl68338908

câu hỏi đã được viết

Hoàn thành C++ Coding Test trong 10 tuần | Thuật toán Coding Test

[Khái niệm cơ bản] Hàm split()

백준 1152질문

Viết

·

525

0

선생님 눈뜨고쓸정도로 스플릿외워서 이때다싶어 사용했습니다만 바로 시간초과가 뜨네요 ㅜ

http://boj.kr/c6c01ff909ca445dbb0b4a283faf9b02

이게 제가 한 링크고

#include <bits/stdc++.h>

using namespace std;

int main() {

string s;

int a = 1;

getline(cin, s);

for (int i = 0; i < s.length(); i++) {

if (isspace(s[i])) {

if (s.length() == 1) { cout << 0; return 0;}

else if (i > 0 && isspace(s[i - 1])) { cout << 0; return 0;}

else if (i == 0 || i == s.length() - 1) continue;

else a++;

}

}

cout << a;

return 0;

}

이건 통과되는 다른사람껀데 아무리봐도 이해가 잘 안되네요 ㅜㅜ 알려주십셔

c++코딩-테스트

Câu trả lời 2

0

spqjdl68338908님의 프로필 이미지
spqjdl68338908
Người đặt câu hỏi

감사합니다 주의하겠습니다!

0

kundol님의 프로필 이미지
kundol
Người chia sẻ kiến thức

안녕하세요 ㅎㅅ님 ㅎㅎ

강의 외의 문제에 대한 질문은 받지 않습니다.

그래도 이번만은 알려드리겠습니다.

split은 이처럼 find() 가 계속해서 있는 함수입니다. 즉, 해당 문자열을 계속해서 찾는 연산이 들어가게 되는데 이 시간복잡도가 O(N)입니다.

	string token = "";
	while((pos = input.find(delimiter)) != string::npos){

근데 이 문제의 최대 문자열의 길이는 100만이기 때문에 100만짜리를 계속해서 찾기 때문에 시간초과가 뜨는 것입니다.

이 문제는 그냥 띄어쓰기만을 찾으면 되고 그러한 로직이라면 해당 문자열을 한번만 순회하면 되는 식의 코드를 구축하는게 가장 효율적입니다.

 

감사합니다.

Hình ảnh hồ sơ của spqjdl68338908
spqjdl68338908

câu hỏi đã được viết

Đặt câu hỏi