마음대로 개발 LIFE

** 철저히 주관적이고 개인적인 고민과 결과를 기록하는 글입니다.

코딩테스트 공부를 본격적으로 시작하기 앞서 어떤 언어로 준비할 것인지 많은 고민을 했다.

고민의 내용과 결과를 기록해두고자 한다.

파이썬의 이점

문법이 간결하다.

같은 내용을 구현할 때 드는 시간이 적다.

자바의 이점

어차피 자바를 주력언어로 사용할 거라면 (내 상황) 언어에 익숙해질 수 있다.

미약하게나마 파이썬으로 코딩테스트 공부를 하면서

간결한 문법에 익숙해져 있었다.

간단한 문제를 자바로 풀어보며 차이를 느껴보고자 했다.

자바 코드

import java.util.*;

class Main {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int inputNumber = scanner.nextInt();
    for (int i = inputNumber; i > 0; i--) {
      System.out.println(i);
    }
    scanner.close();
  }
}

입력 받은 숫자를 1까지 감소시키며 출력하는 아주 간단한 문제를 자바로 구현했다.

이를 파이썬 코드로 바꾸면,

파이썬 코드

n = int(input())
for i in range(n):
    print(n - i)

ㅋㅋㅋㅋ

구글에 '코딩테스트 파이썬 vs 자바'로 검색해서 나오는 대부분의 글을 다 읽어봤는데,

많은 사람들이 기업 코딩테스트 수준에서는 자바로 풀어도 시간이 부족할 정도로 나오지 않을 것이라고 말한다.

중급자 이상이 되면, 구현을 떠올리는 과정이 어렵지

익숙한 언어로 구현하는 것은 일도 아니라고 한다.

하지만 분명 구현하거나 수정하는 데 소요되는 시간이 길어지면

그만큼 히든 케이스를 찾거나 고민할 수 있는 시간이 줄어드는 것은 확실할 거라 생각한다.

이런 저런 이유로 오래 고민하다가..

결국 자바로 공부를 시작하기로 했다.

코딩테스트 공부를 하면서 동시에 자바 언어로 여러 알고리즘을 구현해보고 언어에 익숙해지는 과정,

그리고 어려운 문제를 고민하면서 자바의 자료구조도 뜯어볼 수 있을테니,

일석이조의 효과를 누리는 것이 낫겠다고 판단했다.

웬만한 문제 풀이도 구글에 자바로 나와있고, 백준에 많은 코드도 공유되어 있으니

공부하는 데에도 큰 문제가 없겠다는 생각.

단기적으로 공부할 것이 아니고,

장기적으로 내가 목표로 하는 수준(골드 2~3)에 도달하는 데에는 언어가 큰 지장을 주지 않을 것이라고 판단했다.

적어도 자바에 더 익숙해질 수 있으니 그걸로 됐다!

문제 링크

https://www.acmicpc.net/problem/10989

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1

10
5
2
3
1
4
2
3
5
1
7

예제 출력 1

1
1
2
2
3
3
4
5
5
7

틀린 풀이

import sys

n = int(sys.stdin.readline().rstrip())
array = []

for _ in range(n):
    array.append(int(sys.stdin.readline().rstrip()))

for _ in range(n):
    for i in range(n - 1):
        if array[i] > array[i + 1]:
            array[i], array[i + 1] = array[i + 1], array[i]

for number in array:
    print(number)

이유

• 메모리 초과
  • 메모리를 줄이려고 버블 정렬을 써가며 별짓을 다 했으나, 10,000,000 크기의 리스트를 줄일 수 없어 시실패하였다.

맞은 풀이1

import sys
n = int(sys.stdin.readline().rstrip())
count_array = [0] * 10001

for i in range(n):
    count_array[int(sys.stdin.readline().rstrip())] += 1

for i in range(10001):
    if count_array[i] != 0:
        for j in range(count_array[i]):
            print(i)

접근 방식

• 계수 정렬을 사용!
  • 입력값의 범위가 10,000 이하이므로, 리스트의 크기가 10,000,000에서 10,000으로 줄어든다.

정리

• 계수 정렬의 존재와 사용 방법을 기억하자.

문제 링크

https://www.acmicpc.net/problem/2108

문제

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

예제 입력 1

5
1
3
8
-2
2

예제 출력 1

