문제풀이
A가 1~N까지의 수가 단 한 번씩만 나오는 순열이 맞으면 1반환, 아니면 0을 반환하는 문제이다.
N is an integer within the range [1..100,000];
each element of array A is an integer within the range [1..1,000,000,000].
라는 조건으로 보아 시간복잡도는 O(nlogn)안에 해결해야 할 것 같고,
A의 요소의 범위가 10억인걸 보아 메모리를 신경써야 하는 문제같다.
보통의 코딩문제 메모리 제한이 128MB ~ 512MB 정도이니 리스트는 크기 500만 이내, Set이나 딕셔너리는 크기 100만 이내로 제한해야 한다.
고민 포인트
A가 순열인지는 무조건 배열을 다 돌아야지 알 수 있음 -> 순열의 수의 수가 A의 크기이기 때문
그렇다면 순열이 맞는지 확인하는 것보다 순열이 아닌 조건에서 바로 return 0으로 쳐낸 다음, 반복문을 문제없이 다 돌았다면 순열이 맞다는 방식으로 판단하는게 좋을 것 같다.
순열은 1부터 시작해서 N의 최대 크기가 100000이니, 만약 100000이상인 수가 나오면 볼 것도 없이 바로 순열이 아니다. 그리고 중복된 수도 나올 수가 없으니 이 두 조건을 불충족하면 바로 순열 탈락이다.
2가지 방법을 생각해봤다.
set 방법
Set생성하고 반복문으로 A순환하며 처음 발견한 수 Set에 add하기
중복된 수 나오면 바로 0반환
100000초과인 수 나오면 바로 0반환
무사히 반복문 끝났다? -> 순열 확정!
체크 배열 방법
A의 크기만큼(10만 크기 이하)의 False배열 생성
반복문 돌며 해당하는 수의 인덱스 True로 변환
중복된 수가 나오거나 10만 초과인 수 나오면 바로 return 0
반복문 무사히 끝나면 return 1
Set이 해시테이블을 사용하기 때문에 배열보다 메모리를 아주 조금 더 사용한다는 말에 이번엔 Set말고 배열을 이용해 보기로 하였다.
최종 제출 코드
체크 배열 방법
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
check_arr = [False] * (len(A) + 1) # 0 인덱스는 안 쓰니까 +1
for num in A:
if num > len(A):
return 0
elif check_arr[num]: # 중복인 수 발견
return 0
else: # 해당 수가 미발견 상태이면
check_arr[num] = True
return 1
# A가 순열이면 1 반환, 아니면 0반환
# 체크 배열 방법
# A의 크기만큼(10만 크기 이하)의 False배열 생성
# 반복문 돌며 해당하는 수의 인덱스 True로 변환
# 중복된 수가 나오거나 10만 초과인 수 나오면 바로 return 0
# 반복문 무사히 끝나면 return 1
Set으로 하면 훨씬 간결하게 할 수 있다해서 그냥 Set도 해봤다. 리스트를 Set으로 변환하고 변환된 Set의 크기가 기존 배열 크기와 같고 요소들의 크기가 모두 A의 길이 이하이면 된다.
set 방법
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
N = len(A)
visited = set(A) # 중복 제거된 A
# 길이가 N과 같고 최대값이 N과 같으면 순열
if (len(visited) == N) and (max(visited) == N):
return 1
return 0
