코드리뷰를 좀 받고싶은데 어떻게 올리는 게 좋은지 몰라서 무작정 올려봅니다 ..

    #include<cstdio>
    #include<cstdlib>
    #include<algorithm>
    using namespace std;
     
    int main(){
        int n, k;
        int *a, *operations, *counts;
        int min = 0x7FFFFFFF;
     
        scanf("%d %d", &n, &k);
     
        a = (int *)malloc(sizeof(int) * n);
        operations = (int *)calloc(200001, sizeof(int));
        counts = (int *)calloc(200001, sizeof(int));
     
        for(int i = 0; i < n; i++){
            scanf("%d", a + i);
            counts[a[i]] += 1;
        }
     
        sort(a, a + n);
     
        for(int i = 0; i < n; i++){
     
            int opers = 0;
     
            while(a[i]){
                int has_sufficient_count = (counts[a[i]] >= k);
                int needs_minimum_operations = (operations[a[i]] < min);
                
                min = (-(has_sufficient_count & needs_minimum_operations) & operations[a[i]])
                      + (-(!has_sufficient_count | !needs_minimum_operations) & min);
                      
                a[i] >>= 1;
                opers ++;
                has_sufficient_count = (counts[a[i]] >= k);
                needs_minimum_operations = (operations[a[i]] < min);
                
                operations[a[i]] += (-(!has_sufficient_count) & opers);
                counts[a[i]] += (!has_sufficient_count);
            }
        }
     
        if(operations[0] < min) min = operations[0];
     
        free(a);
        free(operations);
        free(counts);
     
        printf("%d", min);
     
        return 0;
     
    }

혹시 양식을 수정해야 한다면 고치겠습니다…

https://codeforces.com/contest/1213/problem/D2

이 문제의 답을 작성해보았습니다. 일단 accepted는 됐는데

더 나은 코드를 작성하고 싶어 코톡 분들께 조언을 구하고자 합니다.

개발자가 아니다보니 주변에 피드백 받을 곳이 없네요…ㅠ

취미 코딩러면 괜찮으신데요 ㅎ

Level 1 Review

  • n, k 등의 로컬 변수는 선언 즉시 초기화. 포인터는 즉시 nullptr로 초기화
  • has_sufficient_count, needs_minimum_operations : int -> bool
  • 변수명 adata라든가 numbers로 바꾸면 괜찮을 것 같음

Level 2 Review

  • C++면 malloc류 쓰지 마시고 std::vector
  • 음수인게 없으니 int 대신 size_t
  • using namespace std; 금지
  • min같은 변수명은 쓰지 말것. std::min()과 충돌남
  • printf, scanf 대신 std::cin, std::cout
  • C 스타일 헤더를 쓰지 말것
  • std::sort(std::begin(numbers), std::end(numbers));
  • 최소값 변수 초기화는 std::numeric_limits<size_t>::max()

Level 2.5 Review

  • return EXIT_SUCCESS;
  • assert로 n, k에 대한 범위 체크
  • (Optional) assert로 입력받는 원소들에 대한 범위 체크 및 예외 처리
  • 함수를 std::istream& 을 받는 함수로 extract 하고, main에서는 테스트 케이스에 대한 assert로 유닛 테스트 수행
4 Likes

와 정말 감사합니다.
비개발자로서 정말 꿀맛같은 피드백입니다.

질문이 있습니다.

Level1

1.로컬변수를 초기화 하는 이유는 무엇인가요? 

어차피 차후 스캔 받은 값을 사용할 건데, 초기화가 어떤 의미를 가지는지 궁급합니다.

  1. 사실 이 코드는 c로 처음에 작성되었습니다.
    근데 stdlib.h 에서 제공하는 qsort 함수가 특정 test case 수행시 worst case에 걸리는지, 시간초과가 발생하는 문제가 있었습니다.
    그래서 다른 부분은 다 그대로 두고, 오로지 c++의 sort 함수 하나를 위해 c++ 로 헤더를 바꿨습니다.
    이 경우에도 needs_minimum_operations 이런 변수는 bool 타입을 사용하는 것이 좋나요?
    또한, 위와 같은 변수는 비교문의 return value가 1 또는 0 임을 이용해 counts[a[i]] += (!has_sufficient_count); 이런 식의 tricky한 연산을 하는데 그럼에도 bool타입을 써야하는지 궁금합니다.

Level 2

  1. c++에서 c스타일 헤더, malloc, printf, scanf 등을 지양해야 하는 이유는 무엇인가요?

Level 2.5

  1. 유닛 테스트 부분은 무슨 말인지 잘 모르겠습니다ㅜㅜ. 혹시 예시를 좀 들어주실수 있으신가요?
  1. 초기화되지 않은 로컬 변수는 쓰레기 값을 가집니다. 스캔 받기 이전에 님이나 누군가가 그 변수를 잘못 접근한다면 (오타가 난다던가) 버그가 납니다. 최악인 것은 컴파일은 되기 때문에 컴파일 시점에서는 잘 되는 것처럼 착각하게 된다는 것입니다. (warning을 무시하는 개발자라면)

  2. C에서도 bool 타입을 제공합니다. C99에 추가되었으니 20년 전의 일입니다.

  3. C와 C++은 다른 언어입니다. C++의 가장 큰 강점은 RAII(초기화에서 리소스를 획득하고 객체 주기가 끝남과 동시에 리소스를 해제함) 입니다. malloc/calloc류는 free를 빼먹으면 큰일난다는 단점이 있습니다. free를 빼먹지 않아도 다음과 같은 경우에 문제가 됩니다.

// C (invalid in C++)
// X* x = malloc(sizeof X);

// C (valid in C++)
X* x2 = (X*) malloc(sizeof X);

// may return early or throw exception
if (x2->something()) return 1234;
if (x2->somethingelse()) throw std::invalid_argument("sucks");

// you may think you didn't forgot to free x2, but you're screwed
free(x2);

std::vector, std::fstream, std::scoped_lock같은 C++ 오브젝트들은 리소스 관리가 스코프에 의존하기 때문에 저런 문제가 없습니다. malloc류 쓰지 말라는 이유는 장점이 없기 때문입니다.

  1. printf, scanf를 쓰지 말아야 하는 이유는 타입 포매팅 때문입니다. 타입이 안 맞으면 undefined behavior (=버그) 납니다. 단 std::cin, std::coutprintf, scanf보다 느린데, 이것은 std::ios::sync_with_stdio(false)를 써서 해결할 수 있습니다. 단 이렇게 하면 C 스타일 IO를 쓰면 안되죠.

  2. 제출 전에 문제의 테스트 케이스를 assert로 돌려보라는 것입니다. 제출할 때에는 #define NDEBUG로 assert를 끄면 됩니다.
    assert(solve(테스트케이스1) == 테스트케이스1결과);

2 Likes

PS를 계속 하실 생각이시라면 C++을 익히는 것이 큰 도움이 됩니당

Malloc과 new의 차이점을 생각해보시기 바랍니다.

퍄엄청난피드백!

와 저도 들르면서 좋은 피드백 얻고갑니다. 잘 보고가요!