great_park
great_park
great_park
전체 방문자
오늘
어제
08-10 17:55
  • 분류 전체보기 (124)
    • Computer Science (48)
      • Database (9)
      • Operating System (8)
      • Computer Network (0)
      • Computer Architecture (9)
      • Cloud computing (9)
      • Algorithm (13)
    • Algorithm PS (62)
      • DFS & BFS (21)
      • Floyd-Warshall (1)
      • Dijkstra (0)
      • Divide and Conquer (0)
      • Dynamic Programing (22)
      • Greedy (0)
      • BackTracking (11)
      • Binary Search (6)
      • Brute Force (0)
      • Sorting (0)
      • Stack & Queue (1)
      • Number Theory (0)
    • 기타 (12)
      • AWS (3)
      • Docker (1)
      • 기타 (8)
    • 2023 Google Solution Challenge (1)

최근 글

인기 글

블로그 메뉴

  • 홈
  • 태그
  • 방명록
반응형

태그

  • pub/sub
  • BOJ
  • LIS
  • Node.js
  • mysql
  • Docker
  • Binary Search
  • BFS
  • cloud computing
  • Computer Architecture
  • 알고리즘
  • Single-Cycle Datapath
  • Binarysearch
  • dfs
  • DeadLock
  • dp
  • Database
  • php
  • operating system
  • backtracking
hELLO · Designed By 정상우.
great_park
Algorithm PS/Binary Search

[BOJ/백준] 2470번 두 용액 (Python 파이썬) [Two pointer]

Algorithm PS/Binary Search

[BOJ/백준] 2470번 두 용액 (Python 파이썬) [Two pointer]

2022. 7. 27. 14:59
반응형

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

 

2470번: 두 용액

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00

www.acmicpc.net

시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
1 초 (추가 시간 없음) 128 MB 31031 9537 6907 30.512%

 

문제

KOI 부설 과학연구소에서는 많은 종류의 산성 용액과 알칼리성 용액을 보유하고 있다. 각 용액에는 그 용액의 특성을 나타내는 하나의 정수가 주어져있다.  산성 용액의 특성값은 1부터 1,000,000,000까지의 양의 정수로 나타내고, 알칼리성 용액의 특성값은 -1부터 -1,000,000,000까지의 음의 정수로 나타낸다.

같은 양의 두 용액을 혼합한 용액의 특성값은 혼합에 사용된 각 용액의 특성값의 합으로 정의한다. 이 연구소에서는 같은 양의 두 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들려고 한다. 

예를 들어, 주어진 용액들의 특성값이 [-2, 4, -99, -1, 98]인 경우에는 특성값이 -99인 용액과 특성값이 98인 용액을 혼합하면 특성값이 -1인 용액을 만들 수 있고, 이 용액이 특성값이 0에 가장 가까운 용액이다. 참고로, 두 종류의 알칼리성 용액만으로나 혹은 두 종류의 산성 용액만으로 특성값이 0에 가장 가까운 혼합 용액을 만드는 경우도 존재할 수 있다.

산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오.

입력

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,000,000 이하이다. N개의 용액들의 특성값은 모두 다르고, 산성 용액만으로나 알칼리성 용액만으로 입력이 주어지는 경우도 있을 수 있다.

출력

첫째 줄에 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액의 특성값을 출력한다. 출력해야 하는 두 용액은 특성값의 오름차순으로 출력한다. 특성값이 0에 가장 가까운 용액을 만들어내는 경우가 두 개 이상일 경우에는 그 중 아무것이나 하나를 출력한다.

예제 입력 1

5
-2 4 -99 -1 98

예제 출력 1 

-99 98

 


Two pointer 알고리즘을 이용하면 해결 가능한 문제입니다.  

https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Algorithm/%ED%88%AC%ED%8F%AC%EC%9D%B8%ED%84%B0%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.md

 

GitHub - WooVictory/Ready-For-Tech-Interview: 💻 신입 개발자로서 준비를 하기 위해 지식을 정리하는 공간

💻 신입 개발자로서 준비를 하기 위해 지식을 정리하는 공간 👨‍💻. Contribute to WooVictory/Ready-For-Tech-Interview development by creating an account on GitHub.

github.com

말 그대로 포인터 2개를 이용하여 원하는 값을 찾아가는 알고리즘입니다. 그렇다면 우리가 해야할 일은 어떤 조건에서 포인터를 어떻게 조작할 것인지를 결정하는 것입니다.

우선, 대략적인 전략은 다음과 같습니다.

  1. 용액의 특성값을 담은 리스트를 정렬시킨다.
  2. 우리의 목표는 '0'이므로 포인터는 리스트의 양 끝을 가리켜서 점차 0으로 접근하도록 한다.
  3. 두 개의 포인터가 가리키는 값을 더해서 'sum'을 구하고, sum의 절댓값과 ans 중 최솟값을 ans로 저장한다.
  4. sum이 만약 음수라면, 음수쪽 포인터의 크기를 줄여야 하므로 1 증가시킨다.
  5. sum이 만약 양수라면, 양수쪽 포인터의 크기를 줄여야 하므로 1 감소시킨다.
  6. 만약 이 과정에서 음수쪽 포인터가 양수쪽 포인터를 넘어간다면 탐색을 종료한다.
from sys import stdin
input = stdin.readline
N = int(input())
solution = sorted(list(map(int, input().split())))

start, end = 0, N-1
ans = abs(solution[start]+solution[end])
final = [solution[start], solution[end]]

while start < end:
    left = solution[start]
    right = solution[end]

    sum = left + right

    if abs(sum) < ans:
        ans = abs(sum)
        final = [left, right]
        if ans == 0:
            break

    if sum < 0:
        start += 1  # 합이 음수면 0에 가까워지기 위해 start + 1
    else:
        end -= 1  # 합이 양수면 end - 1
print(final[0], final[1])

 

유사 문제가 있어서 소개드리고 마치겠습니다 (2467번 용액, 2473번 세 용액)

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

 

2467번: 용액

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 -

www.acmicpc.net

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

 

2473번: 세 용액

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상

www.acmicpc.net

 

 

2473번: 세 용액

첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상

www.acmicpc.net

 

반응형
저작자표시 (새창열림)

'Algorithm PS > Binary Search' 카테고리의 다른 글

[BOJ/백준] 2110번 공유기 설치 (Python 파이썬)  (0) 2022.09.02
[BOJ/백준] 2512번 예산 (Python 파이썬)  (0) 2022.09.02
[BOJ/백준] 2805번 나무 자르기 (매개변수 탐색) (Python 파이썬)  (0) 2022.07.29
[BOJ/백준] 1654번 랜선 자르기 (매개변수 탐색) (Python 파이썬)  (0) 2022.07.29
[BOJ/백준] 12015번 가장 긴 증가하는 부분 수열 2 (LIS) (Python 파이썬)  (0) 2022.07.29
    'Algorithm PS/Binary Search' 카테고리의 다른 글
    • [BOJ/백준] 2512번 예산 (Python 파이썬)
    • [BOJ/백준] 2805번 나무 자르기 (매개변수 탐색) (Python 파이썬)
    • [BOJ/백준] 1654번 랜선 자르기 (매개변수 탐색) (Python 파이썬)
    • [BOJ/백준] 12015번 가장 긴 증가하는 부분 수열 2 (LIS) (Python 파이썬)
    great_park
    great_park
    GitHub : https://github.com/great-park

    티스토리툴바

    개인정보

    • 티스토리 홈
    • 포럼
    • 로그인

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.