2019 KAKAO BLIND RECRUITMENT 온라인 코딩테스트 문제풀이

• A. 오픈채팅방
   입력으로 오픈채팅방의 기록들이 주어진다. 기록의 내용은 누군가 채팅방에 들어오거나, 나가거나, 닉네임을 바꾼 정보들이다. 주어진 기록을 보고 어떤 사용자가 들어오고, 나갔는지 출력하는 문제이다. 단 문제의 조건은 사용자의 닉네임이 변경되었을 때, 가장 마지막으로 변경된 닉네임을 기준으로 출력해야한다.
   닉네임은 중복될 수 있지만, 같은 닉네임을 가져도 어떤 사용자인지 식별할 수 있도록 고유한 uid가 주어진다. uid가 고유하기 때문에 uid를 Key로 하고, 닉네임을 Value로 하는 Map 자료구조를 이용하면 쉽게 사용자의 닉네임을 관리 할 수 있다.
   처음 주어진 기록들을 한번 순회하여 Map으로 uid와 닉네임을 Key와 Value로 맵핑 해놓는다. Change 커맨드가 주어질 때 Map에서 해당 uid의 닉네임을 바꿔주면 기록들은 순서대로 주어지기 때문에 순회를 마치면 가장 마지막의 닉네임이 저장될 것이다. 그리고 다시 한번 더 순회하여 Enter, Leave 커맨드에 맞게 출력해주면 된다.
  
  
• B. 실패율
   총 스테이지 1~N이 주어지고, 각 플레이어들이 현재 머무르고 있는 스테이지가 주어진다. 문제에서 실패율의 정의는 임의의 (k 스테이지에 머무른 플레이어의 수 / k 스테이지를 넘은 모든 플레이어의 수)이고, 각 스테이지의 실패율이 큰 순서로 스테이지를 출력하는 문제이다.
   임의의 k 스테이지에 머무르고 있는 플레이어들의 수를 알아야 하므로, 주어진 입력에서 처음 한번 순회하여 k 스테이지에 머무르고 있는 플레이어들의 수를 카운트 할 수 있다. 그리고 1~N까지 스테이지를 순서대로 순회하여 실패율을 구하면 된다. 이 때 k 스테이지를 넘은 모든 플레이어의 수는, 스테이지를 순회하면서 전체 플레이어 수에서 각 스테이지에 머무르고 있는 플레이어의 수를 빼주면 된다. 이렇게 하면 각 스테이지 순서대로 실패율을 구할 수 있고, 실패율이 큰 순서대로 정렬하여 출력하면 된다. 단 실패율은 실수형 변수여야 하고, 임의의 두 스테이지의 실패율이 같으면 스테이지가 빠른 순서로 출력해야함을 유의해야 한다.
  
  
• C. 후보키
   최대 8*20 크기의 릴레이션(Relation)이 주어진다. 이 릴레이션에서 유일성과, 최소성을 만족하는 후보키의 최대 개수를 구하는 문제이다. 유일성은 속성 집합 중에서 모든 튜플이 유일해야 한다. 최소성은 유일성을 가지는 속성 집합중 어느 속성 하나를 제외할 때 유일성이 깨지는 것을 말한다.
   최대 칼럼의 개수가 매우 적기 때문에 속성 집합이 1개, 2개, 3개, ..., 8개 일 때, 만들 수 있는 모든 조합의 수인 2^8 -1 를 시도해 볼 수 있다. 모든 조합의 수를 구할 때는 보통 재귀 호출을 통한 이진트리를 구성하거나, 최대 속성의 개수가 2진수의 각 비트의 자리라고 할 때, 00000001부터 11111111까지 모든 경우의 수를 탐색할 수 있다.
   이 문제의 경우 최소성을 검사하기 위해 이진트리(Binary Tree)를 구성하기 보다는 비트마스킹으로 1부터 순서대로 탐색하는 것이 편하다. 1부터 순서대로 탐색하면 속성 집합이 1개, 2개, ..., N개를 탐색할 때, 이미 N-1개 이하의 속성 집합을 검사했을테고, 최소성을 만족하는지 쉽게 알 수 있다. 만약 이 속성 집합이 유일성과 최소성을 만족하였다면 후보키를 찾은 것이다. 
   속성의 유일성은 Set 자료구조를 이용하여 판단할 수 있다. 칼럼의 원소를 Set에 넣을 때, Set에 이미 원소가 있으면 해당 속성은 유일성을 만족하지 못하는 것이다. 여러개의 속성 집합의 유일성을 판단할 때는 단순하게 튜플에 원소를 순서대로 연결하여 하나의 String으로 만들어 Set에 넣었다.
   만약 해당하는 속성 집합이 유일성을 만족하면 후보키를 담은 속성 집합과 비교한다. 1부터 순서대로 탐색할 때, 어느 속성 집합이 유일성을 만족하는 순간에는 반드시 후보키가 담긴 속성 집합에 있는 수보다 큰 수를 가진다. 예를 들면 00010101 이 유일성을 만족한다고 할 때, 후보키가 담긴 속성 집합의 원소들은 이 수보다 작은 수일 것이다. 만약 이 중 한 개의 원소가 00000101이라면 00010101의 최고 큰 비트(속성)을 제거하면 00000101이 되어 최소성을 만족하지 못한다. 이를 AND 연산으로 판단할 수 있다.
  
  
