Facebook Hacker Cup 2018 Qualification Round

나동빈

  페이스북 해커컵(Facebook Hacker Cup)은 특이한 방법으로 진행됩니다. 프로그램을 만들 때의 논리력을 중요시하기 때문에 언어의 제약이 없습니다. 그래서 문제를 푼 뒤에 소스코드를 제출할 때는 페이스북에서 제공하는 입력 파일(Input)을 받아서, 그것을 프로그램에 넣고 나온 결과(Output)을 그대로 제출하면 됩니다. 소스코드도 별도로 제출하긴 하는데 부정행위 검사용에 불과한 것 같습니다.

  실제로 문제를 푼 뒤에 답안을 제출할 때는 6분의 시간을 줍니다. 입력 데이터에 대해 6분 안에 올바른 결과 값을 도출해서 제출하면 되는 방식입니다.

  출력 파일 및 소스코드를 제출하면 다음과 같이 제출이 이루어집니다. 결과는 대회가 끝나야 제대로 나오는 것으로 판단됩니다.

1. Tourist

문제 설명

(페이스북 해커컵의 문제는 영어로 제공됩니다. 제가 임의로 번역한 겁니다.)

- N개의 장소가 있고 장소의 이름은 문자열로 주어집니다.

- 1부터 N까지 인기가 많은 순서대로 주어집니다.

- 한 번 방문할 때 K개의 장소를 방문합니다.

- 구체적으로 어떤 장소를 방문할지 결정하기 위해서, 이미 몇 번 방문한 적이 있는지를 기준으로 N개의 장소를 오름차순 정렬합니다. 그리고 인기도가 많은 순으로 정렬하여 K개를 선택합니다.

- 즉 모든 장소에 대해서 방문한 횟수를 기준으로 먼저 선택하고, 방문한 횟수가 동일하다면 인기도가 높은 장소를 선택하면 됩니다.

- Alex는 이미 V-1번 방문한 적이 있습니다. 이제 V번째 방문을 하고자 합니다. Alex가 V번째 방문할 때 방문하게 될 K개의 장소를 출력하면 됩니다.

- T번의 테스트가 제공되고 매 테스트마다 N, K, V가 주어지고 N개의 장소명이 주어집니다.

- 1 <= T <= 80, 1 <= K <= N <= 50, 1 <= V 10^12

예제 입력

6

4 1 3

LikeSign

Arcade

SweetStop

SwagStore

4 4 100

FoxGazebo

MPK20Roof

WoodenSculpture

Biryani

4 3 1

LikeSign

Arcade

SweetStop

SwagStore

4 3 3

LikeSign

Arcade

SweetStop

SwagStore

4 3 10

LikeSign

Arcade

SweetStop

SwagStore

2 1 1000000000000

RainbowStairs

WallOfPhones

예제 출력

Case #1: SweetStop

Case #2: FoxGazebo MPK20Roof WoodenSculpture Biryani

Case #3: LikeSign Arcade SweetStop

Case #4: LikeSign SweetStop SwagStore

Case #5: LikeSign Arcade SwagStore

Case #6: WallOfPhones

문제 풀이

  문제의 조건을 보면 V가 최대 1,000,000,000,000까지 들어올 수 있습니다. 그래서 단순히 문제에서 요구하는 대로 매 번 정렬을 수행해서 최종적인 답을 도출하려고 하면 정해진 시간 안에 문제를 해결할 수 없을 겁니다. 그래서 최대 1,000,000,000,000 번을 실제로 다 방문하지 말고 어떠한 규칙을 발견할 수 있도록 애초에 문제에서 유도하고 있는 것입니다. 따라서 문제를 풀 때는 정확히 이러한 N, K, V의 범위. 즉 정의역에 대해서 가장 먼저 파악해야 합니다.

  만약에 장소의 개수가 5개라고 할 때, 차례대로 장소를 방문한다고 하면 i번째 장소를 방문하고자 할 때 인덱스는 어떻게 될까요?

  위와 같이 장소가 5개 있다고 해봅시다. 이 때 3번째 장소는 다음과 같이 인덱스 2에 해당합니다.

  그렇다면 9번째 장소는 어떻게 될까요? 다음과 같이 한 바퀴 돌아서 인덱스 3에 해당합니다.

  즉, i번째 장소의 인덱스를 구하려면 (i - 1) % N을 하면 됩니다. 이걸 왜 언급하는 걸까요? 그 이유는 이 문제는 슬라이딩 윈도우와 흡사한 알고리즘이 사용되기 때문입니다. 전체 배열의 크기가 N일 때 한 번 방문할 때 K개만큼 방문하면서 계속해서 원을 그리며 이동하면 됩니다.

  다만 방문 횟수가 동일한 경우에는 더 인기가 많은 장소부터 출력해야 하므로 슬라이딩 윈도우를 수행하며, 출력하기 전에 인덱스를 기준으로 장소의 이름에 대해 오름차순 정렬을 수행해주시면 됩니다.

  결과적으로 이미 V - 1번 방문을 했다고 가정하므로 V번 째 방문을 할 때는 (K * (V - 1)) % N + 1번째 장소부터 (K * (V - 1)) % N + K번째 장소까지 방문하여 출력하면 정답 처리를 받을 수 있습니다. (출력하기 직전에 인덱스를 기준으로 정렬을 해주시면 됩니다.)

