220104 TIL

PS 5문제

문제	문제 제목
1003	피보나치 함수
1676	팩토리얼 0의 개수
17219	비밀번호 찾기
1764	듣보잡
17626	Four Squares

• 1764 듣보잡

  듣지 못한 사람들이 입력으로 들어오고, 후에 보지 못한 사람들이 들어온다.
  여기서 듣도 보도 못한 사람(두 입력의 교집합)을 찾아야 하는데,

  처음에는 find 함수를 통해, 찾으려 했지만 시간 초과가 나왔다.
  이를 이진 탐색으로 수정하여 제출하니 시간 초과 없이 해결되었다.

  // 1764 듣보잡
  #include <bits/stdc++.h>
  using namespace std;
  
  vector<string> n, v;
  int x, y;
  string c;
  
  // 이진 탐색
  int f() {
      int start = 0;
      int end = x - 1;
  
      while (start <= end) {
          int mid = (start + end) / 2;
          if (n[mid] == c)
              return 1;
          else if (n[mid] < c)
              start = mid + 1;
          else if (n[mid] > c)
              end = mid - 1;
      }
      return 0;
  }
  
  int main() {
      ios::sync_with_stdio(0); cin.tie(0);
      cin >> x >> y;
      for (int i = 0; i < x; i++) {
          cin >> c;
          n.push_back(c);
      }
      sort(n.begin(), n.end());
      for (int i = 0; i < y; i++) {
          cin >> c;
          if(f()) v.push_back(c);
          // f함수 내에서 현재 입력된 인원이 듣지 못한 사람 리스트에 있는 지 확인
          // 있으면 벡터에 넣어주고 후에 출력
      }
      cout << v.size() << '\n';
      sort(v.begin(), v.end());
      for (auto i: v) cout << i << '\n';
  }

가변인자

printf는 매개변수의 개수가 정해지지 않은 함수로
매번 함수에 들어가는 인자의 개수가 변하는 것을 가변 인자variable argument ,
해당 함수를 가변 함수variadic function 이라 한다.

• stdarg.h
  가변 함수를 사용하려면 stdarg.h 헤더 파일에서 제공하는 매크로와 타입을 이용해야 한다.
  해당 매크로와 타입은 아래와 같다.

  • va_list
    가변 인자 목록 포인터
    

  • va_start(AP, LASTARG)
    가변 인자의 시작 주소를 AP(va_list형)에 초기화한다.

    LASTARG는 가변 인자 앞에 있는 고정 인수로, 메모리 상에 마지막 고정인수 다음에 가변인자가 위치하기 때문에 인자로 받는다.

    위 이유로 인해, 가변인자를 사용할 때는 앞에 고정 인자가 한 개 이상 있어야한다.

  • va_arg(AP, TYPE)
AP 포인터가 위치한 부분의 데이터를 TYPE의 크기만큼 읽어서 반환한다.
    

  • va_end(AP)
AP를 NULL 로 초기화 한다.(가변인자 사용이 끝났을 때, 실행)