안녕하세요. 주말에 네이버 코테를 보고 쓰는 첫 알고리즘 글이네요.
네이버 코테 후기도 대충 써보고 싶은데 문제 복기를 해도 되는지 모르겠습니다.
2시간에 총 4문제 출제되었고 테스트 케이스 정답 기준으로 3솔을 했는데 결과는 어떨지 모르겠습니다..!!
여튼 오늘 푸는 문제는 카카오 인턴십 문제인 lv.3 보석 쇼핑입니다.
문제는 보석 쇼핑을 하는데, 보석의 번호를 연속적으로 구매한다고 할 때, 모든 종류의 보석을 살 수 있는 가장 짧은 구간을 찾는 문제입니다.
예제에서 보면, 1~7 구간을 모두 구매해도 모든 종류의 보석을 살 수 있지만,
3~7로만 구매해도 충족되기 때문에 이 경우 3~7이 정답이 됩니다.
제가 푼 방식은 다음과 같습니다.
0) 구간의 시작점과 끝을 가리키는 left, right 포인터를 선언합니다. (투 포인터)
# 전체 보석의 종류와 개수
types = set(gems)
n = len(types)
# 각 보석별 마지막으로 등장한 위치 기록용
total = defaultdict(int)
# 등장한 보석 종류를 기록
q = set()
# 전체 보석이 등장한 구간들 저장
result = []
# 구간 중 왼쪽을 가리키는 포인터 선언
left = 0
# right 포인터를 한칸씩 이동해간다
for right, gem in enumerate(gems):1) 가장 짧은 구간이 되려면 가장 최근에 등장한 위치 기준으로 종류를 모두 모았을 때가 후보일 것이다. ( 처음엔 먼저 완성되기만 하면 최단일거라 생각했지만 이후 더 짧은 구간이 나올 수 있다는 걸 깨달았습니다.)
2) right 포인터를 한 칸씩 이동하면서(for문) 처음 등장한 이후로 다시 등장한 보석은 등장한 위치를 갱신합니다. 그러다 구간의 맨 처음에 해당하는 보석이 다시 등장하면 구간의 시작점(left)을 옮겨야 합니다. 이 때, left는 등장한 종류의 보석들 중에서 가장 왼쪽에 있는 것까지 옮깁니다. (예제에서 DIA가 다시 등장한 부분에서는 현재까지 등장한 보석의 종류는 {'DIA', 'RUBY'} 이므로 두 보석이 최근 등장한 위치 중 가장 작은 값 (RUBY='2')까지 움직입니다
if gem in q:
'''
보석 구간 중에 첫 보석인 경우에는 현재까지 등장한 종류가 지켜지는 한도까지 left를 옮긴다
'''
if gem == gems[left]:
total[gem] = right
temp = right
for g in q:
temp = min(temp, total[g])
left = temp
# 구간의 첫 보석이 아닌 경우에는 그냥 최근 등장한 위치만 수정해준다
else:
total[gem] = right
# 등장하지 않은 보석을 기록한다
else:
q.add(gem)
total[gem]= right3) 그러다 보석의 종류가 총 종류의 수와 같아질 때마다 정답을 기록합니다. 이 때, LEFT가 이전 정답 후보와 바뀌지 않은 경우 중복되므로 기록하지 않습니다.
if len(q) == n:
if not result:
result.append([left+1, right+1])
if left+1 != result[-1][0]:
result.append([left+1, right+1])
4) 마지막으로 구간의 길이와 시작점의 위치로 정렬 후 가장 작은 값을 리턴합니다.
result = sorted(result, key=lambda x :[x[1]-x[0], x[0]])
return result[0]Level 3 치고는 복잡한 알고리즘 없는 구현 문제라 쉽게 느껴진 것 같습니다.
다만, 테스트 케이스 결과가 없는 시험이었다면 예외 케이스에 무참히 썰렸을 것 같아
생각하는 능력을 좀 더 길러야겠습니다.
또한, 현재 코드는 left와 같은 보석이 등장할 때마다 left를 바꿔주는데 사실
보석의 종류가 모두 모일때마다 left를 찾는 게 더 효율적일 수 있다는 생각이 듭니다.
혼자서 코드를 개선해봐야 겠습니다.
시간 복잡도 : O(N) / N : 보석의 개수, M : 보석의 종류
각 보석을 한 번씩만 탐색하면서 정답을 찾아낼 수 있다.
