스터디룸

9월 11일에 LINE과 KAKAO 코딩테스트 두 개를 모두 응시해야 했어서 일정 관리에 상당히 애를 먹었다.

서류 제출 후 통과된 인원에 대해 LINE 코딩테스트 응시기회가 주어지는데 라인은 으레 알려졌듯이 면접에서 거의 결정되는 회사로 서류기준이 매우 관대하다고 알려져있어 별 걱정은 하지 않았다.

코딩테스트를 보고난 뒤 느꼈던 점은 정말 중요한 실전에서는 굉장히 긴장이 된다는 점과 그에 따라 코드 작성함에 있어 로직을 구상하거나 분기문 작성하면서 예외 처리에 누락사항이 빈번하게 발생했다는 점이다. 총평은 조금 아쉽다.

총 6문제 출제되었고 3시간이 주어졌다. 전반적으로 요구사항을 잘 읽고 분기문을 작성하던지 의도에 맞게 재귀함수를 작성하던지에 대한 문제들이었고 적절하게 자료형을 채택해서 데이터를 잘 다뤘어야 하는 문제들이 주를 이뤘다. 풀면서 내가 데이터 전처리를 하는 건지 알고리즘을 풀고 있는 건지 혼동이 왔을 정도였다. 출제된 문제들은 대부분 투포인터로 해결할 수 있었는데 다른 코딩테스트에서 bfs나 dfs, dp가 한 문제 정도 출제되었다는 점을 참고한다면 쉬운문제였음에도 오히려 투포인터로 대부분 해결해야 해서 애를 먹을 수도 있었겠다.

1번은 투포인터로 우측 포인터를 이동시키면서 조건에 맞을 경우 왼쪽 포인터를 이동시키면서 시간복잡도 O(n)을 맞춰야 한다.

2번은 해시 자료구조를 잘 다뤄서 카운팅만 잘 해준 뒤 조건에 맞게 분류하면 되는 문제인데 분류 과정이 2번 겹쳐서 DB를 구성하듯이 key-value를 잘 고려해야 했다.

3번은 스케쥴링 문제인데 시간을 1씩 올려가면서 조건에 맞게 현재 요청이 있는지 검사하고 유무에 따라 들어온 작업의 분류 번호 검사, 작업을 쌓는 과정, 작업을 교체, 대기하는 로직을 잘 짜야했다. 분기문이 꽤나 많아지는 문제로 완전탐색임을 캐치해야함은 물론이고 분기문까지 잘 처리해야 했다. 갠적으로 어렵진 않았으나 제일 복잡했던 문제였다. 여기서 시간을 너무 많이 빼앗겼다.

4번은 재귀함수 문제로 병합정렬의 구조를 이해했다면 즉시 해결할 수 있는 문제였다. 분할 조건과 함수의 종결 조건을 잘 설정하면 끝난다.

5번은 문자열 유사도 관련 문제였는데 역시나 투포인터로 수정해야 하는 문자열의 개수를 카운팅하는 함수와 조건에 따라 문자열을 분리해서 분기문을 작성해야 했는데 3번에서 시간을 너무 빼앗겨 시간이 모자라 해결까지는 하지 못했다.

6번도 문자열을 다루는 문제로 스트링을 시간으로 바꿔서 주어진 조건에 해당하는 범위의 레코드만 추려낸 뒤 조건에 맞춰서 해시 자료구조와 배열을 섞어서 데이터를 저장한 뒤에 분류 조건을 따져가면서 정답을 제출해야 했다.

히든 테스트케이스를 제공하지 않아 제출 후 엣지 케이스를 통과할 수 있을지는 모르겠지만 일단 예제는 6문제 중 5문제를 통과시켜서 제출했다. 나머지 한 문제도 긴장을 좀 덜했다면 3번 분기문 처리하면서 예외사항 고려에 시간을 아껴서 해결할 수 있었을텐데 조금 아쉽다. 전반적인 평가를 하자면 코딩 실력보다는 엄청하게 긴 지문을 읽고 조건을 명확하게 파악하여 로직을 만들어야 했던 테스트로 데이터 분석과 요구사항 파악이 주요했다. 코딩테스트를 합격하더라도 악명높은 LINE의 필기테스트와 면접이 남아있는데 아직 거기까진 수준이 못 미치는 듯하여 그냥 열심히 더 준비해야겠다는 생각밖에 들지 않았던 테스트였다.

후기 : 라인 코딩테스트는 합격해서 필기 테스트 응시 자격을 얻었다. 필기 테스트 범위가 겁나 넓던데 겉핥기식으로라도 보고 가야겠다. 면접까지 생각하면 합격하기 힘들 수도 있겠지만 끝까지 최선을 다해 진행해보려 한다.

- 후속 포스팅

2021 하반기 LINE 필기 테스트 후기

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 광고 삽입

문제 풀이

