글 읽기 - 어디가 틀렸을까요..

jskim2023 6년 전 0

11 번째줄 std::ios_base::sync_with_stdio(false); 를 쓰면 틀리고, 안쓰면 시간초과 나는데용

일단 pair로 받은 다음에, 삽입정렬을 통해서 짰습니다.

테스트케이스도 돌아가구요..임의적으로 한 20개까지해서 해봣는데 정렬됩니다.

속도문제인거같아서 std::ios_base::sync_with_stdio(false); 썻는데 틀렸다고 나옵니다 ㅠ.ㅠ..

18~25

만약 비교대상보다 작다면, 위치 계속 옴겨주고요. 만약 같거나, 크다면, for문을 탈출해서 값을 넣어줍니다.

뒤에있는 값들을 순차적으로 삽입하기때문에, 값이 같을경우는 자연스래 뒤에 삽입되게 됩니다.

어느부분이..안된걸까요, 삽입정렬의 느린속도라면, 시간초과라고뜰텐데, 그건 안떠서..너무 헷갈립니다 .ㅠㅠ

#include <algorithm>
#include <iostream>
#include <string>

using namespace std;


int N;
pair<int, string> name[100000];
int main() {
	std::ios_base::sync_with_stdio(false);
	pair<int, string> a;
	scanf("%d", &N);
	int j;
	for (int i = 0; i < N; i++)
		cin >> name[i].first >> name[i].second;

	for (int i = 0; i < N; i++) {
		
		a = name[i];
		for (j = i - 1; j >= 0 && a.first < name[j].first; j--) {
			name[j + 1] = name[j];
		}
		name[j + 1] = a;
	}


	for (int i = 0; i < N; i++)
		cout << name[i].first << " "<< name[i].second << endl;
}

djm03178 6년 전 0

std::ios_base::sync_with_stdio(false); 를 한 뒤에는 stdio 계열과 iostream 계열을 섞어쓰면 안 됩니다. 즉, scanf와 cin을 같이 쓰면 안 됩니다. 마찬가지로 printf와 cout도 혼용하면 안 됩니다.

그리고 이걸 고치시더라도, 10만 개 원소를 O(n^2) 알고리즘으로는 시간 내에 풀 수 없으리라 생각합니다.

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

문제

문제

출처

ICPC

어디가 틀렸을까요..

jskim2023 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말