Runchi

n개의 서로 다른 양의 정수 a1, a2, …, an으로 이루어진 수열이 있다. ai의 값은 1보다 크거나 같고, 1000000보다 작거나 같은 자연수이다. 자연수 x가 주어졌을 때, ai + aj = x (1 ≤ i < j ≤ n)을 만족하는 (ai, aj)쌍의 수를 구하는 프로그램을 작성하시오.

• 입력 첫째 줄에 수열의 크기 n이 주어진다. 다음 줄에는 수열에 포함되는 수가 주어진다. 셋째 줄에는 x가 주어진다. (1 ≤ n ≤ 100000, 1 ≤ x ≤ 2000000)
• 출력 문제의 조건을 만족하는 쌍의 개수를 출력한다.

문제풀이
문제를 간단하게 요약하면 두수릏 합쳐서 어떤수를 나오게 하는 쌍의 갯수를 찾아라는 말인데 가장 단순하게 생각을 해보면 0번째 index와 1,2,3… 더해서 비교 1번째 index와 2,3,4… 더해서 비교 이러한 방식이 가능한데 이와같이 하게되면 시간복잡도 측면이나 코드의 길이나 직관적인 면도 덜할것 같아서 다른 방법을 생각해본다 그래서 생각해낸 방법은 target에 해당되는 세번째 입력값에서 뺀값이 list안에 있는지 확인하는 IDEA를 사용해보려했다.

내 풀이1 🏆

n = int(input())

my_list = [int(i) for i in input().split(' ')]

target = int(input())
cnt = 0
for i in my_list:
  
    if (target - i) in my_list:
        del my_list[my_list.index(target-i)]
        del my_list[my_list.index(i)]
        cnt+=1

보면 input으로 받은 값을 list compre를 이용해 int값으로 바꿔준다음 target에서 element값을 뺀것이 list안에 있는지 체크하고 있으면 재 카운팅을 방지하기 위해 del을 사용해주었다.

그런데 이 코드의 문제는 del연산자체가 n만큼의 복잡도를 가지고 이미 지나간 i같은 경우에는 굳이 제거를 안해줘도 됐을거란 생각이다.

결론적으로 시간초과로 실패했다.

내 풀이2 🏆

n = int(input())

my_list = [int(i) for i in input().split(' ')]

target = int(input())
cnt = 0
for i in my_list:
  
    if (target - i) in my_list:
        cnt+=1

print(cnt//2)

del을 하는 대신 전체를 cnt 하고 쌍이므로 //2 를 해주었는데 문제는 in 연산자 자체도 n만큼의 복잡도를 가지고 있기때문에 시간이 초과되었다.

내 풀이3 🏆

n = int(input())

my_list =input().split(' ')

target = int(input())
cnt = 0
for i,v in enumerate(my_list):
    for j in range(i+1,len(my_list)):
        if int(v) + int(my_list[j])  == target:
            cnt+=1
            break

print(cnt)

그래서 enum을 사용해보았지만 여전히 시간초과가 떴고, 이 코드는 처음에 생각한 가장 단순한 IDEA이고, 코드가 복잡해 보이기에 안쓰려고 했다.

내 풀이4 🏆

n = int(input())

my_list = set(input().split(' '))

target = int(input())
cnt = 0
for i in my_list:
    if str(target - int(i)) in my_list:
        cnt+=1
print(cnt//2)

그래서 이렇게 list 대신 set을 사용하여 in을 사용해주게 되면 1~n까지의 복잡도를 가지고 int처리도 list를 따로 만들어 처리하는게 아닌 연산할때만 순간적으로 처리하게 변경해줬다.