그리디나 이진 탐색이 아니라 누적합과 DP 문제였다. 누적합과 관련된 고난도 문제를 풀어보지 못해 아마 풀제되었어도 해결하지 못했을 것이다. 전체 필드의 길이는 30만초로 각 시청 기록들에 대해 시작 지점에 +1하고 끝나는 지점에 -1하여 시청자 상태를 기록한다. 그리고 1부터 누적합을 1번하면 각 시점 별 시청자가 나오고 다시 1번 더 수행하면 시청자가 누적합된 결과를 얻는다. 1번에 끝내지 않은 이유는 시작 지점에 시청을 하던 시청자가 중간에 끊고 그 중간에 또 다른 시청자가 시청하는 경우를 반영하지 못하기 때문이다. 2번 누적합을 하면 시청자의 수가 커질 수록 변동폭도 그만큼 커진다. 2번 누적합된 배열에 대해 start와 adv_sec + start 지점을 비교해 차이가 가장 큰 시점을 저장하여 변환한다. answer는 start + 1로 갱신하는데 total_time[end] - total_time[start] 는 start + 1에서 end까지의 누적 시청자를 의미하기 때문이다.

• 전체 영상 길이를 초 단위로 변환
• 영상 길이 + 1만큼의 배열 생성
• 광고 영상 길이를 초 단위로 변환
• 각 시청 기록마다 시작 시간, 종료 시간을 초로 변환하여 누적합 배열 좌표에 시청자 반영
• 누적합을 2번 수행
• 초기값은 0초 시작에 max_cnt는 total_time[adv_sec] - total_time[0]이다.
• 1부터 끝까지 순회하되 광고 종료 시각이 범위 밖이면 끝점으로 설정
• 매번 끝지점에서 시작지점을 빼 최댓값인지 검사 후 갱신
• 저장된 시각 변환하여 리턴

python 코드

def solution(play_time, adv_time, logs):
    def str_to_sec(strs):
        h, m, s = strs.split(":")
        return 3600 * int(h) + 60 * int(m) + int(s)
    def sec_to_str(nums):
        h = nums // 3600
        nums %= 3600
        m = nums // 60
        nums %= 60
        return ":".join([str(h).zfill(2) ,str(m).zfill(2), str(nums).zfill(2)])
    total = str_to_sec(play_time)
    adv_sec = str_to_sec(adv_time)
    total_time = [0 for _ in range(total + 1)]
    for log in logs:
        s, e = log.split("-")
        s_sec = str_to_sec(s)
        e_sec = str_to_sec(e)
        total_time[s_sec] += 1
        total_time[e_sec] -= 1
    for i in range(1, len(total_time)):
        total_time[i] = total_time[i] + total_time[i - 1]
    for i in range(1, len(total_time)):
        total_time[i] = total_time[i] + total_time[i - 1]
    max_cnt = total_time[adv_sec]
    answer = 0
    for start in range(1, total):
        end = total if start + adv_sec >= total else start + adv_sec
        if max_cnt < total_time[end] - total_time[start]:
            max_cnt = total_time[end] - total_time[start]
            answer = start + 1
    return sec_to_str(answer)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 순위 검색

문제 풀이

4차원 배열로 정확성은 통과했으나 효율성은 통과하지 못했다. 라이트업을 보니 와일드카득 ㅏ들어갈 모든 경우의 수에 대해 hash키를 만들고 모조리 16가지의 키에 저장하여 키 조회 때마다 정렬된 배열을 불러와 이분탐색을 사용해 시간복잡도를 줄여야 했다. 너무 신박한 풀이라 애초에 혼자서는 해결할 수 없었을 것이다.

• 각 기준에 와일드카드를 넣을 지 결정하는 16가지경우의 수에 대해 삽입합수 정의
• 사전에 모든 키에 대해 조회하여 정렬 수행
• 각 쿼리에 대해 키를 조회하여 lower bound를 찾고 값 저장

python 코드

from collections import defaultdict
from itertools import combinations
from bisect import bisect_left


def solution(info, query):
    tmp = [[0], [1], [2], [3]]
    for i in range(2, 5):
        s = [j for j in range(4)]
        com = combinations(s, i)
        for co in list(com):
            tmp.append(list(co))

    def make_case(info_l, score, tmp):
        user_dict["".join(info_l)].append(score)
        for c in tmp:
            buf = info_l.copy()
            for x in c:
                buf[x] = "-"
            key = "".join(buf)
            user_dict[key].append(score)
    user_dict = defaultdict(list)
    for user in info:
        info_list = user.split()
        info_l = info_list[:-1]
        score = int(info_list[-1])
        make_case(info_l, score, tmp)
    for key in list(user_dict):
        user_dict[key].sort()
    answer = []
    for que in query:
        que_l = que.split()
        q_l = [que_l[0], que_l[2], que_l[4], que_l[6]]
        score = int(que_l[7])
        key = "".join(q_l)
        value_list = user_dict[key]
        answer.append(len(value_list) - bisect_left(value_list, score))
    return answer

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 블록 이동하기

