3-N 비효율적으로 풀었는데 이렇게 접근해도 되나요?
안녕하세요 큰돌님,
다름이 아니고 3-N 완전이진 트리문제 이거 정석적인 방법이 잘 안떠올라서 무식하게 풀었는데 이렇게 풀어도 괜찮은가요?
항상 문제 먼저 풀어보고 안풀리면 큰돌님 영상보는 식으로 학습중이거든요.... 이번에는 영상 보기전에 풀어서 통과가 되었지만 이런 방식으로 문제에 접근해도 괜찮은 건지 여쭙니다.
#include <bits/stdc++.h>
using namespace std;
int K, ksize, input;
vector<vector<int>> result;
vector<int> v;
int main()
{
cin >> K;
ksize = pow(2, K) - 1;
for (int i = 0; i < ksize; ++i)
{
cin >> input;
v.push_back(input);
}
while (v.size())
{
vector<int> temp;
for (int i = 0; i < v.size(); i += 2)
{
temp.push_back(v[i]);
}
result.push_back(temp);
for (int i = v.size() - 1; i >= 0; i--)
{
if (i % 2 == 0)
{
v.erase(v.begin() + i);
}
}
}
for (auto i = result.rbegin(); i != result.rend(); ++i)
{
for (const auto &n : *i)
{
cout << n << ' ';
}
cout << '\n';
}
return 0;
}
Answer 2
1
안녕하세요 희천님 ㅎㅎ
나쁘지 않은 코드입니다.
다만 코드 리뷰를 드리면요.
계속해서 벡터삭제가 발생 : 이거 O(N)의 시간복잡도가 계속 소모가 됩니다.
if (i % 2 == 0)
{
v.erase(v.begin() + i);
}
이것 말고는 괜찮은 것 같습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
코살에 19942 다이어트 문제에 N의 범위가 빠져있슴니다
0
1
0
진행 방법 질문드립니다!
0
30
2
2-I) 왜 이 문제가 그래프이론 카테고리에 있는지 잘 모르겠습니다.
0
55
2
2주차 개념#12 트리 순회
0
25
2
백준사이트가 종료된다고 합니다.
0
284
2
백준 서비스 종료
9
882
1
sk 하이닉스 코테 대비
0
367
2
3-G 최댓값 질문
0
50
1
모듈러 연산 값이 10이 아닌 경우도 있지 않나요?
0
83
2
3-I 코드 질문드립니다.
0
62
2
3-N 질문 있습니다.
0
66
2
학습방법
0
102
2
4-H 질문 있습니다 (코드 리뷰)
0
66
2
코딩테스트 어디까지 준비해야 하는지 질문이 있습니다.
0
169
2
2-O 반례가 무엇일지 어떤 부분이 틀렸는지 잘 모르겠습니다.
0
69
2
2주차 개념 #4-2. 인접행렬 질문있습니다.
0
64
2
1-A 문제풀이 후 궁금한 점이 생겨서 질문드립니다.
0
51
2
조합 재귀 풀이 확인 해주시면 감사하겠습니다.
0
68
2
함수별 시간복잡도
0
73
2
3-h 질문입니다.
0
49
1
안녕하세요 선생님. 시간 복잡도 4번 질문있습니다.
0
53
2
1-I 문제 질문 드립니다.
0
76
2
2-P 질문입니다.
0
56
1
mac에서 시작하기 관련
0
91
2

