프로그래머스 - 카카오 2018 블라인드 테스트 (추석 트래픽)

문제는 시작, 끝 시간으로 구성된 여러개의 시간 구간들이 주어진다. 

 

그리고 임의의 1초 구간 동안  동시에 시간 구간이 몇개나 최대로 같이 있는지 구해보라는 것이다.

 

시간 구간은 2000개가 주어지니까 n^2도 문제 없다.

 

내가 생각한 구현은 시작 , 끝 구간 시간들 쭉 저장하고, 그것을 순회하면서 이 사이에 있는 타임라인들의 수를 구하고 그 최대를 구한다.

 

시간의 범위는 9월15일 00:00:00.000 ~ 23:59:59.999 인듯? 그냥 int로 변환해서 저장하면 될듯

 

근데 문제가 시간을 못 더하겠다.....음 ....

 

 

1.181 -> 이게 string인데 어떻게 바꾸지.

 

 

해결하려 한 부분들

1. 소수 문자열을 -> 실제 소수로 변환 -> 근데 float ,double은 밑에 부분이 잘려서 그냥 int로 변환

2. 시작 시간 끝 시간을 계산함 -> 주어진건 끝 시간 거기서 999를 빼야 시작 시간.

 

2-1. 문제는 60분법이라 그냥 뺐더니 틀렸다. 그래서 이걸 100분법으로 바꿔야 될거 같다.

음 바꿨는데도 틀렸다. 테케는 맞는데 답이 틀림...68점

 

 

#include <string>
#include <vector>
#include <iostream>
#include<string>
#include<cstdio>

using namespace std;
using ll = pair<int,int>;
vector<ll> vec;

double Left = 240000000 ,Right =0;

int getUnixTime(int x) {
	int below = x % 1000;
	int up = x/ 1000;
	int ans = 0;
	int tmp = 0;
	string s = to_string(up);

	if (s.size() < 6) {
		string temp;
		for (int i = 0; i < 6 - s.size(); i++) {
			temp.push_back('0');
		}
		temp += s;
		s = temp;
	}
	

	string twodigit="";
	//cout << s << "\n";
	
	twodigit.push_back(s[4]);
	twodigit.push_back(s[5]);

	//cout << twodigit << "\n";
	tmp = stoi(twodigit);
	ans += tmp;
	twodigit.clear();

	twodigit.push_back(s[2]);
	twodigit.push_back(s[3]);
	tmp = stoi(twodigit) * 60;
	ans += tmp;
	twodigit.clear();

	twodigit.push_back(s[0]);
	twodigit.push_back(s[1]);
	tmp = stoi(twodigit) * 3600;
	ans += tmp;
	twodigit.clear();
	
	ans = ans * 1000;
	ans += below;

	return ans;
}


int sTof(string s) {
	double ans = 0;
	bool pointFlag = 0;
	string tmp="";
	double exp = 10;

	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '.') {
			ans += stof(tmp);
			pointFlag = 1;
			continue;
		}

		if (pointFlag == 0) {
			tmp.push_back(s[i]);
		}
		else
		{
			ans += (s[i] - '0') / exp;
			exp = exp * 10.0f;
		}



		if (pointFlag == 0 && i == s.size() - 1) {
			ans += stof(tmp);
		}
	}

	ans = ans * 1000.0f;
	return ans;
}

int solution(vector<string> lines) {
	int answer = 0;

	for (int i = 0; i < lines.size(); i++) {
		//2016-09-15 20:59:57.421 0.351s
		//0123456789 
		string st = lines[i].substr(11, 12);
		string dt = lines[i].substr(24, lines[i].size() - 24 - 1);

		string st2;
		string term;

		for (int i = 0; i < st.size(); i++) {
			if (st[i] >= '0' && st[i] <= '9')
				st2.push_back(st[i]);
		}

		for (int i = 0; i < dt.size(); i++) {
			
			term.push_back(dt[i]);
		}

		

		int terms = sTof(term);
		//terms = getUnixTime(terms);

		int dt3 = stoi(st2);

		dt3 = getUnixTime(dt3);
		int st3;
		if (dt3 - terms + 1 > 0)
			st3 = dt3 - terms + 1;
		else {
			st3 = 0;
		}
		

		if (Left > st3) {
			Left = st3;
		}
		if (Right < dt3) {
			Right = dt3;
		}

		vec.push_back(ll(st3, dt3));

	}

	
	int onesec = 999;

	vector<int> borders;
	for (int i = 0; i < vec.size(); i++) {
		borders.push_back(vec[i].first);
		borders.push_back(vec[i].second);
	}
	
	for (int i = 0; i < borders.size();i++) {
		int cnt = 0;
		int lval = borders[i];


		for (int j = 0; j < vec.size(); j++) {
			
			if (( vec[j].first<= lval &&  lval <= vec[j].second) || (vec[j].first <= lval+onesec && lval+onesec <= vec[j].second  )) {
				//cout << lval << " " << vec[j].first << " " << vec[j].second << " " << lval+ onesec <<"\n";
				cnt++;
			}
		}
		if (answer < cnt) {
			answer = cnt;
		}

	}				


	return answer;
}

 

