6-G 게임을 map으로 시도했습니다
337
작성한 질문수 7
안녕하세요 큰돌님.
이분탐색 대신 map을 활용해서 풀어봤는데 반례를 찾을 수가 없네요 ㅠㅠㅠ
어떤 부분이 잘못된건가요?
감사합니다.
#include <bits/stdc++.h>
using namespace std;
int T;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> T;
while(T--){
map<int, int> diary;
int N, M, tmp;
cin >> N;
for(int i = 0 ; i < N ; i++){ cin >> tmp; diary[tmp]++;}
cin >> M;
for(int i = 0 ; i < M ; i++){
cin >> tmp;
diary[tmp]++;
if(diary[tmp]>=2){
cout << 1 << '\n';
diary[tmp]--;
}else{
cout << 0 << '\n';
}
}
}
return 0;
}
답변 1
1
안녕하세요 태승님 ㅎㅎ
먼저 게임이 아니라 암기왕이겠죠? ㅎㅎ
일단 생각자체는 훌륭하고 좋습니다.
태승님이 생각하시는것은 아마 이런코드가 아닐까요? (조금 고쳐봤습니다. )
#include <bits/stdc++.h>
using namespace std;
int T;
int main(){
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> T;
while(T--){
map<int, int> diary;
int N, M, tmp;
cin >> N;
for(int i = 0 ; i < N ; i++){ cin >> tmp; diary[tmp]++;}
cin >> M;
for(int i = 0 ; i < M ; i++){
cin >> tmp;
if(diary[tmp] >= 1){
cout << 1 << '\n';
}else{
cout << 0 << '\n';
}
}
}
return 0;
}로직자체는 괜찮습니다.
나무랄데 없지요.
근데 이렇게 제출하면 시간초과가 뜹니다.
왜냐하면 map에다 집어넣게 되면 자동적으로 정렬이 들어가게 되는데 이 때문에 그런거 같아요.
즉,
for(int i = 0 ; i < N ; i++){ cin >> tmp; diary[tmp]++;}이 때마다 정렬하게 되고 N * O(logN)의 시간이 발생하니까 해답코드와는 그차이가 아닌가 싶습니다.
for(int i = 0 ; i < M ; i++){
cin >> tmp;
if(diary[tmp] >= 1){
cout << 1 << '\n';
}else{
cout << 0 << '\n';
}
물론 앞의 코드는 이분탐색과 동일한 시간복잡도를 갖는 코드구요.
감사합니다.
4 - A
0
25
2
코딩살구클럽 입장이 안됩니다
0
64
2
4-F 경우의 수 질문입니다.
0
32
2
코딩살구클럽 가입이 안됩니다.
0
75
2
살구 클럽에 대한 질문있습ㄴ디ㅏ
0
55
1
교안 158페이지 문의드립니다
0
44
2
코딩살구클럽 관련 건의사항
0
116
1
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
44
1
진행 방법 질문드립니다!
0
81
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
63
2
2주차 개념#12 트리 순회
0
32
2
백준사이트가 종료된다고 합니다.
0
316
2
백준 서비스 종료
9
951
1
sk 하이닉스 코테 대비
0
385
2
3-G 최댓값 질문
0
54
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
84
2
3-I 코드 질문드립니다.
0
65
2
3-N 질문 있습니다.
0
68
2
학습방법
0
105
2
4-H 질문 있습니다 (코드 리뷰)
0
69
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
183
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
72
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
65
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
53
2