문제 링크

문제 소개

해당 문제는 주어진 단어들의 접두사 중 가장 큰 접두사를 갖고 있는 단어 2개를 출력하는 문제이다.

해당 문제를 봤을 때, 아래와 같이 간단하게 풀어봤다.

import sys


def solution():
    input = sys.stdin.readline
    N = int(input().rstrip('\n'))
    words = [input().rstrip('\n') for _ in range(N)]
    words.sort()
    S, T, cnt = '', '', -1
    for i in range(N):
        for j in range(i + 1, N):
            tempS, tempT, tempCnt = words[i], words[j], 0
            for ts, tt in zip(tempS, tempT):
                if ts == tt:
                    tempCnt += 1
                else:
                    break
            if tempCnt > cnt:
                cnt = tempCnt
                S, T = tempS, tempT
    print(S)
    print(T)


solution()

하지만 이 코드는 여러가지 문제점이 아래와 같았다.

1. O(n^2)임으로 시간 초과
2. 정렬을 했을 때, 문제에서는 최대 접두사를 갖고있는 단어들이 여러개 있다면 먼저 입력된 것을 출력해야 하지만 이 코드에서는 그냥 sort함수를 사용했기 때문에 순서가 뒤죽박죽

2번의 예를 들어보면, 아래와 같이 입력했다고 보자

4
aaad
aaac
aaab
aaaa

이렇게 입력이 들어오면 답은 접두사 aaa를 갖는 aaad와 aaac를 출력해야 한다. 하지만, 위의 코드에서는 sort함수를 사용했기 때문에 [aaaa,aaab,aaac,aaad] 로 바꿔서 결국 aaaa와 aaab라는 잘못된 값을 출력한다.

그럼으로, 이 문제의 핵심은 접두사부분과 들어온 순서에 집중해야 한다.

해결책 1 - Sort

먼저, 우리는 들어온 단어들을 아래와 같이 인덱스를 추가하여 저장해둘 것이다. 그럼으로, 나중에 이 값을 가지고 들어온 순서를 다룰수 있다.

    words = sorted(enumerate(originalWords, start=0), key=lambda x: (x[1]))

그 다음, 각 단어의 최대 길이를 저장할 수 있는 리스트를 만들고 채울것이다. 이렇게 채운 최대 길이를 가지고 답인 것을 출력할 것이다.

우리가 처음에 originalWords에 sort함수를 사용한 것은 2차 반복문을 줄이기 위한 목적이었다. 어처피 서로 최대한 닮은 얘들끼리 비교를 해야하는데, 2차 반복문을 사용해서 쓸모없는 연산을 하는 것보다 sort함수를 사용하면 최대한 비슷한 단어들끼리 정렬되기 때문이다.

그럼으로 반복문을 돌면서 두 단어의 최대 접두사 길이를 구한 다음 이 값을 아까 만들어 놓은 각 단어의 최대 길이를 저장할 수 있는 리스트에 업데이트한다.

이러한 과정을 다 진행했다면, 아래와 같이 2가지 상황에 놓일 것이다.

1. 공통되는 접두사가 없어서, 선 입력된 단어 2개를 출력해야할 경우
2. 공통되는 접두사가 존재해서 중간에 살펴봐서 출력해야할 경우

1번은 입력된 순으로 출력하면 되고, 문제는 2번이다.

우리가 만들어놓은 최대 길이 리스트는 따로 무슨 접두사로 이뤄져있는지 저장해놓지 않았기 때문에, 추가적인 것이 필요하다.

그럼으로 아래의 코드와 같이, step을 나눠서 step 0에서는 해당 단어의 접두사가 최대 접두사 길이인지 확인한다. 그 다음 step 1에서는 마찬가지로 최대 접두사 길이인지 확인하고 step 0에서의 접두사와 같은지 확인하고 만약 같다면 바로 출력하고 종료한다.

해결책 1번의 전체 코드는 아래와 같다.

import sys


def getPrefixCnt(word1, word2):
    cnt = 0
    for w1, w2 in zip(word1, word2):
        if w1 == w2:
            cnt += 1
        else:
            break
    return cnt


def solution1():
    input = sys.stdin.readline
    N = int(input().rstrip('\n'))
    originalWords = [input().rstrip('\n') for _ in range(N)]
    words = sorted(enumerate(originalWords, start=0), key=lambda x: (x[1]))
    prefixLength = [0 for _ in range(N)]
    maxCnt = 0
    for i in range(N - 1):
        tempCnt = getPrefixCnt(words[i][1], words[i + 1][1])
        maxCnt = max(maxCnt, tempCnt)
        prefixLength[words[i][0]] = max(prefixLength[words[i][0]], tempCnt)
        prefixLength[words[i + 1][0]] = max(prefixLength[words[i + 1][0]], tempCnt)
    if maxCnt == 0:
        print(originalWords[0], originalWords[1], sep='\n')
    else:
        step, prefix = 0, ''
        for i in range(N):
            if step == 0 and maxCnt == prefixLength[i]:
                prefix = originalWords[i][:maxCnt]
                step += 1
                print(originalWords[i])
            elif step == 1 and maxCnt == prefixLength[i] and prefix == originalWords[i][:maxCnt]:
                print(originalWords[i])
                break

