PS#5 오늘의PS

pengooseDev·2023년 6월 8일

10799 10845 11279 11286 1158 1927 26043 4889 백준

오늘의 문제

오늘도 준아님이 맛깔난 문제들을 던져주셨다.
C++로 오늘까지 다 풀어오는게 숙제!

Queue

요세푸스

길이가 N인 수열에서 K번째 element를 제거하는 과정을 반복하는 방식이다.
아래의 사진은 N = 41, K = 2인 요세푸스 순열이다.

간단한 구현문제이다. N - 1만큼 queue의 front값을 pop하여 rear로 옮긴 뒤, K번째 수를 출력하면 되는 문제이다.
순서를 몇 번 나열해보면 금방 로직이 보이는 간단한 구현문제다.

/*
1 2 3 4 5 6 7

2 3 4 5 6 7 1
3 4 5 6 7 1 2
pop!
4 5 6 7 1 2

... queue가 빌때까지 반복!
*/

#include <iostream>
#include <queue>
using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N, K;
  cin >> N >> K;

  queue<int> q;
  for (int i = 1; i <= N; i++)
    q.push(i);

  cout << "<";

  while (!q.empty())
  {
    for (int i = 1; i < K; i++)
    {
      int front = q.front();
      q.pop();
      q.push(front);
    }

    cout << q.front();
    q.pop();

    if (!q.empty())
      cout << ", ";
  }

  cout << ">" << endl;

  return 0;
}

큐

이 문제도 간단한 구현 문제이다. 요구사항에 맞게 구현하면 간단하게 통과하는 문제이다.
JS에서 class로 직접 구현하다가 이렇게 제공해주는 자료구조를 쓰니 너무 간편한 것 같다.. 🥳

#include <iostream>
#include <queue>
#include <string>
using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N;
  cin >> N;

  queue<int> q;

  for (int i = 0; i < N; i++)
  {
    string command;
    cin >> command;

    if (command == "push")
    {
      int value;
      cin >> value;
      q.push(value);
      continue;
    }

    if (command == "pop")
    {
      int res;
      if (q.empty())
        cout << "-1"
             << "\n";
      else
      {
        cout << q.front() << "\n";
        q.pop();
      }

      continue;
    }

    if (command == "size")
    {
      cout << q.size() << "\n";
      continue;
    }

    if (command == "empty")
    {
      cout << q.empty() << "\n";
      continue;
    }

    if (command == "front")
    {
      if (q.empty())
      {
        cout << "-1"
             << "\n";
        continue;
      }

      cout << q.front() << "\n";
      continue;
    }

    if (command == "back")
    {
      if (q.empty())
      {
        cout << "-1"
             << "\n";
        continue;
      }

      cout << q.back() << "\n";
      continue;
    }
  }

  return 0;
}

식당메뉴

밥을 먹지 못한 학생들이 눈물을 흘리고 있다.
type이 1일 때, queue에 학생의 번호와 선호하는 메뉴가 담겨있는 pair를 넣어주면 간단히 풀 수 있는 문제이다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int N;
  cin >> N;

  queue<pair<int, int>> q;
  vector<int> a, b, c;

  for (int i = 0; i < N; i++)
  {
    int type, student, favorite;
    cin >> type;

    if (type == 1)
    {
      cin >> student >> favorite;
      // 페어로 queue 등록
      pair<int, int> student_pair = {student, favorite};
      q.emplace(student_pair);
    }
    else
    {
      // 메뉴 퍼주고 결과 벡터 등록
      pair<int, int> tmp;
      tmp = q.front();
      q.pop();

      int curr_plate;
      cin >> curr_plate;

      if (curr_plate == tmp.second)
        a.push_back(tmp.first);
      else
        b.push_back(tmp.first);
    }
  }

  // queue에 남은 밥 못먹은 친구들 전부 c 벡터로 이동.
  while (!q.empty())
  {
    pair<int, int> remains = q.front();
    q.pop();
    c.push_back(remains.first);
  }

  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  sort(c.begin(), c.end());

  // 각 벡터 size 확인해서 0이면 None 넣어주기.
  if (a.empty())
  {
    cout << "None"
         << "\n";
  }
  else
  {
    for (int i : a)
    {
      cout << i << " ";
    }
    cout << "\n";
  }

  if (b.empty())
  {
    cout << "None"
         << "\n";
  }
  else
  {
    for (int i : b)
    {
      cout << i << " ";
    }
    cout << "\n";
  }

  if (c.empty())
  {
    cout << "None"
         << "\n";
  }
  else
  {
    for (int i : c)
    {
      cout << i << " ";
    }
    cout << "\n";
  }

  return 0;
}

PriorityQueue

최대 힙

눈물이 나는 문제이다.
왜 눈물이 나느냐?
JS에선 풀려면 Class로 한 땀 한 땀, 시간복잡도를 고려하여 구현해야 하는 자료구조를 그냥 제공하기 때문이다. 눈물이 난다...
JS 조금만 더 힘내자,...

왜 실버2인지 이해가 안되지만, 그냥 공짜 문제다.

0이면 최대값을 출력 후 삭제. 비어있으면 0 출력!

#include <iostream>
#include <queue>
using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);

  int N;
  cin >> N;

  priority_queue<int> pq;

  for (int i = 0; i < N; i++)
  {
    int curr;
    cin >> curr;

    if (curr == 0)
    {
      if (pq.empty())
        cout << 0 << "\n";
      else
      {
        cout << pq.top() << "\n";
        pq.pop();
      }
    }
    else
      pq.emplace(curr);
  }

  return 0;
}

