처음 생각은, 카드를 입력받으면서 카드 개수도 같이 세주는 것을 생각했는데, 카드 개수를 세기 위해서는 매번 위치를 찾아야해서 여기서 시간초과가 계속 뜬 듯 하다. 해법은 이진탐색을 이용해서, 일단 입력 받은 후에, sortinng 하고 lowerboudn, upperbounnd찾는것.
내가 짠 코드
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> deck;
int N;
int upperBound(int value);
int lowerBound(int value);
int main(void){
int i,value,idx;
int upper,lower;
scanf("%d",&N);
for(i=0;i<N;i++){
scanf("%d",&value);
deck.push_back(value);
}
sort(deck.begin(),deck.end());
int M;
scanf("%d",&M);
for(i=0;i<M;i++){
scanf("%d",&value);
upper = upperBound(value);
lower = lowerBound(value);
if(deck[lower]==value){
idx = upper - lower + 1;
}
else idx = 0;
printf("%d ",idx);
}
printf("\n");
return 0;
}
int upperBound(int value){
int s,e,m;
s=0;
e=N-1;
while(e-s > 0){
m = (s+e)/2;
if(deck[m] <=value) s= m+1;
else e=m;
}
if(deck[e] !=value) e --;
return e;
}
int lowerBound(int value){
int s,e,m;
s=0;
e=N-1;
while(e-s > 0){
m = (s+e)/2;
if(deck[m] <value) s= m+1;
else e=m;
}
return e;
}
시간 초과 된 코드
C++ 의 map을 이용해서 접근했는데 시간초과가 뜬다. 이것이 뭔 일이람.
#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
int main(void){
int N,i,value;
scanf("%d",&N);
map <int, int> deck;
for(i=0;i<N;i++){
scanf("%d",&value);
if(deck.count(value)==0) deck.insert(make_pair(value,1));
else deck[value]++;
}
scanf("%d",&N);
for(i=0;i<N;i++){
scanf("%d",&value);
printf("%d ",deck[value]);
}
printf("\n");
return 0;
}
시간 초과 된 코드 2
C++ 벡터를 2개 사용해서 value, count값을 저장했는데 여전히 시간초과.
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(void){
int N,i,value,idx;
vector<int> deck;
vector<int> count;
vector<int>::iterator iter;
scanf("%d",&N);
for(i=0;i<N;i++){
scanf("%d",&value);
iter = find(deck.begin(),deck.end(),value);
if(iter<deck.end()){ //이미 있다면
idx = iter - deck.begin();
count[idx]++;
}
else {
deck.push_back(value);
count.push_back(1);
}
}
scanf("%d",&N);
for(i=0;i<N;i++){
scanf("%d",&value);
iter = find(deck.begin(),deck.end(),value);
if(iter<deck.end()){
idx = iter - deck.begin();
printf("%d ",count[idx]);
}
else printf("0 ");
}
printf("\n");
return 0;
}
10816번: 숫자 카드 2
첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,
www.acmicpc.net
'Problem Solving > 백준' 카테고리의 다른 글
[백준] 1406번: 에디터 (0) | 2021.02.24 |
---|---|
[백준] 9012: 괄호 (0) | 2021.02.24 |
[백준] 11651번 : 좌표 정렬하기 2 (0) | 2021.02.24 |
[백준] 1009: 분산처리 (0) | 2021.02.19 |
[백준] 1032: 명령 프롬프트 (0) | 2021.02.19 |