#include <iostream>

#include <fstream>

#include <algorithm>

#include <vector>

using namespace std;

long long int n, k, v;

string a[50];

class Node {

  public:

    int rate;

    string name;

    Node(int rate, string name) {

      this->rate = rate;

      this->name = name;

    }

    bool operator <(Node other) {

      return this->rate < other.rate;

    }

};

int getIndex(int number) {

  return (number - 1) % n;

}

int main(void) {

  ifstream inFile("Tourist.txt");

  ofstream outFile("Tourist Answer.txt");

  int T;

  inFile >> T;

  for(int testCase = 1; testCase <= T; testCase++) {

    vector<Node> nodes;

    inFile >> n >> k >> v;

    for(int i = 0; i < n; i++) {

      inFile >> a[i];

    }

    for(int i = (k * (v - 1) % n + 1); i <= (k * (v - 1) % n + k); i++) {

      int index = getIndex(i);

      nodes.push_back(Node(index, a[index]));

    }

    sort(nodes.begin(), nodes.end());

    outFile << "Case #" << testCase << ": ";

    for(int i = 0; i < nodes.size(); i++) {

      outFile << nodes[i].name << ' ';

    }

    outFile << '\n';

  }

  return 0;

}

2. Interception

문제 설명

(페이스북 해커컵의 문제는 영어로 제공됩니다. 제가 임의로 번역한 겁니다.)

-

- 위와 같은 형태로 표현되는 다항식이 있습니다.

- 이러한 다항식을 실제로 계산할 때는 연산자 우선순위가 덧셈(+), 곱셈(*), 지수 승(^) 순서입니다.

- 예를 들어 는 로 계산됩니다.

- 음수(-) 부호는 우선순위가 제일 높습니다.

- 0^0은 1입니다.

- T번의 다항식(Polynomial)이 주어집니다.

- 다항식마다 최고 차수 N이 주어지고, 그 이후에 차수 N부터 0까지 차례대로 계수가 주어집니다.

- 계산하기 위한 다항식을 f(x)라고 했을 때 f(x) = 0이 되는 X의 개수를 출력하고, 각 라인에서는 각 X의 값을 오름차순으로 출력합니다.

예제 입력

2

1

1

1

4

9

0

-6

2

-2

예제 출력

Case #1: 1

0.0

Case #2: 0

부가 설명

주어진 예제 입력을 설명해드리자면 다음과 같습니다.

2: 테스트 케이스가 2

1: 첫 번째 테스트 케이스는 최고 차수가 1

1: 차수 1의 계수

1: 차수 0의 계수

4: 두 번째 테스트 케이스는 최고 차수가 4

9: 차수 4의 계수

0: 차수 3의 계수

-6: 차수 2의 계수

2: 차수 1의 계수

-2: 차수 0의 계수

첫 번째 테스트 케이스에서 들어온 입력은 다음과 같은 식입니다.

이제 이걸 f(x)로 표현하면 다음과 같습니다.

  그러므로 X가 0일 때 f(x)가 0이 될 수 있는 것입니다.