최소 힙

이전 문제와 동일하다. 대신, 최대힙이 아닌 최소힙을 구현하면 된다.
priority_queue의 설정을 바꿔주면 nlogn의 최소힙을 간단히 사용할 수 있다.

#include <iostream>
#include <queue>
using namespace std;

int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int N;
cin >> N;

priority_queue<int, vector<int>, greater<int>> pq;

for (int i = 0; i < N; i++)
{
  int curr;
  cin >> curr;

  if (curr == 0)
  {
    if (pq.empty())
      cout << 0 << "\n";
    else
    {
      cout << pq.top() << "\n";
      pq.pop();
    }
  }
  else
    pq.emplace(curr);
}

return 0;
}

여기서 배워야 하는 것은 다음과 같다.

priority_queue<자료형, 구현체, 비교함수> pq;

pq는 vector로 구현되어있다. 자료형 또한 숫자를 사용하기에 int를 넣어준다면, 남은 비교함수만 살펴보면 된다.

최소힙을 priority_queue로 구현하는 것은 공식과 같은 부분이라 비교함수 부분에서 greater를 사용하면 된다는 것은 당연한 이야기지만, 이를 응용하고자 한다면 comp함수를 람다함수로 작성해서 decltype(comp)와 같이 넣어줄 수 있다는 것을 인지하고 가는 것이 좋다.

//min-heap
priority_queue<int, vector<int>, greater<int>> min_heap; 

//custom
priority_queue<int, vector<int>, decltype(comp)> custom_heap(comp);

절대값 힙

위에서 언급한 커스텀 힙을 이런 문제에서 사용하게 된다.
문제의 조건이 조금 헷갈릴 수 있으니 문제 꼼꼼히 읽고 람다함수로 비교함수만 구현하면 간단히 풀리는 문제!

#include <iostream>
#include <queue>
using namespace std;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  auto myComp = [](const int &a, const int &b)
  {
    if (abs(a) == abs(b))
    {
      return a > b;
    }

    return abs(a) > abs(b);
  };

  int N;
  cin >> N;

  priority_queue<int, vector<int>, decltype(myComp)> pq(myComp);

  for (int i = 0; i < N; i++)
  {
    int curr;
    cin >> curr;

    if (curr == 0)
    {
      if (pq.empty())
        cout << 0 << "\n";
      else
      {
        cout << pq.top() << "\n";
        pq.pop();
      }
    }
    else
      pq.emplace(curr);
  }

  return 0;
}

번외 문제

안정적인 문자열(괄호 변형)

stack을 사용해 올바른 괄호를 만드는 최소 연산수를 구하는 문제이다.
여기서 "연산"이란, '{'를 '}'로 바꾸거나 '}'를 '{'로 바꾸는 것을 의미한다.

연산 횟수를 분기처리하는 과정에서 아래의 요소를 잘 고려해야한다.

닫는 괄호일 때 '}', stack이 비어있는 경우. (여는 괄호로 바꿔야하기에 연산++)

닫는 괄호일 때, top도 닫는괄호인 경우.

괄호를 전부 계산한 뒤, stack에 남아있는 괄호들은 무조건 짝수개의 올바르지 않은 괄호이다. 그렇기에 최종적으로 stack의 남은 값의 절반이 answer에 더해져야한다.

answer += s.size() / 2

이를 코드로 구현하면 아래와 같다.

#include <iostream>
#include <stack>
#include <string>
#include <cstring>
using namespace std;

int main()
{
  int round = 0;
  while (true)
  {
    round++;
    string text;
    cin >> text;

    if (text[0] == '-')
      break;

    /* stack */
    stack<string> s;
    int answer = 0;

    for (int i = 0; i < text.length(); i++)
    {
      string curr;
      curr = text[i];
      if (curr == "}" && (!s.empty() && s.top() == "{"))
      {
        s.pop();
      }
      else if (curr == "{")
      {
        s.push(curr);
      }
      else
      {
        answer++;
        s.push("{");
      }
    }

    answer += s.size() / 2;
    cout << round << ". " << answer << "\n";
  }

  cout << endl;

  return 0;
}

정답률이 64%인데 나에겐 조금 어려웠던 문제.
단순히 stack을 사용해서 푼다기보단, 경우의 수를 전부 고려해 분기처리하고 이러한 특성들을 활용하여 푸는 문제다. stack에 얽매이면 오히려 풀이가 어려워짐.
사실상 stack 내부엔 열린괄호 '('만 들어가기에 stack으로 분기처리를 하는 것이 아닌 input된 값의 index를 이용해 풀어낼 수 있다! :)

#include <iostream>
#include <string>
#include <stack>
using namespace std;

int main()
{
  string input;
  cin >> input;

  stack<char> s;
  int answer = 0;

  for (int i = 0; i < input.length(); i++)
  {
    char curr = input[i];
    if (curr == '(')
      s.push('(');
    else
    {
      s.pop();
      if (input[i - 1] == '(')
      {
        answer += s.size();
      }
      else
      {
        answer += 1;
      }
    }
  }

  cout << answer << endl;

  return 0;
}

/*
## (인 경우 그냥 push
## )인 경우
pop하고
1. 레이저 top == '(' &&  (!s.empty() && s.top() == ')');
answer += s.size()
2. 막대 끝
사라지는 막대 끝 += 1;
*/