문제 풀이

괴랄한 bfs라 생각했는데 조금만 더 직관이 들어갔으면 해결할 수 있었을지도 모르겠다. 여전히 시뮬레이션 문제는 너무나 어렵다.

상하좌우는 쉬운데 회전 처리가 감이 안잡힌다. 그러나 회전 경로에 칸이 없어야 함은 주어졌으므로 해당 방향으로 평행 이동이 가능하다면 회전 또한 가능함을 보여준다. 그리고 시간 복잡도를 줄이기 위해 양 모터의 좌표를 set에 담아 동일 포지션에서의 재탐색을 막도록 한다. 그리고 회전 시 맵 바깥으로의 이동을 방지하기 위해 전체 맵을 1로 감싸면 연산이 편하다.

• 주어진 좌표에서 움직일 수 있는 좌표들을 담은 배열을 반환하는 함수 정의
  • 상하좌우 및 수평, 수직 상태에서 상하좌우로 움직일 수 있다면 회전가능
• 맵 전체를 외벽으로 감싸서 새로운 지도 완성
• 큐에 초기 모터 좌표 입력, 모터가 2개이므로 좌표도 2개이고 비용은 0부터 시작
• 큐가 없어질 때까지 popleft하여 움직일 수 있는 좌표가 있는지 탐색

python 코드

from collections import deque
def solution(board):
    def move(p1, p2):
        pos = []
        dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        for dr, dc in dirs:
            np1 = (p1[0] + dr, p1[1] + dc)
            np2 = (p2[0] + dr, p2[1] + dc)
            if grid[np1[0]][np1[1]] == 0 and grid[np2[0]][np2[1]] == 0:
                pos.append((np1, np2))
        if p1[0] == p2[0]:
            for i in [1, -1]:
                if grid[p1[0] + i][p1[1]] == 0 and grid[p2[0] + i][p2[1]] == 0:
                    pos.append((p1, (p2[0] + i, p1[1])))
                    pos.append(((p1[0] + i, p2[1]), p2))
        else:
            for i in [1, -1]:
                if grid[p1[0]][p1[1] - i] == 0 and grid[p2[0]][p2[1] - i] == 0:
                    pos.append((p1, (p1[0], p2[1] - i)))
                    pos.append(((p2[0], p1[1] - i), p2))
        return pos
    N = len(board)
    grid = [[1 for _ in range(N + 2)] for _ in range(N + 2)]
    for r in range(N):
        for c in range(N):
            grid[r + 1][c + 1] = board[r][c]

    q = deque([((1,1), (1,2), 0)])
    confirm = set()
    confirm.add(((1,1), (1,2)))
    answer = 0
    while q:
        p1, p2, result = q.popleft()
        if p1 == (N,N) or p2 == (N,N):
            return result
        for k in move(p1, p2):
            if k not in confirm:
                q.append((k[0], k[1], result + 1))
                confirm.add(k)

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

Programmers. 가사 검색

문제 풀이

Trie 사용은 알고 있어서 정확성은 모두 통과했으나 효율성에서 통과하지 못했다. 보아하니 정규식의 길이가 정확히 매칭되어야 하므로 가능한 모든 길이에 trie를 생성하고 길이 별로 쿼리해서 탐색을 줄여야 했다.

• 가능한 단어 길이만큼의 trie, 역순 단어를 저장할 trie 배열 선언
• 각 단어에 대해 단어 길이에 해당하는 trie에 단어, 역순 단어 삽입
• 삽입 시 count를 1 올려 이후 ?가 왔을 때 현재 단어를 거쳐간 단어의 개수를 리턴

python 코드

import sys
sys.setrecursionlimit(100001)
class Trie:
    def __init__(self):
        self.count = 0
        self.child = {}

    def insert(self, word, idx):
        self.count += 1
        if idx == len(word):
            return
        if word[idx] not in self.child:
            self.child[word[idx]] = Trie()
        self.child[word[idx]].insert(word, idx + 1)
    def search(self, word, idx):
        if idx == len(word):
            return self.count
        if word[idx] not in self.child:
            return 0
        return self.child[word[idx]].search(word, idx + 1)

def solution(words, queries):
    trie = [Trie() for n in range(10002)]
    rev_trie = [Trie() for n in range(10002)]
    for word in words:
        trie[len(word)].insert(word, 0)
        rev_trie[len(word)].insert(word[::-1], 0)
    answer = []
    for q in queries:
        x = q.replace("?", "")
        if q[0] == "?":
            answer.append(rev_trie[len(q)].search(x[::-1], 0))
        else:
            answer.append(trie[len(q)].search(x, 0))
    return answer

여기서 참고할 점은 defaultdict를 쓰면 시간이 지연되어 효율성 일부를 맞출 수 없다. 따라서 기본 dict 자료형을 사용해야 한다.