문제 풀이

  일단 문제에서 요구하는 연산자의 우선순위를 따랐을 때 모든 다항식은 ‘지수함수’으로 표현된다는 것을 이해하셔야 합니다. 왜냐하면 지수 연산(^)의 우선순위가 제일 낮기 때문입니다. 어떠한 입력이 들어와도 결과적으로 f(x)는 지수함수 형태에요. 이 때 일반적인 지수함수는 절대로 f(x) = 0이 될 수 없다는 것을 생각해보세요. 지수함수는 다음과 같이 생겼습니다.

다만, 문제의 형태를 보면 항상 최종적으로는 X와 어떠한 식을 곱하도록 되어있습니다. 예를 들어 다음의 식을 고려해보세요.  이 식은 다음과 같이 바뀝니다.

  즉 어떠한 다항식이 들어왔을 때 무조건 (어떠한 숫자 * X)의 지수 승 형태로 표현되는 것을 알 수 있습니다. 이게 힌트인데요. 일반적인 지수함수는 어떤 일이 있어도 그 결과 f(x) = 0이 될 수 없기 때문에 (어떠한 숫자 * X)를 이용하셔야 합니다. X = 0인 경우에는 f(x) = 0이 될 가능성이 존재하기 때문입니다. 다시 말해서 어떠한 입력 값이 들어오더라도 근이 한 개 존재하는 경우(X = 0), 근이 아예 존재하지 않는 경우 두 가지 경우 밖에 존재하지 않는다는 것입니다.

  이 때 실제로 특정한 f(x)에 대해 X = 0을 넣는 방식으로 답을 계산할 수도 있을 것입니다. 다만 저는 조금 더 문제를 분석해보았어요. 그랬더니 재미있는 규칙을 찾았습니다. 바로 항의 개수가 홀수일 때는 근이 없고, 항의 개수가 짝수일 때는 근이 있다는 겁니다. 종이로 그려보니까 다음과 같았어요.

  따라서 테스트 케이스마다 N을 입력 받아서 N이 홀수일 때와 짝수일 때를 구분해서 정답을 출력하면 문제를 쉽게 해결할 수 있습니다.

#include <iostream>

#include <fstream>

using namespace std;

int main(void) {

  ifstream inFile("Interception.txt");

  ofstream outFile("Interception Answer.txt");

  int T;

  inFile >> T;

  for(int testCase = 1; testCase <= T; testCase++) {

    int n;

    inFile >> n;

    for(int i = 0; i <= n; i++) {

      int x;

      inFile >> x;

    }

    outFile << "Case #" << testCase << ": ";

    if(n % 2 == 1) {

      outFile << 1 << '\n';

      outFile << "0.0" << '\n';

    } else {

      outFile << 0 << '\n';

    }

  }

  return 0;

}

3. Ethan Searches for a String

문제 설명

(페이스북 해커컵의 문제는 영어로 제공됩니다. 제가 임의로 번역한 겁니다.)

- 문자열 매칭 알고리즘이란 문자열 A가 문자열 B 안에 포함이 되어있는지를 판단하는 알고리즘입니다.

- 다음의 Ethan이 작성한 문자열 매칭 알고리즘이 있습니다. 이 알고리즘은 잘못된 알고리즘입니다.

(1) i와 j를 1로 설정합니다.

(2) i > |A|일 때, TRUE를 반환합니다.

(3) j > |B|일 때, FALSE를 반환합니다.

(4) Ai = Bj일 때, i와 j를 1 증가시키고 (2) 단계로 이동합니다.

(5) i = 1일 때, j를 1 증가시키고 (2) 단계로 이동합니다.

(6) i를 1로 설정하고 (2) 단계로 이동합니다.

- A라는 문자열이 주어졌을 때, 우리는 문자열 A가 B라는 문자열 안에 포함이 되는데도 불구하고 Ethan의 알고리즘이 FALSE를 뱉는 ‘문자열 B’를 찾아내고자 합니다.

- 문자열 B를 찾을 수 없을 때는 'Impossible'을 출력합니다.

- 테스트 케이스 T는 100개까지 주어질 수 있습니다.

- 1 <= A의 길이 <= 2,000

- 1 <= B의 길이 <= 10,000

예제 입력

4

ABACUS

FACEBOOK

XYZXZYX

FBFBF

예제 출력

Case #1: ASUCABABACUSA

Case #2: Impossible

Case #3: XZYXYZXYZXZYXYZXYZYX

