문제 개요
숫자 n과 배열 rounds가 주어진다고 가정해 보겠습니다. 우리에게는 1부터 n까지 번호가 매겨진 n개의 서로 다른 섹터로 이루어진 원형 트랙이 있습니다. 이 트랙 위에서 경주가 열리며, 경주는 총 m개의 라운드로 구성됩니다. i번째 라운드는 rounds[i-1]번 섹터에서 출발하여 rounds[i]번 섹터에서 종료됩니다. 예를 들어 첫 번째 라운드는 rounds[0]에서 시작해 rounds[1]에서 끝납니다.
트랙의 번호는 반시계 방향으로 섹터 번호가 오름차순으로 증가하며, 우리의 목표는 경주 중 가장 많이 방문된 섹터를 찾아 오름차순으로 정렬해 반환하는 것입니다.
예시로 이해하기
입력이 n = 4, rounds = [1, 3, 1, 2]라고 해봅시다. 이때 출력은 [1, 2]가 됩니다.
경주는 1번 섹터에서 시작합니다. 방문되는 섹터의 순서는 다음과 같습니다.
[1, 2, 3(첫 번째 라운드 종료), 4, 1(두 번째 라운드 종료), 2(세 번째 라운드 종료)]
여기서 1번과 2번 섹터는 두 번씩 방문되어 가장 많이 방문된 섹터가 되고, 3번과 4번 섹터는 한 번만 방문됩니다.
해결 접근 방법
이 문제는 각 섹터의 방문 횟수를 누적해 기록한 뒤, 최대 방문 횟수를 가진 섹터들을 추출하는 방식으로 해결할 수 있습니다. 단계별 과정은 다음과 같습니다.
- 각 섹터의 방문 횟수를 저장할 딕셔너리 d를 생성하고, 1부터 n까지 모든 섹터의 값을 0으로 초기화합니다.
- 출발 섹터인 rounds[0]의 방문 횟수를 1로 설정합니다.
- 각 라운드 구간을 순회하며 방문 횟수를 누적합니다.
- rounds[i] > rounds[i-1]인 경우(같은 바퀴 안에서 이동): rounds[i-1]+1부터 rounds[i]까지의 섹터 방문 횟수를 1씩 증가시킵니다.
- 그렇지 않은 경우(바퀴를 넘어가는 이동): rounds[i-1]+1부터 n까지, 그리고 1부터 rounds[i]까지의 섹터 방문 횟수를 각각 1씩 증가시킵니다.
- 최대 방문 횟수 curr와 결과 리스트 out을 출발 섹터 기준으로 초기화합니다.
- 1부터 n까지 모든 섹터를 확인하면서, 방문 횟수가 현재 최댓값보다 크면 최댓값과 결과를 갱신하고, 횟수가 같으면 해당 섹터를 결과에 추가합니다.
- 마지막으로 out을 오름차순으로 정렬해 반환합니다.
Python 구현 예제
다음 구현을 통해 더 잘 이해할 수 있습니다.
def solve(n, rounds):
d = {}
for j in range(1, n+1):
d[j] = 0
d[rounds[0]] = 1
for i in range(1, len(rounds)):
if rounds[i] > rounds[i-1]:
for j in range(rounds[i-1]+1, rounds[i]+1):
d[j] += 1
else:
for j in range(rounds[i-1]+1, n+1):
d[j] += 1
for j in range(1, rounds[i]+1):
d[j] += 1
curr = d[rounds[0]]
out = [rounds[0]]
for i in range(1, n+1):
if i != rounds[0]:
if d[i] > curr:
curr = d[i]
out = [i]
elif d[i] == curr:
out = out + [i]
return(sorted(out))
n = 4
rounds = [1, 3, 1, 2]
print(solve(n, rounds))
입력
4, [1,3,1,2]
출력
[1, 2]
복잡도 분석
시간 복잡도는 각 라운드마다 실제로 이동한 구간의 길이만큼 순회하므로, 최악의 경우 O(n × m)입니다. 공간 복잡도는 섹터 개수에 비례하여 O(n)입니다. 입력 크기가 작거나 중간 수준일 때 충분히 효율적으로 동작하는 직관적인 시뮬레이션 기반 풀이입니다.