문제 링크

문제 소개

해당 문제는 주어진 수열에서 수가 중복되지 않는 연속된 수들의 조합의 개수를 물어보는 문제이다.

해당 문제를 풀 때, 아래의 방법과 같이 러프하게 풀어봤다.

import sys


def check(arr):
    if len(set(arr)) == len(arr):
        return True
    return False


def solution():
    input = sys.stdin.readline
    N = int(input().rstrip('\n'))
    nList = list(map(int, input().split()))
    ans = 0
    for i in range(N):
        for j in range(i + 1, N + 1):
            if check(nList[i:j]):
                ans += 1
    print(ans)


solution()

해당 코드는 당연히 시간초과가 발생하였다. 그 이유는 아래와 같다.

1. N이 최대 100000이기 때문에 O(n^2)인 코드 사용
2. 슬라이싱을 사용
3. 중복 체크하는 과정에서 set으로 변환

위의 문제점을 수정하기 위해 여러가지 방법으로 접근해보았다.

접근 1 : dp

해당 접근 방법의 핵심은 먼저 시작이 0번째 인덱스일때, 1부터 N-1까지 슬라이싱을 통해 0번째 인덱스에서 시작했을 때 각각 인덱스에 조건 성립(중복이 안되는 조합)이 되는지를 저장해둔다.

그리고, 1번째 인덱스가 시작될 때는 0번째 인덱스에서 조건이 성립되는 인덱스는 별다른 계산없이 이어받고 마지막 값만 조건 성립이 되는지 확인하고 업데이트한다.

예를 들어, [1,2,3,1,2]라는 수열이 있을 때 0을 시작점으로 잡고 조건이 성립되는 경우를 리스트로 표현하면 [True,True,True,False,False]가 될것이다.

그 다음, 1을 시작점으로 잡게되면 0부터 시작했을 때 조건이 성립했던 인덱스들은 자동으로 1을 시작점으로 두었어도 조건이 성립될 것이다. 그럼으로 시작점 이전값은 False로 바꿔주고, 2번째 인덱스까지는 이전 리스트가 True이기 때문에 마찬가지로 적용해준다. 그리고 마지막 3번째 인덱스는 추가로 계산을 하여 1을 시작점으로 두었을 때 조건 성립 리스트는 [False,True,True,True,False]가 될것이다.

이러한 방식을 통해 초기 방식에서 중복 체크하는 부분 중 쓸모없는 부분을 줄였다.

하지만 이러한 방식에도 불구하고 시간초과가 발생하였는데 역시 O(n^2)부분이 문제였다.

import sys


def check(arr):
    if len(set(arr)) == len(arr):
        return True
    return False

def solution3():
    input = sys.stdin.readline
    N = int(input().rstrip('\n'))
    nList = list(map(int, input().split()))
    temp = [0 for _ in range(N)]
    ans = 0
    # 1 2 3 1 2
    for i in range(N):
        if check(nList[:i+1]):
            temp[i] = 1
            ans += 1
        else:
            break
    # print(temp)
    for i in range(1,N):
        for j in range(i):
            temp[j] = 0
        for j in range(i,N):
            if temp[j]:
                temp[j] = 1
                ans += 1
            else:
                if check(nList[i:j+1]):
                    temp[j] = 1
                    ans += 1
                break
        # print(temp)
    # 1 1 1 0 0
    # 0 1 1 1 0
    # 0 0 1 1 1
    # 0 0 0 1 1
    # 0 0 0 0 1
    print(ans)

solution3()

접근 2: two pointer

우선, 중복 체크를 하기 위해 리스트를 두어 포인터를 이동하면서 중복되는지 안되는지 확인할 것이다.

이렇게 포인터를 옮기는 과정에서 아래의 부분이 가장 핵심적이다.

    dup = [False for _ in range(1000001)]
    p1,p2,ans = 0,0,0
    while p1<N and p2<N:
        if not dup[nList[p2]]:
            dup[nList[p2]] = True
            p2 += 1
            ans += p2-p1
        else:
            dup[nList[p1]] = False
            p1 += 1

우선 뒤의 포인터를 하나씩 이동해보면서 중복인지 아닌지 확인한다. 만약 중복이 아니라면 중복 체크를 해주고 뒤의 포인터를 뒤로 하나씩 움직인다. 그리고 경우의 수를 더해주기 위해 start와 end의 거리를 더해주었다.

예를 들어, [1,2,3,1,2]에서 p1=0,p2=2일 때 나올수 있는 조합은 [3],[2,3],[1,2,3]임으로 총 3개이다. 만약, p1=1,p2=3일 때 나올수 있는 조합은 [1], [3,1], [2,3,1]임으로 마찬가지로 3개이다.

만약, 중복이 발생할 경우 해당 시작점을 False로 초기화하고 앞의 포인터를 앞으로 이동하여 초기화해준다.

이러한 방식으로 문제를 풀었고 최종 코드는 아래와 같다.

최종 코드

import sys


def solution3():
    input = sys.stdin.readline
    N = int(input().rstrip('\n'))
    nList = list(map(int, input().split()))

    dup = [False for _ in range(1000001)]
    p1,p2,ans = 0,0,0
    while p1<N and p2<N:
        if not dup[nList[p2]]:
            dup[nList[p2]] = True
            p2 += 1
            ans += p2-p1
        else:
            dup[nList[p1]] = False
            p1 += 1
    print(ans)

solution3()