Google Kickstart 2018 Round A 풀이 (코드포함)

Posted on by

이 포스팅에서는 Google Kickstart 2018 Round A 풀이와 코드를 제공합니다. 본 풀이는 공식적인 풀이와 다를 수 있으며, 온라인 채점 도구를 통과한 소스코드를 제공합니다. 대회에 대한 자세한 사항은 공식 홈페이지를 참조하시기 바랍니다.

Prob A ‘Even Digits’

문제 링크

문제 설명

모든 자릿수가 짝수인 수들 중에서 주어진 N과 가장 가까운 수와 N의 차의 절대값을 출력하는 문제

문제 풀이

아래 코드는 이분 검색을 통해 문제를 해결한 것이다. 모든 자릿수가 짝수인 수는 0, 2, 4, 6, 8로만 구성된다. 5진법을 이용한다면, 5진법으로 나타낸 수의 각 자릿수값 0, 1, 2, 3, 4를 0, 2, 4, 6, 8로 치환시킬 수 있다. 5 ** 19는 5진법으로 19자리이기 때문에 문제의 조건을 만족하는 10진수에 19자리까지 대응시킬 수 있다. 이분 검색의 범위를 나타내는 left와 right는 실제 10진수 값이 아니라, 문제의 조건을 만족하는 10진수들을 오름차순으로 정렬했다고 가정할 때 그 수의 인덱스를 나타내는 값이라고 생각하면 된다. 이 인덱스를 이분 검색으로 줄여나가며 왼쪽과 오른쪽에서 주어진 수 N과 가장 가까운 수를 각각 찾아서 그 중 더 가까운 것과 N의 차의 절대값을 출력한다.

