Array 중복 확인

ASCII 방식의 Array 중복 확인

• boolean 방식으로 index를 설정하고 전부 false로 둔 뒤 index를 돌았을 때, true값이 이미 있으면 중복임을 확인 가능

Unicode를 이용한 Array 중복 확인

• 2의 20승 + 2의 16승이 = 1,114,112 값이므로 HashMap을 사용하는것이 좋다.

Bit Operator(비트 연산자)

• 하나의 숫자에 여러가지 의미를 담고 싶을 때 사용하는 연산자
  • 1, 2, 4, 8, 16으로 각각의 고유한 비트 값이어서 더하더라도 구분이 가능해짐.
• 담을 수 있는 데이터 값이 한정적이므로 a~z까지 소문자로 데이터를 등록한다.
• 쉬프트 연산을 이용해서 구현이 가능하다.

추가 배열을 생성할 수 없다면?

• 두개의 포인터를 사용해서 하나의 포인터는 해당 값만큼 검사, 다른 포인터는 배열의 끝까지 검사하는 방식
  • O(n2제곱)
• Quick sort(퀵 정렬) 방식으로 한번 돌 때 값의 옆자리까지 검사해서 중복된 값이 있는지 확인
  • O(n log n)