배열 - 문제후기

 

내가 푼 배열 문제

 

문제집 이름이 배열인 만큼 아직 특별한 알고리즘 기법이 나오지 않기 때문에, 거의 모든 문제가 그냥 수수께끼, 수학, 구현력과 관련된 문제였다. 그러나 하나 기억하면 좋을것 같은 문제가 하나 있었다. 이는 [BOJ 3273: 두 수의 합] 문제였다. 

 

 

3273번: 두 수의 합

 

 

처음에 이 문제가 왜 실버4의 문제 티어를 가지고 있는지 몰랐었다. 왜냐하면 이 문제는 그저 배열안에 저장되어 있는 수열중의 원소 두개를 합했을때 특정 N의 값과 일치하는 경우의수를 찾으면 되는 문제였다.

그리고 다행스럽게도 파이썬에는 "from itertools import combination"을 이용하여 리스트안의 원소의 경우의수를 모두 뽑아주는 메써드가 있었기 때문에 " 다른 언어 사용자에게는 어렵게 만들어진 문제인가보다~" 라고 생각하였으나. 시간 초과가 떴다. 이는 아마 combination 라이브러리가 이중배열로 경우의수를 뽑기 때문에 O(N^2)의 시간 복잡도를 가졌기 때문이라 생각한다. 

 

그렇다면 내가 구현해야 하는데... 약 20분정도 이것저것 시도를 해보다가 갑자기 바킹독님께서 말씀하신 배열의 합을 O(N)에 구하는 방법을 말씀하신것이 기억이났다. 

 

 

이는 즉, 미리 수열의 최대 숫자의 길이만큼 배열을 만들고, 이후 N번에 걸쳐서 배열을 탐색할때 이미 탐색 한것은 아까 만들어둔 배열에서, 해당 숫자에 대한 인덱스를 찾아가 0 -> 1로 만들어주는것이다. 단, 수열은 오름차순으로 정렬되어 있어야 한다.

 

이것의 목적은 바로 "내가 탐색해오면서 봐왔던 숫자들은 등장했다고 내가 배열에 저장을 해둘게, 만약에 네가 지금 X라는 숫자가 이전에 있었는지 궁금하다면 그 값을 주면 내가 배열에 저장해뒀는지 알아볼께" 라는 의미이다.

 

예를들면, 위와 같이 77에 도달했을때 합이 100이 되려면 23이 리스트에 있는지 확인해봐야 할텐데, 다행히도 23을 지나쳐왔고, 이를 기록해두었기 때문에 23이 존재함을 알수있었고, 하나의 경우의수를 찾을수있게 되는 것이다. 기억이 안나면 내가 썼던 코드를 다시 살펴보자.

 

import sys
count = 0
n = int(sys.stdin.readline())

arr = list(map(int,sys.stdin.readline().split()))

x = int(sys.stdin.readline())

checked = [0 for i in range(2000000)]

arr.sort()

for i in arr:
    if (checked[x-i]):
        count += 1

    auth[i] = 1

print(count)

 

하지만 이는 바킹독님이 강의에서 다루셔서 운 좋게 써먹은 것이고, 배열도 추가적으로 사용한다. 그러하여 전통적으로 이러한 수열의합을 다룰때 쓰는 기법이 있다고 하는데 이는 바로 "투포인터 알고리즘" 이다.

 

투포인터를 제일 쉽게 이해할수있는 사진

 

두 수의 합의 결과에 따라 좌, 우의 인덱스를 조절하기 위해서는 정렬(오름차순)을 해주어야 한다.

정렬 후 3가지 경우에 따라 투 포인터 탐색을 진행하면 된다.

 

1. 두 수의 합이 x보다 큰 경우 - 더 작은 값을 더해야하므로 end-1
2. 두 수의 합이 x보다 작은 경우 - 더 큰 값을 더해야하므로 start+1
3. 두 수의 합에 도달한 경우 - 발견!

 

Miscellaneous

---

• 아스키 코드 변환 ord(string) => integer, chr(int) => string

 

• value = [int(sys.stdin.readline()) for _ in range(3)] 지정된 길이로 배열 저장

 

• for i in str(result_str):
      result_int.append(i)   문자열 숫자, 1의자리 혹은 글자단위로 쪼개서 리스트 저장

 

• 계산에서 괄호 잘쳐주기 (확인 좀 잘해라..)

 

• 배열 index 고려해서 길이 잘 정해주기