• D. 무지의 먹방 라이브
   문제의 입력으로 여러 개의 음식이 주어지는데, 각 음식은 먹을 수 있는 시간이 정해져있다. 음식 하나를 1초동안 먹고, 바로 옆 음식을 먹는 것을 k번 반복할 때 그 다음으로 먹어야 할 음식이 무엇인지 구하는 문제이다.
   정확성을 해결하기 위해서는 문제에서 주어진 요구사항 그대로 시뮬레이션을 하면 된다. 하지만 효율성의 경우 각 음식을 먹는데 주어진 시간이 최대 1억이기 때문에 단순히 시뮬레이션을 하면 시간초과를 피하기가 힘들다.
   효율성을 해결하기 위해서는 주어진 음식을 한번에 먹을 수 있는 방법을 생각할 수 있다. 모든 음식을 처음부터 끝까지 순서대로 먹는 것을 반복하는데, 이 때 음식을 먹을 수 있는 시간이 정렬되어 있으면 맨 앞의 원소의 시간만큼 모든 음식을 먹을 수 있다. 먹은 음식의 총 시간은 남은 음식의 개수를 곱하여 구할 수 있고 이를 k에서 빼주면된다. 모든 음식을 먹는데 소요한 시간이 k 보다 커지는 경우에는 남은 음식의 개수만큼 나머지를 구하여 k를 감소시키면 되는데, 정렬하기 전 원래의 음식과 비교해야 하는 점을 주의해야한다. 이 때 k가 0이 되면 마지막 음식이 된다.
  
  
• E. 길 찾기 게임
   (x, y)의 좌표에 해당하는 노드들이 입력으로 주어진다. x축으로는 노드들이 절대 겹치지 않는다. 좌표로 주어지는 노드들을 가지고 이진 트리를 구성하고 이를 전위 순회한 결과와 후위 순회한 결과를 출력하는 문제이다.
   y축에 있는 노드들은 루트노드로부터 같은 레벨을 가지기 때문에, 노드들을 y축 순서로 정렬하면 루트노드에서부터 레벨 순서대로 트리를 구축해 나갈 수 있다. 이 때 y값이 가장 큰 노드가 루트노드이다.
   현재 보고 있는 노드의 자식노드가 존재한다는 의미는 현재 노드의 y축 바로 아래의 y축이 있고 이는 트리의 레벨 형태이다. 부모노드의 x축을 기준으로 바로 아래 y축 레벨의 왼쪽, 오른쪽에 있는 노드가 해당 노드의 자식노드들이다. 만약 입력으로 주어지는 노드 중에서 가장 오른쪽에 있는 노드의 x값이 20이라고 하자. 그러면 x축의 범위는 [0, 20]이다. x축으로는 서로 겹치는 노드들이 없기 때문에, 만약 루트노드의 x값이 10이였다면 왼쪽 자식은 x축이 [0, 9]사이에 있을 것이고, 오른쪽 자식은 x축이 [11, 20]에 있을 것이다. 그리고 이 왼쪽 자식의 x값이 5이고, 이 왼쪽 자식노드의 자식노드들을 다시 구해본다면 왼쪽 자식은 x축이 [0, 4], 오른쪽 자식은 [6, 9] 사이에 있을 것이다. 즉 어느 노드의 자식노드의 범위를 결정할 때 단순히 부모노드만 기준으로 하는게 아니라, 부모노드의 조상노드까지 범위를 고려해야 한다. 이는 루트노드부터 레벨 순서대로 탐색하기 때문에 범위를 줄여가면서 쉽게 구현할 수 있다.
   하지만 위의 방법에서 노드를 y축으로만 정렬하면 문제가 생긴다. y축으로만 정렬된 노드들의 배열에서 x축의 범위에 해당하는 자식노드를 찾으려면 모든 노드를 탐색해야하기 때문이다. 따라서 y축과 x축 모두 정렬한 배열이 필요하다. 이는 주어진 입력에서 등장하는 y와 x의 값으로만 Set을 이용하여 좌표를 압축하는 방법을 생각할 수 있다. x축의 노드는 겹치지 않으므로 x축으로 노드들이 정렬되어 있다면, x의 값으로 자기 자신 노드의 인덱스를 노드들의 배열에서 이진탐색(Binary Search)으로 찾을 수 있다.
   노드들의 배열은 x축으로 정렬을 하고, y값만 가지고 있는 Set을 차례로 순회하는 방법을 사용한다. y값을 가지는 어떤 임의의 노드의 자식노드를 찾을 때 x축으로 정렬된 노드들의 배열에서 이진탐색으로 자기 자신의 노드를 찾고, x축으로 노드들이 정렬되어 있기 때문에 위에서 설명한 방식대로 범위 안에서만 자식노드를 찾으면 되므로 자식노드를 찾는 시간이 줄어든다.
  
  
