본문 바로가기

전체 글

 (351)
[BOJ] 1541. 잃어버린 괄호 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - input이 들어올 때, '-'를 기준으로 분리해서 배열에 저장한다. - '-' 뒤에 붙은 문자들은 다시 '-'가 올 때까지 빼주어야 한다. - 그러기 위해서는 '+'가 포함된 인덱스에서 다시 한번 분리해서 리스트화 한다. """ 2. 정답코드 import sys input = sys.stdin.readline arr = input().split('-'..
[BOJ] 2470. 두 용액 https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 투포인터를 이용 - start 는 맨 왼쪽, end는 맨 오른쪽 인덱스 위치로 설정 - 두 용액의 합(add_v)와 min_v의 값을 비교하고 더 작은 값을 min_v로 최신화 - add_v가 0보다 작으면 start + 1, 0보다 크면 end - 1 - 해당 인덱스의 값을 print """ 2. 정답코드 import sy..
[BOJ] 2805. 나무 자르기 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 이진 탐색을 활용 - 이분 탐색이 끝날 때까지 while문을 돌린다. - start는 1, end는 나무 길이가 가장 큰 숫자 - 자른 나무의 길이가 목표 길이보다 크면 mid -1, 작으면 +1 - 조건에 만족하면 print """ 2. 정답코드 # pypy3 import sys input = sys.stdin.rea..
[BOJ] 1654. 랜선 자르기 https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 이분 탐색을 이용한다. - 이분 탐색이 끝날 때까지 while문을 돌린다. - start는 1, end는 로프 길이가 가장 긴 숫자로 한다. - 랜선의 길이가 타겟 이상이면 mid + 1, 이하면 -1 """ 2. 정답코드 import sys input = sys.stdin.readline N, K = map(int, input(..
[BOJ] 10816. 숫자 카드2 https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - N 배열을 정렬 - 이진 탐색으로 검색 -> 시간 초과 - 파이썬의 Counter() 함수를 사용 """ 2. 정답 코드 # 시간 초과 import sys input = sys.stdin.readline N = int(input()) nums = sorted(list(map(int, input().split()))) M = ..
[BOJ] 1920. 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - M 배열을 for문 돌린다. - 시간복잡도를 고려해서 N개의 배열을 정렬해서 이진탐색을 활용한다. 2. 시간복잡도 - O(NlogN) """ 2. 정답코드 import sys input = sys.stdin.readline N = int(input()) nums = sorted(list(map(int, inpu..
[BOJ] 2467. 용액 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 입력받은 배열을 먼저 정렬한다. - 투포인터를 활용 (맨 왼쪽, 맨 오른쪽) - 두 개의 합을 구해서 abs(min_v)에 저장 - 합이 양수면 맨 오른쪽 인덱스 위치 -1, 음수면 맨 왼쪽 인덱스 위치 + 1 - 앞 서 저장한 min_v와 위치 이동한 인덱스 값의 합을 절댓값으로 비교 - 절댓값이 가장 작은 인덱스 값을 출력 2. 시간복잡도 - O(N..
[BOJ] 2003. 수들의 합2 https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 1. 해결방법 """ 1. 아이디어 - 투 포인터를 활용 - 왼쪽 첫 번째 두 번째를 target으로 잡고 합을 계산 - 합이 M보다 작다면 두 번째 타겟의 위치를 +1, 반대면 첫 번째 타겟의 위치를 -1, 합이 M 이라면 count + 1 - 첫 번째 타겟이 N보다 같거나 커지면 종료 2. 시간 복잡도 - O(N) """ 2. 정답코드 import sy..

티스토리툴바