네이버 코딩테스트 후기

네이버 월간영입 코딩테스트 후기. 테스트는 Codility 플랫폼에서 진행됐다. 총 3문제, 160분이었다. 테스트는 온라인 비대면으로 진행됐으며 서류합격발표(화요일) 후 해당 주 일요일 밤까지가 테스트 마감 기한이었다.

문제는 모두 영어로 출제됐고 codility의 다른 lesson questions보다는 테스트 케이스가 나름 다양하게(?) 주어졌다. 문제당 기본 3-4개정도.. 난이도는 중 정도였다. 올해 치뤘던 카카오, SK 코테와 비교해보면 제일 어렵긴 했다.

Q1

[문제설명]

• 문자열 S와 이름 배열 L이 주어진다.
• 문자열 S의 문자들로 주어진 배열의 각 이름을 몇개나 만들 수 있을지 세어보고 최대 제작가능 횟수를 반환한다.
• S=LILLYBILLYBOO, L=[‘BILL’, ‘MARIA’, ‘LILLY’] 일때 BILL은 2번, MARIA는 0번, LILLY는 1번 만들 수 있다. 따라서 2를 반환해야 한다.

[풀이]

def solutionTask1(S, L):
    scnt = dict()
    maxret = 0

    for s in S:
        if s not in scnt.keys():
            scnt[s] = 1
        else:
            scnt[s] += 1
    # print(scnt)

    for name in L:
        ncnt = dict()
        for c in name:
            if c not in ncnt.keys():
                ncnt[c] = 1
            else:
                ncnt[c] += 1
        # print(name, ncnt)

        curret = 999
        for key in ncnt.keys():
            if key not in scnt.keys():
                curret = 0
                break

            # print(key, scnt[key], ncnt[key], curret, scnt[key] // ncnt[key])
            curret = min(curret, scnt[key] // ncnt[key])

        maxret = max(maxret, curret)

    return maxret

• 부분합 알고리즘에서 사용했던 개념을 일부 사용했다

Q2

[문제설명]

• 배열 A와 기준 R이 주어진다.
• 배열 A에서 R 길이만큼을 빼고 남은 값들의 종류의 개수가 최대가 되는 경우를 찾아, 그 종류의 개수를 반환하라
• 배열의 순서는 바꿀 수 없다. A의 길이는 최대 10만. 배열의 원소 값도 최대 10만이었던걸로 기억한다.
• A=[2, 3, 1, 4, 2, 2], R=3 일때 [4, 2, 2]를 빼면 남은 값의 종류의 개수가 3으로 최대가 된다.

[풀이1]

def solutionTask2(A, R):
    # 가장 종류 적은 부분 R을 찾는다
    minidx, minuniq = 0, 2e9
    curcnt = dict()

    # 초기값
    for a in A[:R]:
        if a not in curcnt.keys():
            curcnt[a] = 1
        else:
            curcnt[a] += 1
    print(curcnt)

    # 배열 순회하며 가짓수가 최소가 되는 start idx(minidx) 찾는다
    for i in range(len(A) - R):
        curuniq = len(list(curcnt.keys()))
        if curuniq < minuniq:
            minuniq = curuniq
            minidx = i
        print(i, curuniq, minuniq)

        # R개 부분의 가짓수 저장 dict 업데이트
        curkey, nextkey = A[i], A[R + i]
        if curcnt[curkey] == 1:
            del curcnt[curkey]
        else:
            curcnt[curkey] -= 1

        if nextkey not in curcnt.keys():
            curcnt[nextkey] = 1
        else:
            curcnt[nextkey] += 1
        print(curkey, nextkey, curcnt)

    del A[minidx:minidx + R]
    return len(list(set(A)))

• 처음엔 값의 종류가 가장 적은 R길이의 부분배열을 찾으면 될거라고 생각했다.
• 이경우 예외케이스가 생긴다. A=[2, 3, 1, 1, 2], R=2 일때 [1, 1]을 빼는 것 보다 [1,2] 를 빼는게 남은 원소의 종류의 개수 더 많기 때문.

[풀이2]

def solutionTask222(A, R):
    maxcnt = 0
    for startidx in range(len(A)-R):
        curcnt = len(set(A[:startidx]+A[startidx+R:]))
        maxcnt = max(maxcnt, curcnt)

    return maxcnt

• 시간이 얼마 안남아서 어쩔 수 없었다
• 알고리즘 없이 그냥 전체탐색.. tc는 모두 맞았지만 large testset 에서 백퍼 timeout 발생할거라고 예상된다.

Q3

[문제설명]

• N * M 의 지도 B가 주어진다. 지도의 각 셀은 # 혹은 . 로 표현된다.

• 지도에는 patrol, submarine, destroyers라는 세가지 타입의 배가 #로 표시되어있다.

  1. Patrol
  => #
  2. Submarine
  => ##, #
         #
  3. Destroyers
  => ###, ##, ##, #  ,  #  , #
          #    #  ##   ##    #
                             #

• ‘.’ 은 빈 공간을 의미한다.

• 지도에서 patrol, submarine, destroyers의 갯수를 각각 세서 반환한다.

• B=[‘.#..#’, ‘##..#’, ‘…#.’] 일때 [1, 1, 1]을 반환한다.

[풀이]

destroyers = [
    [[1, 0], [2, 0]],
    [[0, 1], [0, 2]],
    [[1, 0], [0, 1]],
    [[1, 0], [1, 1]],
    [[0, 1], [1, 1]],
    [[1, -1], [1, 0]],
]


def isD(B, a, b, M, N):
    whichShape = -1

    for id, shape in enumerate(destroyers):
        flag = True
        for addA, addB in shape:
            if a + addA < 0 or b + addB < 0 or a + addA >= N or b + addB >= M or B[a + addA][b + addB] == ".":
                flag = False
                break

        if flag == True:
            whichShape = id
            break

    return whichShape

def printB(B):
    for line in B:
        print(line)

def solution(B):
    N, M = len(B), len(B[0])
    ret = [0, 0, 0]
    B = list(list(col) for col in B)
    for a, col in enumerate(B):
        for b, cell in enumerate(col):
            print(a, b, cell)
            printB(B)
            if cell == '#':
                # 어떤 모양인지 체크한다.
                di = isD(B, a, b, M, N)
                if di >= 0:
                    # Destroyer인 경우
                    B[a][b] = '.'
                    B[a + destroyers[di][0][0]][b + destroyers[di][0][1]] = '.'
                    B[a + destroyers[di][1][0]][b + destroyers[di][1][1]] = '.'

                    ret[2] += 1
                else:
                    if a + 1 < N and B[a + 1][b] == '#':
                        # Submarine shape1
                        B[a][b] = '.'
                        B[a + 1][b] = '.'

                        ret[1] += 1
                    elif b + 1 < M and B[a][b + 1] == '#':
                        # Submarine shape2
                        B[a][b] = '.'
                        B[a][b + 1] = '.'

                        ret[1] += 1
                    else:
                        # Patrol
                        B[a][b] = '.'
                        ret[0] += 1
    return ret

좌측 상단부터 훑어가면서 # 인경우 세가지 배 중 어느타입에 속하는지 확인후 해당 셀을 ‘.’ 으로 바꾼다.

• string 문자열은 인덱스로 접근해 값 할당할 수 없으므로 초반에 받아온 문자열 배열을 리스트로 변환해준다.