BOJ

[문제] https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net [풀이] 이 문제의 핵심은 아래 두 가지로 요약할 수 있다. 1. 선을 좌표 기준으로 정렬해야된다. (우선순위 큐 혹은 배열 정렬) 2. 선이 포함되는 경우 조건문으로 처리 👎 배열에 선을 그은 곳은 1로 채워 총 1의 수를 구할 경우, 배열 크기를 2조로 지정해야되기 때문에 다른 방법을 생각해야한다. 문제에서 주어진 입력된 선을 형광펜으로 표시하면 이렇다..

[문제] https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net [풀이] "아홉 난쟁이의 키는 모두 다르지만 그중 일곱 난쟁이의 크기의 합은 100이 된다" 는 것은 sum(난쟁이 리스트) - (난쟁이1 + 난쟁이2) == 100과 같다. 두 난쟁이를 구하기 위해 전체 탐색을 해야 한다. [코드] import sys men = [int(sys.stdin.readline()) for _ in range(9)] flag = False for i in range(9..

[문제] https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net [풀이] 문제의 핵심은 현재 수업의 종료 시간이 다음 수업의 종료 시간보다 늦을 경우 회의실 하나를 더 배정해야 한다. 먼저 수업의 시작과 끝 시간을 queue에 넣고 이를 정렬하면 시작 시간이 가장 빠른 수업이 가장 앞에 오게 되기 때문에 첫 수업의 종료시간을 새로운 큐인 room에 넣는다. 두 번째 수업부터 첫 번째 회의와 비교를 하는데 두 번째 수업의 시작시간 < 첫 수업의 종료시간 일 경우 강의실을 새로 배정해야 하고 그렇지 않..

[문제] https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net [풀이] 처음에는 간단하게 sort 함수를 이용해 풀었는데 이는 O(nlogn)으로 우선순위 큐를 이용하면 O(logn)으로 시간복잡도를 줄일 수 있다. 우선순위 큐 사용시, 값을 바꿀 카드 2개를 우선순위 큐에 삽입만 하면 되기 때문에 매번 정렬해야하는 sort 보다 훨씬 효율적인 것이다. 따라서 cards 리스트를 만든 후 heapq 내장 모듈 사..

[문제] https://www.acmicpc.net/problem/9009 9009번: 피보나치 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n www.acmicpc.net [풀이] 우선 피보나치 리스트를 만들어 올바른 값을 미리 넣어준다. 문제에 n의 최댓값이 1,000,000,000이라고 했기 때문에 44번 째 피보나치 수열까지만 구하면 된다. 만들 수 있는 숫자 중 최소 개수로 n을 만들기 위해서는 n 이하의 수 중 가장 n과 가까운 수를 써야 한다. 문제에 나온 예시처럼 100을 만들기 위해서는 (3 + 8 + 89) 도 가능하지만 (3 + 8 + 34 ..

[문제] https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net [풀이] 우선.. for문을 두 번 쓰면 런타임 에러가 난다. 당연함. 100,000명을 2차 반복문으로 돌리면.. 따라서 반복문 한번에 비교를 끝내야한다. 그러기 위해 우선 첫 번째 점수를 기준으로 정렬을 한 후에 rank_asc 변수에 담는다. rank_asc 변수의 첫 번째 원소는 서류 심사가 가장 높은 사람이 오기 때문에 이 사람의 면접 결과가 몇 점이든 무조..

[문제] https://www.acmicpc.net/problem/1817 1817번: 짐 챙기는 숌 첫째 줄에 책의 개수 N과 박스에 넣을 수 있는 최대 무게 M이 주어진다. N은 0보다 크거나 같고 50보다 작거나 같은 정수이고, M은 1,000보다 작거나 같은 자연수이다. N이 0보다 큰 경우 둘째 줄에 책 www.acmicpc.net [풀이] 이 문제의 핵심은 책을 차례대로 박스에 넣을 수 있다는 것이다. 때문에 차례대로 반복문을 돌며 박스에 책을 넣었을 때 박스에 들어간 무게가 M을 넘는다면 박스 무게를 초기화 하여 현재 책의 무게를 담고 cnt를 1 증가시킨다. [코드] import sys N, M = map(int, sys.stdin.readline().split()) if N > 0: bo..

[문제] https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net [풀이] 입력받은 문자열을 한 글자씩 리스트에 넣는다. 첫 번째 문자가 0이면 zero_count를 1 더해주고, 1이면 one_count를 1 더해준다. zero_count: 0을 1로 바꿔야 하는 횟수 one_count: 1을 0으로 바꿔야 하는 횟수 반복문으로 문자열의 (i - 1) 인덱스와 (i) 인덱스의 값이 일치하는지 확인한다. 일치하지 않을 경우 (i) 인덱스의 값이 0이면 ..

[문제] https://www.acmicpc.net/problem/3578 3578번: Holes You may have seen a mechanic typewriter — such devices were widespread just 15 years ago, before computers replaced them. It is a very simple thing. You strike a key on the typewriter keyboard, the corresponding type bar rises, and the metallic letter mo www.acmicpc.net [풀이] 문제에 쓸데없는 설명들이 많은데 요약하자면 0, 4, 6, 9 를 타이핑 할 경우 종이에 구멍이 1개 생기고 8 을 타이..