Case #4: Impossible

문제 풀이

  먼저 문제를 접하기 전에 KMP 알고리즘에 대한 제 강의 노트를 한 번 보시고 오시기 바랍니다.

  KMP 알고리즘: https://blog.naver.com/ndb796/221240660061

  일단 Ethan의 알고리즘을 직접 C++ 소스코드로 구현해보겠습니다.

#include <iostream>

using namespace std;

bool contains(string a, string b) {

  int i = 1, j = 1;

  while(1) {

    if(i > a.length()) return true;

    if(j > b.length()) return false;

    if(a[i - 1] == b[j - 1]) {

      i++;

      j++;

      continue;

    }

    if(i == 1) {

      j++;

      continue;

    }

    i = 1;

  }

}

int main(void) {

  string a = "ABACUS";

  string b = "ASUCABABACUSA";

  cout << contains(a, b) << '\n';

  int result = b.find(a);

  cout << result;

  return 0;

}

  위 소스코드를 보시면 “ABACUS”는 분명히 “ASUCABABACUSA”에 포함이 되는데도 불구하고 Ethan의 알고리즘은 FALSE(0)라는 값을 반환하는 것을 알 수 있습니다. find() 함수는 C++에서 기본적으로 제공하는 문자열 매칭 함수입니다. find() 함수는 "ABACUS"가 포함되는 시작 인덱스인 6이라는 값을 내뱉는 것을 알 수 있습니다. 그렇다면 이 문제를 풀기 위해서는 어떻게 해야 할까요? Ethan의 알고리즘을 직접 손으로 차근차근 해보면 쉽게 이해하실 수 있습니다. 문자열이 일치하는지 하나씩 검사하는 알고리즘인데요, 접미사와 동일한 접두사가 존재하는 경우를 캐치하지 못한답니다.

  따라서 하나씩 검사하다가 불일치 할 때 위치에서의 접미사와 동일한 접두사가 존재하는지 확인해야합니다. Ethan의 소스코드는 그러한 경우를 캐치하지 못하고 넘어가는 불완전한 소스코드니까요.

  예를 들어 FBFBFK는 Ethan의 소스코드의 결함을 보여주는 예시입니다. FBFBFBFK와 비교했을 때 하나씩 검사하다가 FBFBFK와 FBFBFBFK가 불일치가 발생합니다. 이 때 접미사와 접두사는 FBFB로 동일하게 구성됩니다.

A: FBFBFK

B: FBFBFBFK

  이러한 경우 실제로는 문자열이 포함됨에도 불구하고 Ethan의 함수는 이를 감지할 수 없습니다. 따라서 Ethan 함수의 결함을 지적하기 위해서는 하나씩 검사하다가 불일치 할 때 위치에서의 접미사와 동일한 접두사가 존재하는 문자열 B를 만들면 됩니다.

  다만 불일치하기 직전까지는 일단 A와 B가 일치했다는 것을 이해하셔야 합니다.

A: FBFBFK

B: FBFBFBFK

  위 경우를 보시면 일단 FBFBF까지는 일치했습니다. 그 이후에 K와 B가 서로 다른 겁니다. 따라서 불일치 할 때 위치에서의 접두사와 접미사가 일치하려면, 불일치하기 직전까지 검사했던 일련의 문자열들도 당연히 접두사와 같아야 합니다. 예를 들어 FBF와 F 두 개가 존재할 겁니다.

  다시 말해서 ‘하나씩 검사하다가 불일치 할 때 위치에서의 접미사와 동일한 접두사가 존재하는 문자열 B’를 만들기 위해서는 문자열 A에서 이미 접두사와 접미사가 일치하는 문자열 쌍이 존재해야만 합니다. 예를 들어 FACEBOOK은 접두사와 접미사가 일치하는 문자열 쌍이 하나도 존재하지 않습니다. 그렇기 때문에 Ethan의 함수에서의 결함을 찾을 수 없는 예시가 되는 겁니다.

  이제 문자열 ‘FBFBF’를 고려해봅시다. 이것도 Ethan의 함수의 결함을 찾을 수 없습니다.

A: FBFBF