음 첨부터 구분자를 사용해서 시간을 절대 값으로 딱 구하는게 좋을거 같다. 지금 방식은 코드가 길어져서 중간에 뭐가 틀린듯??아... 왜틀렸ㅈ...

 

이유를 알았다.

이 그림에서 회색 트래픽이 빨간색인 1초 안에 들어오면 내 기존의 코드는 확인을 못했다. 그래서 그 조건을 추가해 주었다. 그랬더니 맞음 ㅎㅎ .

 

#include <string>
#include <vector>
#include <iostream>
#include<string>
#include<cstdio>

using namespace std;
using ll = pair<int, int>;
vector<ll> vec;

double Left = 240000000, Right = 0;

int getUnixTime(int x) {
	int below = x % 1000;
	int up = x / 1000;
	int ans = 0;
	int tmp = 0;
	string s = to_string(up);

	if (s.size() < 6) {
		string temp;
		for (int i = 0; i < 6 - s.size(); i++) {
			temp.push_back('0');
		}
		temp += s;
		s = temp;
	}


	string twodigit = "";
	//cout << s << "\n";

	twodigit.push_back(s[4]);
	twodigit.push_back(s[5]);

	//cout << twodigit << "\n";
	tmp = stoi(twodigit);
	ans += tmp;
	twodigit.clear();

	twodigit.push_back(s[2]);
	twodigit.push_back(s[3]);
	tmp = stoi(twodigit) * 60;
	ans += tmp;
	twodigit.clear();

	twodigit.push_back(s[0]);
	twodigit.push_back(s[1]);
	tmp = stoi(twodigit) * 3600;
	ans += tmp;
	twodigit.clear();

	ans = ans * 1000;
	ans += below;

	return ans;
}


int sTof(string s) {
	double ans = 0;
	bool pointFlag = 0;
	string tmp = "";
	double exp = 10;

	for (int i = 0; i < s.size(); i++) {
		if (s[i] == '.') {
			ans += stof(tmp);
			pointFlag = 1;
			continue;
		}

		if (pointFlag == 0) {
			tmp.push_back(s[i]);
		}
		else
		{
			ans += (s[i] - '0') / exp;
			exp = exp * 10.0f;
		}



		if (pointFlag == 0 && i == s.size() - 1) {
			ans += stof(tmp);
		}
	}

	ans = ans * 1000.0f;
	return ans;
}

int solution(vector<string> lines) {
	int answer = 0;

	for (int i = 0; i < lines.size(); i++) {
		//2016-09-15 20:59:57.421 0.351s
		//0123456789 
		string st = lines[i].substr(11, 12);
		string dt = lines[i].substr(24, lines[i].size() - 24 - 1);

		string st2;
		string term;

		for (int i = 0; i < st.size(); i++) {
			if (st[i] >= '0' && st[i] <= '9')
				st2.push_back(st[i]);
		}

		for (int i = 0; i < dt.size(); i++) {

			term.push_back(dt[i]);
		}



		int terms = sTof(term);
		//terms = getUnixTime(terms);

		int dt3 = stoi(st2);

		dt3 = getUnixTime(dt3);
		int st3;
		if (dt3 - terms + 1 > 0)
			st3 = dt3 - terms + 1;
		else {
			st3 = 0;
		}


		if (Left > st3) {
			Left = st3;
		}
		if (Right < dt3) {
			Right = dt3;
		}

		vec.push_back(ll(st3, dt3));

	}


	int onesec = 999;

	vector<int> borders;
	for (int i = 0; i < vec.size(); i++) {
		borders.push_back(vec[i].first);
		borders.push_back(vec[i].second);
	}

	for (int i = 0; i < borders.size(); i++) {
		int cnt = 0;
		int lval = borders[i];


		for (int j = 0; j < vec.size(); j++) {

			if ( (lval <= vec[j].first && vec[j].second<= lval +onesec) || (vec[j].first <= lval && lval <= vec[j].second) || (vec[j].first <= lval + onesec && lval + onesec <= vec[j].second)) {
				//cout << lval << " " << vec[j].first << " " << vec[j].second << " " << lval+ onesec <<"\n";
				cnt++;
			}
		}
		if (answer < cnt) {
			answer = cnt;
		}

	}


	return answer;
}

 

조건에 대해 항상 2% 부족하게 구현하는 이유는 뭘까.....

그리고 : 기준으로 시간을 분할하는게 더 좋았을거 같다.

 

다른 사람 풀이는 st~dt사이의 1000ms를 buff[시간대 전부]를 그냥 1씩 추가해서 시간대 중에서 최대 값을 구했다.