본문 바로가기
728x90

정렬34

[python] 백준 1727 커플 만들기 https://www.acmicpc.net/problem/1727 1727번: 커플 만들기 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 줄에는 n명의 남자들의 성격이 주어진다. 그 다음 줄에는 m명의 여자들의 성격이 주어진다. 성격은 1,000,000이하의 자연수이다. www.acmicpc.net 문제 해결 커플 만드는 문제 최근 코딩테스트에서 나오는 문제 유형이다.(사실 이것보다 더 어렵다.ㅠㅠ) 시간복잡도 신경쓰면서 커플을 연결하는 것이 쉽지 않다. 구하고자 하는 것은 성격의 차이의 합이 최소가 되는 것이다. 따라서 누적합을 통해 답을 도출하도록 한다. sort를 통해 성격을 수치화한 것을 오름차순으로 만든 다음 남자 0번과 가장 맞는 여자 j(0 2023. 4. 24.
[python] 백준 3151 합이 0 https://www.acmicpc.net/problem/3151 3151번: 합이 0 Elly는 예상치 못하게 프로그래밍 대회를 준비하는 학생들을 가르칠 위기에 처했다. 대회는 정확히 3명으로 구성된 팀만 참가가 가능하다. 그러나 그녀가 가르칠 학생들에게는 큰 문제가 있었다. www.acmicpc.net 문제 해결 3개의 수를 고르는 문제는 전형적으로 A[i] + A[j] + A[k] = c 에서 A[j] + A[k] = c - A[i]로 바꾼다. c= 0이므로 A[j]+A[k] = -A[i]를 찾는 문제 그러면 A[i]를 고정시키고 j와 k를 찾는 것이 편하다. 처음에 j= i+1 k=n-1으로 정하고 A[j]+A[k] >A[i]면 k를 내리고 A[j] + A[k] < A[i]이면 j를 올리는 식으로.. 2023. 4. 24.
[python] 백준 18869 멀티버스 Ⅱ https://www.acmicpc.net/problem/18869 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net 문제 해결 각 우주안에서 몇 번째로 큰 수인지를 알 수 있다면 비교하기 쉬울 것이다. 각 우주의 행성을 리스트안에 넣은 것을 A라하고 각 행성의 크기 등수를 적은 리스트를 B라 하면 f:A→B 는 일대일 대응이므로 바꿔서 계산해도 문제 없다. defaultdict 딕셔너리를 이용해 B가 같은 것들의 우주의 개수를 value로 하여 균등한 우주의 쌍을 계산할 수 있다. ( S[B] = n이라.. 2023. 4. 24.
[python] 백준 3649 로봇 프로젝트 https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 문제 해결 전형적인 투포인터 문제 n==0일 때와 n==1일 때 불가능하므로 danger 출력하고 다음 테스트케이스 출력 n>=2일 때부터 올림차순으로 정렬된 리스트에서 start =0 end = n-1을 잡고 두 원소의 합이 x가 될 때까지 숫자를 조절하여 찾는다. start>=end가 되면 찾을 수 없는 것이므로 danger 출력하고 다음 테스트 케이스 출력 CODE .. 2023. 4. 22.
728x90