inflearn logo
강의

Course

Instructor

10-Week Completion C++ Coding Test | Algorithm Coding Test

3-N

3-N 비효율적으로 풀었는데 이렇게 접근해도 되나요?

Resolved

359

heecheon920594

9 asked

0

안녕하세요 큰돌님,

다름이 아니고 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;
}

c++ 코딩-테스트

Answer 2

1

kundol

안녕하세요 희천님 ㅎㅎ

나쁘지 않은 코드입니다.

다만 코드 리뷰를 드리면요.

 

계속해서 벡터삭제가 발생 : 이거 O(N)의 시간복잡도가 계속 소모가 됩니다.

      if (i % 2 == 0)
      {
        v.erase(v.begin() + i);
      }

 

이것 말고는 괜찮은 것 같습니다.



또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.


0

heecheon920594

작은 피드백도 감사합니다. 큰돌님의 방식으로 다시 학습해볼게요!

0

heecheon920594

영상 주행했습니다.

 

위 풀이대로 풀면 입력 사이즈 커지면 바로 짤이겠네요 ㅠㅠ

코살에 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