inflearn logo
강의

講義

知識共有

10週間完成 C++ コーディングテスト | アルゴリズムコーディングテスト

3-N

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

解決済みの質問

363

heecheon920594

投稿した質問数 9

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++ 코딩-테스트

回答 2

1

kundol

안녕하세요 희천님 ㅎㅎ

나쁘지 않은 코드입니다.

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

 

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

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

 

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



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

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

감사합니다.

강사 큰돌 올림.


0

heecheon920594

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

0

heecheon920594

영상 주행했습니다.

 

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

코딩 살구 클럽 가입 요청 드립니다

0

50

2

코딩살구클럽 가입 요청드립니다.

0

45

2

코딩살구클럽 채점 안됨

0

51

2

4-O 채점 관련 질문

0

42

2

코딩살구클럽가입

0

42

2

코딩살구클럽 가입

0

62

2

비쥬얼 스튜디오로 해도 되나요?

0

57

2

코딩살구클럽 가입 문의

0

74

2

코딩 살구 클럽 컴파일 에러

0

55

3

추천 문제

0

43

2

코딩살구클럽 승인

0

58

2

코살구 1주차 1940번 문제 조건과 프라이빗 테스트 불일치 문의

0

42

2

문제를 고민하는 시간 관련

0

37

2

코딩살구클럽

0

49

2

코딩살구클럽 문의

0

58

2

코딩살구클럽 승인

0

47

2

DP 경우의 수 설명이 이해가 되지 않습니다.

0

43

2

3-F 채점 관련 질문

0

41

1

BFS, DFS 활용이 되는 상황에서의 방향성

0

43

2

코딩살구클럽 승인

0

50

2

코딩살구클럽승인

0

46

3

코딩살구클럽 승인

0

69

2

3-D 관련 질문

0

37

2

코살구 회원가입 문의

0

49

2