2
2
1
10

예제 입력 2

1
4000

예제 출력 2

4000
4000
4000
0

예제 입력 3

5
-1
-2
-3
-1
-2

예제 출력 3

-2
-2
-1
2

예제 입력 4

3
0
0
-1

예제 출력 4

0
0
0
1

(0 + 0 + (-1)) / 3 = -0.333333... 이고 이를 첫째 자리에서 반올림하면 0이다. -0으로 출력하면 안된다.

내 풀이

import sys
from collections import Counter

n = int(sys.stdin.readline().rstrip())

array = []
for i in range(n):
    array.append(int(sys.stdin.readline().rstrip()))

array.sort()

s = sum(array)
max_number = max(array)
min_number = min(array)
length_array = len(array)

# 최빈값 구하는 로직
counter = Counter(array)
mode = counter.most_common() # 숫자:빈도 를 나타내는 튜플을 빈도 순으로 나열
mode = [i for i in mode if i[1] == mode[0][1]] # 빈도수가 최빈값과 같은 튜플들만 남긴다
mode_result = []

# 빈도가 아닌 숫자만 남긴다
for i in mode:
    mode_result.append(i[0])

mode_result.sort() # 정렬

# 최빈값이 2개 이상이면 2번째로 작은 수를, 아니면 최빈값을 저장한다.
if len(mode_result) >= 2:        
    mode_number = mode_result[1]
else:
    mode_number = mode_result[0]