B: FBFB?

  위 경우를 보시면 물음표 위치에 F를 넣는다고 하면 문자열 일치가 발생해버리고, K와 같이 다른 문자를 넣는다고 하면 ‘불일치 할 때 위치에서의 접미사와 동일한 접두사’가 존재할 수 없습니다. 모순이 발생하는 거죠. 분명히 접두사와 접미사가 일치하는 경우는 'F', 'FB', 'FBF' 세 개가 존재함에도 불구하고 이러한 문제가 발생했습니다. 여기에서 하나의 사실을 유추할 수 있습니다. 바로 접두사와 접미사가 일치하는 ‘연속된 경우’의 뒤에 ‘하나 이상의 여분 문자가 필요’하다는 것입니다.

  예를 들어 FBFBK는 'F', 'FB'라는 두 개의 ‘접미사와 동일한 접두사’가 존재할 수 있습니다. 이제 'F'와 ‘FB'는 연속되어 있으므로 ’FB'만 고려하겠습니다. 이 때 잘 살펴보시면 'FB'의 뒤에 K라는 하나 이상의 여분 문자가 존재합니다. 그래서 이 K를 F로 바꾸어주고, 뒤에 BK를 붙여줌으로써 다음과 같은 문자열을 만들 수 있어요.

B: FBFBFBK

  이렇게 만들게 되면 Ethan의 함수에 존재하는 결함을 밝힐 수 있게 되는 것입니다. 따라서 문제를 해결하기 위한 방법은 다음과 같습니다.

< Ethan의 함수에 존재하는 결함을 밝히는 방법 >

1. 접두사 및 접미사 쌍 테이블을 만들기

2. 접두사와 접미사가 일치하는 ‘연속된 경우’의 뒤에 ‘하나 이상의 여분 문자가 존재’하는지 확인하기

  예를 들어 ‘XYZXZYX’의 접두사 및 접미사 쌍 테이블은 다음과 같습니다.

  보면 ‘XYZXZYX’는 인덱스 3의 값이 1이라서 접두사와 접미사가 일치하는 부분 문자열이 존재하는 겁니다. 이 때 인덱스 4가 여분 문자로 존재합니다. 따라서 다음과 같은 문자열을 만들 수 있어요.

XYZXYZXZYX

  다시 말해 XYZX에서 그 뒤로 YZXZYX를 넣어준 겁니다. 이것은 접두사와 접미사가 일치할 수 있는 부분이 인덱스 3의 ‘X’이므로 그 뒤로 접미사를 제외한 YZXZYX를 넣어준 것이라고 할 수 있습니다. 이런식으로 만들게 되면 ‘XYZXYZXZYX' 안에 'XYZXZYX’가 포함되어 있음에도 불구하고 Ethan의 함수는 이를 찾아내지 못합니다. 이제 이 내용을 소스코드로 옮기면 됩니다.

#include <iostream>

#include <fstream>

#include <vector>

using namespace std;

vector<int> makeTable(string pattern) {

  int patternSize = pattern.size();

  vector<int> table(patternSize, 0);

  int j = 0;

  for(int i = 1; i < patternSize; i++) {

    while(j > 0 && pattern[i] != pattern[j]) {

      j = table[j - 1];

    }

    if(pattern[i] == pattern[j]) {

      table[i] = ++j;

    }

  }

  return table;

}

int main(void) {

  ifstream inFile("Ethan.txt");

  ofstream outFile("Ethan Answer.txt");

  int T;

  inFile >> T;

  for(int testCase = 1; testCase <= T; testCase++) {

    outFile << "Case #" << testCase << ": ";

    string pattern;

    inFile >> pattern;

    vector<int> table = makeTable(pattern);

    bool find = false;

    for(int i = 1; i < table.size(); i++) {

      // 접두사와 접미사가 일치하는 '연속된 경우'의 뒤에 '하나 이상의 여분 문자가 존재'하는지 확인

      if(table[i] <= table[i - 1] && table[i - 1] != 0) {

        // 찾았을 경우 문자열 생성

        find = true;

        // 앞 부분 출력

        for(int j = 0; j < i; j++) {

          outFile << pattern[j];

        }

        // 뒷 부분 출력

        for(int j = table[i - 1]; j < pattern.size(); j++) {

          outFile << pattern[j];

        }

        outFile << '\n';

        break;

      }

    }

    if(!find) {

      outFile << "Impossible\n";

    }

  }

  return 0;

}