• F. 매칭 점수
   HTML 형식의 페이지가 주어지고, 각 페이지는 요구사항에 맞게 점수가 메겨진다. 이 때 점수가 가장 큰 페이지의 인덱스를 출력하는 문제이다.
   해당 페이지의 URL은 <head> 태그 내부의 property가 "og:url"이고 content가 "URL"인 <meta> 태그를 찾으면 된다. 처음에는 property와 content의 순서가 반대로 되어 있는 경우 등, 이런 저런 예외가 있을 것이라 생각했는데, 별다른 예외 없이 해당하는 패턴을 찾으면 된다.
   등장하는 단어의 개수를 셀 때에도 <head> 내부에도 단어가 있으면? 이라는 생각을 가졌는데 아마도 <body> 에만 존재하는 단어만 찾으면 되는 것 같았다. 또 외부링크와 내부링크 또한 <body>에서만 찾으면 되는 것 같다.
   전체적으로 원하는 문자열을 찾을 때 해당 문자열이 등장하는 패턴 그대로 검색하면 된다. HTML의 총 문자열의 크기가 작기 때문에 O(N*M)으로 문자열을 검색해도 충분하다.
   이 문제에서 가장 관건은 단어의 개수를 찾는 것이다. 왜냐하면 단순히 단어가 공백을 기준으로 나눠지는 게 아니기 때문이다. <body> 내부의 텍스트를 모두 가져와서 알파벳을 제외한 모든 부분을 공백으로 바꾸고, 다시 탐색할 때 공백을 기준으로 단어를 찾을 수 있다. 이 때 태그 안의 속성들도 단어의 개수로 세야하는가? 라는 의문이 있었지만 태그 안의 속성들을 제외하고 단어의 개수를 세어도 정답으로 통과되었다.
  
  
• G. 블록 게임
   총 12개 종류의 테트리스 블록이 보드위에 있는데, 이 블록에 검은블록을 채워서 직사각형을 만들면 삭제할 수 있다. 검은블록은 1*1 크기이며, 위에서 아래로 한 개씩 떨어뜨릴 수 있다. 이 때 삭제할 수 있는 블록의 최대 개수를 구하는 문제이다.
   검은블록은 위에서 아래로만 떨어지기 때문에 사실 12개의 테트리스 블록 중 검은블록을 채워서 삭제할 수 있는 블록은 5개 뿐이다. 따라서 모든 칸에 검은블록을 떨어뜨리고 삭제할 수 있는 5가지 블록만 찾으면 되는데, 블록을 삭제할 수 없을 때 까지 이를 반복하면 된다. 단 주의해야할 점은 검은블록을 매번 x축에 1개씩만 떨어뜨리면 x축으로 2개의 검은블록과 만나야 삭제될 수 있는 블록이 존재하므로 매 반복마다 x축에 2개의 검은블록을 떨어뜨리면 된다.
  

위 문제의 모든 풀이 코드는 아래의 GitHub 링크에 공개되어 있습니다.
https://github.com/ISKU/Algorithm/tree/master/Programmers/2019%20KAKAO%20BLIND%20RECRUITMENT