def TenToFive(num):
  if num == 0:
    return '0'
  else:
    if num // 5 != 0:
      return TenToFive(num // 5) + str(num % 5)
    else:
      return str(num % 5)

def FiveToTen(num):
  V = ['0', '2', '4', '6', '8']
  return int("".join(V[int(i)] for i in str(num)))

def Do(left, right):
  global N, Left, Right
  if left > right:
    return
  mid = (left + right) // 2
  Num = FiveToTen(TenToFive(mid))

  if Num > N:
    Right = min(Right, Num)
    Do(left, mid - 1)
  elif Num < N:
    Left = max(Left, Num)
    Do(mid + 1, right)
  else:
    Right = min(Right, Num)
    Left = max(Left, Num)

T = int(input())
for tt in range(T):
  N = int(input())
  Left, Right = -1, FiveToTen(TenToFive(5 ** 19))
  Do(0, 5 ** 19)
  print ("Case #" + str(tt + 1) + ":", min(N - Left, Right - N))

Prob B ‘Lucky Dip’

문제 링크

문제 설명

가방 안에 N개의 아이템이 있고 각 아이템은 V_i 만큼의 가치를 가진다. 가방에 손을 집어넣어 무작위로 아이템을 뽑는데, K + 1번까지 시도할 수 있다. 재도전은 현재 뽑은 아이템을 다시 가방에 넣은 후에 진행한다. 가장 마지막 도전에서 뽑은 아이템의 가치가 최종 스코어가 된다. 최종 스코어의 기댓값을 최대화 시켰을 때 그 값은 무엇인가.

문제 풀이

매 단계에서 다시 주사위를 던질지 말지를 결정하는 방식은 다음과 같다.
현재 꺼낸 아이템의 가치가 재시도의 기댓값보다 크다면 Stop, 아니라면 Go하는 것이다.

다음 단계의 기댓값이 Next일 때, 현재 단계의 기댓값은
count(Next보다 작은 가치의 아이템 수) / N x Next + sum(Next보다 큰 아이템 가치) / N 이다.

def getSum(arr):
  Sum = [0] * len(arr)
  Sum[0] = arr[0]
  for i in range(1, len(arr)):
    Sum[i] = Sum[i - 1] + arr[i]
  return Sum
    
def findIndexOfBiggerElement(arr, val):
  left = 0
  right = len(arr) - 1
  check = len(arr)
  while left <= right:
    mid = (left + right) // 2
    if arr[mid] >= val:
      check = min(check, mid)
      right = mid - 1
    else:
      left = mid + 1
  return check

T = int(input())
for tt in range(T):
    N, K = [int(x) for x in input().split()]
    Nums = [int(x) for x in input().split()]
    Nums.sort()
    Sum = [0] + getSum(Nums)
    
    # Calc ExpectedValue
    ExpectedValue = sum(float(num) for num in Nums)/float(N)
    
    # Improve Expected Value over try
    Next = ExpectedValue
    for i in range(K):
      Temp = 0.0
      Idx = findIndexOfBiggerElement(Nums, Next)
      LocalSum = Sum[N] - Sum[Idx]
      Temp = float(LocalSum)/float(N) + float(Idx) * float(Next) / float(N)
      Next = Temp
    
    print ("Case #" + str(tt +1) + ":", Next)

Prob C ‘Scrambled Words’

문제 링크

문제 설명

임의로 생성된 문자열과 여러 단어가 주어진다. 주어진 단어 중에서 문자열의 부분문자열과 일치하는 것의 갯수를 출력하는 문제다.
다만 여기에선 문자열 비교 방식이 좀 다르다. 두 문자열의 비교는 처음과 끝 알파벳이 같고, 단어를 구성하는 각 알파벳의 수가 동일하면 같은 것으로 간주한다. 예를 들어 abcde는 acbde나 adcbe와도 같은 것이다.

문제 풀이

우선 어떤 단어가 문자열에 포함되는지 쉽게 판별하는 방법을 찾아낸다. 문자는 26개이고 앞과 끝 글자와 구성만 비교하기 때문에 배열을 사용한다. 길이 26의 배열에 각 알파벳이 출현하는 빈도를 기록하고, 앞과 끝 글자만 기록한다. A[i : i + len(word)]에 속하는 부분문자열에서 A[i + 1 : i + 1 + len(word)]에 속하는 부분문자열로 넘어갈 때는 기존 빈도에서 A[i]에 해당하는 빈도를 하나 감소시키고 A[i + 1 + len(word)]에 해당하는 빈도를 하나 증가시킨다. 그리고 앞과 끝 글자만 업데이트하면 된다.

이 값들을 모두 “,”로 합쳐서 HashString을 만든다. 딕셔너리를 사용해서 Dic[HashString] = True로 만들고, 주어진 단어로 만든 HashString이 Dic에 포함되어 있는지 판별한다.

전체 문자열의 길이는 10^5를 넘지 않는다. 이 말은 서로 다른 단어의 길이가 많아야 500개 이하로 존재한다는 말이다. 각 길이에 대해서 딕셔너리는 한 번만 만들면 되기 때문에 딕셔너리는 500개를 넘지 않는다. 각 단어를 길이순으로 정렬해서, 같은 길이들에 대해서는 기존에 만들어진 딕셔너리에 대해 포함되는 HashString의 갯수를 세면 되겠다.

배열 때문인지 Large Case에서는 Error가 난다.

def genDic(sentence, sentenceVec, length):
  Dic = {}
  Arr = [0] * 26
  
  # Initial Array
  s1, s2 = sentence[0], sentence[length - 1]
  for i in range(length):
    Arr[sentenceVec[i]] += 1
  Dic[getHashKey(s1, s2, Arr)] = 1

  # Iterate
  for i in range(0, len(sentenceVec) - length):
    Arr[sentenceVec[i]] -= 1
    Arr[sentenceVec[i + length]] += 1
    s1, s2 = sentence[i + 1], sentence[i + length]
    Dic[getHashKey(s1, s2, Arr)] = 1
  return Dic
  
def getHashKey(s1, s2, Arr):
  return ",".join([s1,s2] + [str(x) for x in Arr])

def chrToInt(sentence):
  vec = [0] * len(sentence)
  for i in range(len(sentence)):
    vec[i] = ord(sentence[i]) - 97
  return vec

def wordToVec(word):
  vec = [0] * 26
  for i in range(len(word)):
    vec[ord(word[i]) - 97] += 1
  return vec

def genSentence(s1, s2, N, A, B, C, D):
  A, B, C, D = int(A), int(B), int(C), int(D)
  sentence = [0] * N
  sentence[0], sentence[1] = s1, s2
  x1, x2 = ord(s1), ord(s2)
  for i in range(2, N):
    x1, x2 = x2, (A * x2 + B * x1 + C) % D
    sentence[i] = chr(97 + (x2 % 26))
  return "".join(sentence)

T = int(input())
for tt in range(1, T + 1):
  # Get words and preprocess
  wordCnt = int(input())
  words = raw_input().split()
  wordVectors = []
  wordLength = []
  for i in range(len(words)):
    length = len(words[i])
    wordLength.append([length, i])
  wordLength.sort()
  
  for i in range(len(wordLength)):
    word = words[wordLength[i][1]]
    length = wordLength[i][0]
    vector = wordToVec(word)
    wordVectors.append([length, getHashKey(word[0], word[length - 1], vector)])

  # Generate String
  s1, s2, N, A, B, C, D = raw_input().split()
  N = int(N)
  sentence = genSentence(s1, s2, N, A, B, C, D)
  sentenceVec = chrToInt(sentence)

  prevLength = -1
  cnt = 0
  for i in range(len(wordVectors)):
    vector = wordVectors[i]
    length = vector[0]
    HashString = vector[1]
    # Get Vector Dictionary for new length
    if prevLength != length:
      Dic = genDic(sentence, sentenceVec, length)
      prevLength = length
    if HashString in Dic:
      cnt += 1
  print "Case #" + str(tt) + ": " + str(cnt)