해결책 2 - HashMap(Dict)

이번에는 문제 힌트에 나와있는 HaspMap을 사용해볼 것이다. 먼저, 해결책 1에서 내용을 HashMap으로 교체하는 중 문제가 발생하였다.

import sys
from collections import defaultdict


def getPrefix(word1, word2):
    cnt = 0
    for w1, w2 in zip(word1, word2):
        if w1 == w2:
            cnt += 1
        else:
            break
    return word1[:cnt], cnt


def solution2():
    input = sys.stdin.readline
    N = int(input().rstrip('\n'))
    originalWords = [input().rstrip('\n') for _ in range(N)]
    words = sorted(enumerate(originalWords, start=0), key=lambda x: (x[1]))
    wordDict = defaultdict(list)
    maxPrefix = ''
    for i in range(N - 1):
        tempS, tempT = words[i], words[i + 1]
        tempPrefix, tempCnt = getPrefix(tempS[1], tempT[1])
        if len(maxPrefix) <= len(tempPrefix):
            maxPrefix = tempPrefix
            wordDict[tempPrefix].append(tempS)
            wordDict[tempPrefix].append(tempT)
    ans = sorted(wordDict[max(wordDict, key=lambda x: len(x))])
    for i in range(2):
        print(ans[i][1])


solution2()

위의 코드에서의 문제점은 바로 앞의 문제 소개부분에서 설명했던 순서부분이 미흡한 부분이다. 그럼으로 이러한 부분을 신경쓰며 코드를 변경해보았다. 수정하는 과정에서 다른 분의 코드도 참고하였다.

먼저, 이 코드의 핵심 부분은 최대 길이를 기준으로 하나씩 줄여보면서 해당 조건이 성립하는 두 단어가 존재할 경우 출력하고 종료한다.

마찬가지로 두 단어의 접두사를 구하는 함수는 아래와 같이 구현하였다.

def getPrefix(word1, word2):
    cnt = 0
    for w1, w2 in zip(word1, word2):
        if w1 == w2:
            cnt += 1
        else:
            break
    return word1[:cnt], cnt

주어진 단어들을 입력받을 때 뒤에서 단어 최대 길이를 기준으로 최대 접두사 길이를 줄여나갈것이기 때문에, 입력받을 때 아래와 같이 받는다.

    for _ in range(N):
        word = input().rstrip('\n')
        words.append(word)
        max_len = max(max_len, len(word))

그리고, 최대 길이를 기준으로 단어를 하나하나씩 살펴볼 것이다. HashMap의 기본 구조는 key = 접두사, value = [단어,해당 단어가 입력된 인덱스]으로 정해둘 것이다.

가장 중요한 점은 단어를 하나하나씩 보면서 접두사를 뽑아내고 뽑아낸 접두사를 기준으로 전에 뽑아낸 접두사가 있을 경우 미리 뽑아낸 접두사를 가진 단어(A)와 지금의 단어(B)를 비교한다.

우리는 지금 최대 접두사 길이가 큰 것들 중 인덱스가 가장 적은 두 조합을 뽑으려는 것이다. 접두사가 있다는 가정하에 단어들의 인덱스를 비교해서 작은 것을 찾아나가다 보면 답을 얻을 수 있을 것이다.

아래는 최종 코드이다.

import sys


def getPrefix(word1, word2):
    cnt = 0
    for w1, w2 in zip(word1, word2):
        if w1 == w2:
            cnt += 1
        else:
            break
    return word1[:cnt], cnt


def solution2():
    input = sys.stdin.readline
    N = int(input().rstrip('\n'))
    words = []
    max_len = 0
    for _ in range(N):
        word = input().rstrip('\n')
        words.append(word)
        max_len = max(max_len, len(word))

    for length in range(max_len, -1, -1):
        wordDict = {}
        word1, wor2 = None, None
        word1Idx, word2Idx = sys.maxsize, sys.maxsize
        for i in range(N):
            croppedWord = words[i][:length]
            if len(words[i]) >= length:
                if wordDict.get(croppedWord):
                    if words[i] != wordDict[croppedWord][0] and word1Idx > wordDict[croppedWord][1]:
                        word1, word1Idx = wordDict[croppedWord]
                        word2, word2Idx = words[i], i
                else:
                    wordDict[croppedWord] = [words[i], i]
        if word1 != None:
            break

    print(word1)
    print(word2)


solution2()