글 읽기 - 시간초과 좀 부탁드립니다.

khseob0715 6년 전 0

어떻게 고쳐야 될까요............

아니면 아예 새로 짜는게 빠를까요?

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int main(){
	int a,b,num;
	vector<int> v;
	cin >> a >> b;
	while(--b){
		cin >> num;
		for(int i = 0 ; i < v.size(); i++){
			if(v.at(i) == num){
				v.erase(remove(v.begin(),v.end(),num));
				break;
			}
		}
		v.push_back(num);
	}
	for(int i = 0 ; i < a ; i++){
		cout << v.at(i) << '\n';
	}
}

AIAI 6년 전 1

Line 12:16 구간이 비효율적입니다. 아래 2부분에서 개선이 가능하겠습니다.

1. num이 기존 vector v내에 있는지 찾기 위해 linear search하는 것.

2. 위의 1에서 찾은 element를 삭제하기 위해 v.erase를 사용하는 것.

khseob0715 6년 전 0

@AIAI

말씀해주신게

1, 2번처럼 바꾸라는게 아니라

제 소스가 1,2 번 내용처럼 되어있으니까

고치라는 말씀이시죠?

그리고 아래 소스처럼 바꿔봐도 안되는데

선형탐색 말고 다른 방법을 써야 되는것 인가요?

	for(int i = 0 ; i < v.size(); i++){
			if(v.at(i) == num){
				v.erase(v.begin()+i);
				break;
			}
		}

AIAI 6년 전 1

네, 현재 작성하신 코드가 1, 2번 내용처럼 되어 있는 상태이기 때문에 map과 같이 log(n)에 검색할 수 있는 자료구조를 쓰시면 손쉽게 해결이 되지 않나 싶습니다.

khseob0715 6년 전 0

@AIAI

도와주세요 ㅠㅠ

제가 map을 오늘 처음 보는데요..

일단 아래와 같이 작성하였습니다.

막상 출력해보면 순서가 섞여있는데...왜 그런걸까요.....

#include<iostream>
#include<algorithm>
#include<map>
#include<string>
using namespace std;

int main()
{
	int a,b;
	string num;
	map<string, string> dic;
	map<string, string>::iterator it;

	cin >> a >> b;

	while(b--){
		cin >> num;
		it = dic.find(num);

		if(it != dic.end())	{
			dic.erase(it);
		}
		dic.insert(make_pair(num,num));
	}
	it = dic.begin();

	while(a--){
		string res = it->first;
		cout << res << '\n';
		it++;
	}
}

map 관련 자료를 좀 더 찾아보시면 좋을 것 같습니다.

map<key, value>을 iterator를 사용하셔서 접근하시게되면, insert한 순서가 아닌 key의 order순으로 정렬되어 나옵니다. 때문에 우리가 원하는 수강신청한 학생 순으로 결과를 뽑으시려면 입력한 순서를 저장해둬야 합니다. 그리고 string이 아닌 int 형으로도 충분히 모두 처리가능합니다. 이 문제에서 map을 사용하시는 목적은, 어떤 학생이 중복되어 등장하는지 여부를 체크하는 것으로 충분합니다.

khseob0715 6년 전 0

열심히 더 공부해보도록 하겠습니다.

조언 감사합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과 좀 부탁드립니다.

khseob0715 6년 전 0

AIAI 6년 전 1

khseob0715 6년 전 0

AIAI 6년 전 1

khseob0715 6년 전 0

AIAI 6년 전 1

khseob0715 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말