Algorithm/BOJ

백준#1417 국회의원 선거 in Python

1417번: 국회의원 선거 첫째 줄에 후보의 수 N이 주어진다. 둘째 줄부터 차례대로 기호 1번을 찍으려고 하는 사람의 수, 기호 2번을 찍으려고 하는 수, 이렇게 총 N개의 줄에 걸쳐 입력이 들어온다. N은 50보다 작거나 같 www.acmicpc.net 이 문제를 풀기 위한 자료구조로 우선순위 큐가 적합하다는 것을 깨닫는 순간 빠르게 풀리는 문제다. 필자는 그걸 깨닫지 못해 여러 시행착오와 반례 선정을 거쳐 꽤 오랜 시간이 걸렸다... 후보가 1명일 경우, 바로 0을 프린트하고 종료한다. 후보가 2명 이상일 경우, 0번 인덱스(1번 후보)의 값을 target 변수에 저장해 따로 떼어두었다. └ 이 자체가 필수적인 의미를 갖지는 않지만, 메모리를 고려하지 않는 내 작은 코드에서는 이 라인을 없애는 순간..

백준#2075 N번째 큰 수 in Python

2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 이 문제의 핵심은 입력으로 주어지는 수를 모두 배열에 때려 박아서 정렬하는 것보다 더 효율적인 방법이 무엇인지 고민하는 것이다. 여기서, 'N번째 큰 수'란, 'N개의 수들 중 가장 작은 수'라는 것을 깨닫고 나면 문제가 쉽게 풀린다. 문제 예시처럼 N=5라고 가정할 때, 최대 크기가 5인 리스트를 만들었다. └ 크기가 5보다 작으면 일단 숫자를 넣고, 그 외의 경우에는 (크기가 5인 경우) 다음 행위를 실행한다. 리스트의 크기가 5일 때 새로운 숫자를 만나면 최소값과..