inflearn logo
강의

Course

Instructor

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

3-N

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

Resolved

363

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

영상 주행했습니다.

 

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

3-F 채점 관련 질문

0

4

0

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

0

8

2

코딩살구클럽 승인

0

15

2

코딩살구클럽승인

0

13

2

코딩살구클럽 승인

0

43

2

3-D 관련 질문

0

33

2

코살구 회원가입 문의

0

38

2

코살구 로그인 문제

0

60

2

3-A 문제 풀이 관련 질문

0

51

3

2-O 질문 있습니다

0

38

2

2-T 문제에 관한 질문

0

38

2

코딩 살구 클럽 접속 및 사용방법 문의

0

57

2

안녕하세요~. 현재 코살코딩클럽 사이트가 접속이 안됩니다~

0

64

2

코딩살구클럽 로그인문제

0

74

3

코딩 살구 클럽 로그인 문제

0

79

2

2-J 채점관련 질문

0

65

3

코딩 살구 클럽 Python 지원 가능 여부

0

77

1

살구클럽 아이디 없음 문제

0

76

1

1-O 코딩살구클럽 채점관련 질문

0

60

2

히든 테스트 케이스가 사라졌습니다

0

57

1

채점서버 혹시 다른 언어 지원도 가능하게 해주실 수 있나요

1

74

2

살구 클럽 채점 관련 문의(테스트 케이스)

0

66

2

1-H 문제 채점하기 오류

0

58

3

코딩살구클럽 2주차 2-L 문제 채점하기 오류

0

52

2