# 출력
print(round(s / n))
print(array[length_array // 2])
print(mode_number)
print(max_number - min_number)

접근 방식

• 평균, 중앙값, 길이는 쉬우니까 pass
• 최빈값은 Counter 라이브러리의 most_common() 모듈을 사용하였다.
  • [1, 1, 1, 2, 3, 3, 3] 을 [(1, 3), (3, 3), (2, 1)] 로 바꿔주는 라이브러리
  • 잘 조작하여 조건에 맞는 최빈값을 구하였다.

남의 풀이

import sys
from collections import Counter
n = int(sys.stdin.readline())
nums = []
for i in range(n):
    nums.append(int(sys.stdin.readline()))
nums.sort()
nums_s = Counter(nums).most_common()
print(round(sum(nums) / n))
print(nums[n // 2])
if len(nums_s) > 1:
    if nums_s[0][1] == nums_s[1][1]:
        print(nums_s[1][0])
    else:
        print(nums_s[0][0])
else:
    print(nums_s[0][0])
print(nums[-1] - nums[0])

접근 방식

• 다른 것은 볼 필요 없고, 최빈값 출력하는 로직만 보면 된다.
• 비슷한 로직인데, Counter 객체를 출력할 때 더 간결하게 사용하였다.
  • 숫자 리스트 길이가 2 이상일 때, 첫번째 빈도와 두번째 빈도가 같다면 두번째 숫자를 출력
  • 첫번째 빈도가 더 크다면, 첫번째 숫자를 출력!

정리

• 최빈값과 빈도를 다룰 때는 Counter 라이브러리를 잘 사용해야 한다!
• Counter.most_common() 을 사용하는 방법에 대해 알 수 있었다.

문제 링크

https://www.acmicpc.net/problem/1929

문제

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다.

출력

한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다.

예제 입력 1

3 16

예제 출력 1

3
5
7
11
13

틀린 풀이

n, m = map(int, input().split())

start_time = time.time()
# 2 ~ m의 리스트
array = list(range(2, m + 1))
array = [2] + [i for i in array if i % 2 == 1] # 2와 3 이상의 홀수만 남긴다

index = 0
while True:
		# 걸리지고 남은 맨 앞의 수부터 차례로 골라, 뒤에 있는 수를 나눠 소수를 판별한다 (에라토스테네스의 체)
    array = array[0:index + 1] + [i for i in array[index + 1:] if i % array[index] != 0]
    index += 1
		# 끝까지 다 진행한 경우 종료
    if index >= len(array):
        break
		# 사실 여기 올 일이 없음
    if array[index] >= m:
        break

# 위에서 2 ~ m 리스트로 시작했으니
# n 이상인지 판별하여 남긴다
result = [i for i in array if n <= i]
for number in result:
    print(number)

end_time = time.time()
print(end_time - start_time)

이유

• 시간초과
• 에라토스테네스의 체를 사용했으나, 시간복잡도가 너무 크다.

맞은 풀이1 (시간복잡도 상으로는 틀려야 한다..)

import time

start_time = time.time()
def check_prime(number):
    if number == 1:
        return False
    else:
        for i in range(2, int(number ** 0.5 + 1)):
            if number % i == 0:
                return False
        return True

n, m = map(int, input().split())

for i in range(n, m + 1):
    if check_prime(i) == True:
        print(i)
end_time = time.time()

print(end_time - start_time)

접근 방식

• n이 소수인지 판별하려면, 1 ~ root(n) + 1 까지의 수로 나누어보면 된다.
• → 약수를 대칭을 이루므로, root(n) + 1 까지 나누어떨어지지 않는다면, 그 이상의 수로 나누어떨어질 일이 없기 때문.
• 해당 방식이 작은 수에는 더 많은 시간이 소요되지만, 큰 수에 대해서는 훨씬 적은 시간이 소요된다.
• 시간 복잡도 : O(N*N^0.5) → 10억 번의 연산으로 시간초과가 맞아 보인다..

맞은 풀이2

n, m = map(int, input().split())

start_time = time.time()
array = list(range(2, m + 1))
array = [2] + [i for i in array if i % 2 == 1]

index = 0
while True:
    array = array[0:index + 1] + [i for i in array[index + 1:] if i % array[index] != 0]
    index += 1
    if index >= len(array):
        break
    if array[index] >= m ** 0.5 + 1:
        break

result = [i for i in array if n <= i]
for number in result:
    print(number)

end_time = time.time()
print(end_time - start_time)

접근 방식

• 에라토스테네스의 체를 이용한 풀이
• 에라토스테네스의 체를 사용할 때, 맞은 풀이1 처럼 m의 제곱근까지만 배수를 제거하였다. (그 이상의 배수는 존재하지 않는다! 이미 그 이하 수의 배수를 제거할 때 없어졌기 때문!)
• (연산이 간결해져서 훨씬 빠르다..)

맞은 풀이3

def prime_list(n):
    # 에라토스테네스의 체 초기화: n개 요소에 True 설정(소수로 간주)
    sieve = [True] * n

    # n의 최대 약수가 sqrt(n) 이하이므로 i=sqrt(n)까지 검사
    m = int(n ** 0.5)
    for i in range(2, m + 1):
        if sieve[i] == True:           # i가 소수인 경우
            for j in range(i+i, n, i): # i이후 i의 배수들을 False 판정
                sieve[j] = False

    # 소수 목록 산출
    return [i for i in range(2, n) if sieve[i] == True]

M, N = map(int, input().split())

N += 1
sieve = [True] * N
for i in range(2, int(N**0.5)+1):
    if sieve[i]:
        for j in range(2*i, N, i):
            sieve[j] = False
for i in range(M, N):
    if i > 1:
        if sieve[i]:
            print(i)

접근 방식

• 에라토스테네스의 체를 이용한 풀이
• 맞은 풀이2 를 보다 깔끔하게 정리한 풀이
• 실제 소수의 리스트를 남기는 것이 아니라, 1 ~ m(해당 코드에서는 n)까지의 True리스트를 만들고, 1 ~ squr(m) + 1의 배수에 해당하는 인덱스의 값을 False로 바꿨다.

정리

• 대량의 소수를 찾아야 한다!
  1. 에라토스테네스의 체 사용
  2. 1 ~ m 이 아닌, 1 ~ sqrt(m) + 1 까지만 배수를 제거하면 된다!

문제 링크

https://www.acmicpc.net/problem/1874

문제

스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다.

1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 작성하라.

입력

첫 줄에 n (1 ≤ n ≤ 100,000)이 주어진다. 둘째 줄부터 n개의 줄에는 수열을 이루는 1이상 n이하의 정수가 하나씩 순서대로 주어진다. 물론 같은 정수가 두 번 나오는 일은 없다.

출력

입력된 수열을 만들기 위해 필요한 연산을 한 줄에 한 개씩 출력한다. push연산은 +로, pop 연산은 -로 표현하도록 한다. 불가능한 경우 NO를 출력한다.

예제 입력 1

8
4
3
6
8
7
5
2
1

예제 출력 1

+
+
+
+
-
-
+
+
-
+
+
-
-
-
-
-

예제 입력 2

5
1
2
5
3
4

예제 출력 2

NO

틀린 풀이

import sys

n = int(input())
numbers = sorted(list(range(1, n + 1)), reverse=True)
example = []
for i in range(n):
    example.append(int(sys.stdin.readline().rstrip()))

stack = []
result = []
plus_minus = []

# example에 입력 배열을 저장한다
# numbers에 숫자를 차례로 저장해 pop하고 stack에 추가한다
# stack에서 pop하여 result에 저장한다.

# example을 차례로 순회하며, 해당 차례 값이 numbers에 있는 경우
# 그 값까지 pop하며 stack에 저장한다

# 해당 차례 값이 stack에 있는 경우 pop하여 result에 저장하고,
# pop한 값이 해당 차례 값과 다른 경우, "NO"를 출력하고 프로그램을 종료한다.

for a in example:
    if numbers.count(a) == 1:
        index_numbers = numbers.index(a)
        temp = numbers[index_numbers:]
        temp.reverse()
        stack += temp
        del numbers[index_numbers:]
        plus_minus += ['+'] * len(temp)
        result.append(stack.pop())
        plus_minus.append('-')
        
    elif stack.count(a) == 1:
        index_stack = stack.index(a)
        if index_stack != len(stack) - 1:
            print("NO")
            plus_minus = []
            break
        result.append(stack.pop())
        plus_minus.append('-')
 
if len(plus_minus) != 0:
    for a in plus_minus:
        print(a)

이유

• 시간 초과
  • stack, result를 직접 연산할 필요가 없었다.

맞은 풀이1

import sys

n = int(input())
num_list = [int(sys.stdin.readline()) for _ in range(n)]

stack = [] # 스택
result = [] # 결과값 저장
result_no = True # 불가능한 경우 False
cnt = 0

for num in num_list:
    
    while cnt < num:
        cnt += 1
        stack.append(cnt)
        result.append('+')
        
    # 스택의 가장 위의 수와 num과 같으면 pop하고 result에 '-' 저장
    if stack[-1] == num:
        stack.pop()
        result.append('-')
    # 스택의 가장 위의 수가 num과 다르다면 스택 불가능
    else:
        result_no = False
        break
    
if result_no == False:
    print('NO')
else:
    print('\\n'.join(result))

접근 방식

• numbers에서 pop하여 stack에 저장하는 대신, 그만큼 cnt를 증가시켜 저장했다.
• example(num_list)을 순회하는 방식은 동일했다.
• cnt가 해당 차례 num에 도달할 때까지 증가시키며
  • stack에 cnt를 append하고
  • result에 ‘+’를 append 했다.
• cnt ≥ num인 경우 즉, 해당 num이 이미 stack으로 옮겨진 경우,
  • stack.pop()한 값이 num과 같아야만 한다.
  • 그렇지 않으면 “NO”를 출력하고 프로그램을 종료한다.

종합하면,

위에서 numbers, stack, result, plus_minus로 연산하던 것을

cnt, stack, result(plus_minus와 동일)로 연산하여 reslut를 제외했고,

해당 차례의 수(num)가 stack에 있는지 찾는 연산 대신,

cnt 값을 활용하여 연산 없이 확인하여 시간을 줄였다.

정리

• 스택 자료구조를 활용한 문제이다.
• 불필요한 연산을 줄인다.
• 숫자가 stack에 순차적으로 쌓이고, 스택 최상단의 값만 pop할 수 있다는 사실을 활용한다.
  • 스택 최상단의 값과 원하는 값이 다른 경우, 프로그램을 종료한다.

문제 링크

https://www.acmicpc.net/problem/1654

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

예제 입력 1

4 11
802
743
457
539

예제 출력 1

200

틀린 풀이

import sys

k, n = map(int, input().split())
sticks = []
for i in range(k):
    sticks.append(int(sys.stdin.readline().rstrip()))

start = 0
end = sum(sticks) // n + 1  # 가장 이상적인 경우의 랜선 길이를 end로 정한다
mid = 0

# 길이에 따른 랜선 개수를 구하는 함수
def count_sticks(sticks, length):
    count = 0
    for stick in sticks:
        count += stick // length
    return count

while True:
    mid = (start + end) // 2
    count = count_sticks(sticks, mid)
    count2 = count_sticks(sticks, mid + 1)
		# 랜선 개수가 n이면서 길이가 1 늘어났을 때 랜선 개수가 n - 1이 되는,
		# 즉, 랜선 개수가 n일 때의 최대 길이를 mid에 저장한 채로 break 한다
    if count == n and count2 == n - 1:
        break
    if n > count:
        end =  mid - 1
    elif n < count or count2 == n:
        start = mid + 1

print(mid)

이유

• 시간초과
• 정확하게 왜 시간초과인지는 모르겠으나, 로직이 복잡함.

맞은 풀이1

import sys

k, n = map(int, input().split())
sticks = []
for i in range(k):
    sticks.append(int(sys.stdin.readline().rstrip()))

def count_sticks(sticks, length):
    count = 0
    for stick in sticks:
        count += stick // length
    return count

start = 0
end = sum(sticks) // n + 1

result = 0
while start <= end:
    mid = (start + end) // 2
    count = count_sticks(sticks, mid)
    if count < n:
        end = mid - 1
    else:
        result = mid
        start = mid + 1

print(result)

접근 방식

• 이분탐색
  • 입력의 범위가 매우 큼(K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수)
  • 최적의 해 하나를 찾아들어가는 형식
• 탐색 범위를 줄인다
  • 최대의 end는, 이상적인 경우에 위와 같이 나타남을 이용해 범위를 축소시킨다

정리

• 탐색 문제가 입력의 범위가 매우 크면 → 이분 탐색 떠올리기
• 위의 반복문 형식 기억하기

관련 학습 자료

https://www.youtube.com/watch?v=94RC-DsGMLo&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=5

12분 30초 - 떡볶이 떡 만들기 문제

난이도: 골드5

https://www.acmicpc.net/problem/2470

n = int(input())
array = sorted(list(map(int, input().split())))

# 포인터 두 개(left, right)와 최소일 때의 값, 위치를 기억하는 변수들(min, min_left, min_right)을 선언
left = 0
right = n - 1
min = abs(array[left] + array[right])
min_left = left
min_right = right


while left < right:
	# 용액의 합이 0이면 기록 후 즉시 종료
    if abs(array[left] + array[right]) == 0:
        min = abs(array[left] + array[right])
        min_left = left
        min_right = right
        break
	# left, right의 차이가 2 이상일 때(이동 시 겹치지 않을 때)
    # left 또는 right가 이동한 경우, 각각의 값을 비교하여 어느 포인터를 이동할지 결정
    if abs(array[left] + array[right - 1]) < abs(array[left + 1] + array[right]) and (right - left) >= 2:
		# 이동한 것이 최소라면, 해당 정보 기록
		if abs(array[left] + array[right - 1]) < min:
            min = abs(array[left] + array[right - 1])
            min_left = left
            min_right = right - 1
        right -= 1
    # 위와 로직 동일
    elif abs(array[left] + array[right - 1]) >= abs(array[left + 1] + array[right]) and (right - left) >= 2:
        if abs(array[left + 1] + array[right]) < min:
            min = abs(array[left + 1] + array[right])
            min_left = left + 1
            min_right = right
        left += 1
    # left, right 차이가 1이라면, 같게 만들어 다음 반복문이 실행되지 않게 함
    else:
        right -= 1
    

print(array[min_left], array[min_right])

# input 입력 받기
n = int(input())
solution = list(map(int, input().split(' ')))

# 정렬하기
solution.sort()

# 이중포인터 설정
left = 0
right = n-1

answer = 2e+9+1 # 기준값
final = [] # 정답

# 투포인터 진행
while left < right:
    s_left = solution[left]
    s_right = solution[right]

    tot = s_left + s_right
    # 두 용액의 합이 0과 가장 가까운 용액을 정답에 담아주기
    if abs(tot) < answer:
        answer = abs(tot)
        final = [s_left, s_right]
	
    # 두 용액의합이 0보다 작다면 왼쪽의 값을 늘려 조금 더 0에 가깝게 만들어준다
    if tot < 0:
        left += 1
    # 반대로, 두 용액의 합이 0보다 크다면 오른쪽의 값을 줄여서 조금 더 0에 가깝게 만들어준다
    else:
        right -= 1

print(final[0], final[1])

전체적인 논리는 비슷하지만,

이동 시 값을 비교한 것이 아니라, 논리를 통해 접근했다.

두 용액의 합이 0보다 작다면, left를 +=1 하고

0보다 크다면, right를 -=1 했다.

굳이 left +=1, right -=1 한 경우를 비교한 후 움직일 필요가 없었던 것이다.

남의 풀이2 (이분 탐색 사용)

출처 : https://latte-is-horse.tistory.com/316

n = int(input())
arr = sorted(map(int, input().split()))  # 정렬된 용액들


def binary_search(s, target):
    global arr
    res = n
    start, end = s, n - 1

    while start <= end:
        mid = (start + end) // 2
        if arr[mid] >= target:
            res = mid
            end = mid - 1
        else:
            start = mid + 1
    return res


def solution():
    global arr
    v1, v2 = 0, 0
    best_sum = 10 ** 10
    for i in range(n):
        # 이분 탐색 수행: 현재 위치(i) 이후의 용액에서 탐색, 찾는 값은 (현재 용액 * -1)
        res = binary_search(i + 1, -arr[i])
        
        # 찾은 용액의 왼쪽 용액 확인
        if i + 1 <= res - 1 < n and abs(arr[i] + arr[res - 1]) < best_sum:
            best_sum = abs(arr[i] + arr[res - 1])
            v1, v2 = arr[i], arr[res - 1]

        # 찾은 용액 확인
        if i + 1 <= res < n and abs(arr[i] + arr[res]) < best_sum:
            best_sum = abs(arr[i] + arr[res])
            v1, v2 = arr[i], arr[res]
    
    print(v1, v2) # i 번째 용액을 확인할 때 i + 1번 용액부터 확인하기 때문에 항상 v1 <= v2 이다.


solution()

이분 탐색으로 풀었다는 것이, 직관적인 논리로 다가오지는 않는다.

하지만, 아래와 같은 사고 흐름이라면 직관적이다.

1. 브루트포스(전체 경우의 수에 대해 탐색)를 생각

2. 시간 복잡도를 고려하면 시간 초과가 우려됨.

3. 모든 경우의 수를 탐색하되, 이분 탐색을 사용하여 시간 복잡도를 줄인다.

위와 같이 생각했다면,

이분 탐색 함수를 우선 구현하고,

전체 용액에 대해 이분 탐색을 실행하는 알고리즘을 생각할 수 있었을 것이다.

세상은 넓고 똑똑쓰들은 많다..

나도 한 자리 주쇼..

난이도: 실버3

https://www.acmicpc.net/problem/3273

import sys

n = int(input())
array = sorted(list(map(int, sys.stdin.readline().split())))	# 리스트 입력 시 정렬하여 저장
x = int(input())

count = 0

for i in range(len(array)):
    for j in range(i, len(array)):
        if array[i] >= (x//2 + 1):	# 앞의 수와 더했을 때 x보다 반드시 큰 경우 제외
            break
        if array[i] + array[j] == x:	# 이미 탐색한 경우(i와 i-1 등)를 제외하여 i, j 설정
            count += 1
	
print(count)

import sys

n = int(input())
array = sorted(list(map(int, sys.stdin.readline().split())))	# 리스트를 정렬하여 입력 받기
x = int(input())

count = 0
left, right = 0, n-1	# 두 포인터 설정

while left < right:	# 두 포인터가 교차되는 순간 반복문 종료
    sum = array[left] + array[right]
    if sum == x:	# left, right가 가리키는 값의 합이 x와 같은 경우
        count += 1
        left += 1	# left를 이동시켜 sum > x로 만든다
    elif sum > x:	# 값이 큰 경우 right를 이동시켜 값을 줄인다
        right -= 1
    elif sum < x:	# 값이 작은 경우 left를 이동시켜 값을 키운다
        left += 1
    
print(count)

시간 복잡도가 크게 줄어 시간 초과 없이 문제를 풀 수 있었다.

'나의 풀이' 에서 사용한 알고리즘은, 중첩 반복문이기에 O(N^2)의 시간 복잡도를 가진다.

'남의 풀이' 에서 사용한 알고리즘은, 좌우 포인터가 움직이면서 N번의 탐색을 하기에

O(N)의 시간 복잡도를 가진다.

두 포인터에 대해 알게 된 문제였다.