BOJ

[문제] https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net [풀이] 같은 코드여도 pypy3로 하면 맞는데 python3로 하면 다 시간 초과 오류 떴다.. 처음에는 brute force로 푸는 줄 알고 우왕 쉽다 하면서 풀었는데 시간 초과가 떠서 이건 이렇게 간단하게 풀 문제가 아니라는 걸 직감했다. -> 이분 탐색으로 풀어야 한다 가장 짧은 나무의 길이를 1을 start로, trees 중 가장 큰 값을 ..

[문제] https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net [풀이] 산술평균, 중앙값, 범위 구하는 법은 쉬워서 패스.. 최빈값 구하는 게 아주 조금 까다로웠다. 처음에 입력 받을 때 sorted함수를 통해 차례대로 정렬한 상태로 리스트에 저장한다. num_cnt 딕셔너리를 생성한 후 try-except문을 활용해 num_cnt에 숫자 당 빈도수를 저장했다. for문으로 num에 있는 숫자를 차례대로 꺼내 num_cnt[i] += 1을 하게 되면 num_cnt..

[문제] https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net [풀이] 문자열을 sentence 변수에 저장한다. sentence에 있는 문자 하나씩 검사한다 문자가 '(' 이거나 '[' 인 경우 (열린 문자일 경우) stack 리스트에 문자를 추가한다. 문자가 ')' 인 경우 stack 리스트가 empty이거나 stack의 마지막 원소를 꺼냈을 때 '['인 경우 flag를 False로 변환 break로 반복문 나옴 stack의 마지막..

[문제] https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net [풀이] 원하는 문서가 몇 번째로 인쇄되는지를 출력해야 하기 때문에 인쇄 큐 순서가 바뀔 때마다 인덱스 순서도 같이 바꿔줘야 한다. 그래야만 원래 m번째 문서가 언제 출력되는지 구할 수 있다. 입력값을 알맞게 변수에 넣은 후 idx 리스트를 선언한 후 원하는 문서 인덱스 값은 'target'으로 바꾼다. 예를 들어 예제 입력의 두 번째 테스트 케이스에서 idx[m] = 'target'을 하면..

[문제] https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net [풀이] 2021.07.28 - [BOJ] - [Python] BOJ/백준 11650번 좌표 정렬하기 [Python] BOJ/백준 11650번 좌표 정렬하기 [문제] https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. ..

[문제] https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net [풀이] 처음에는 슬라이싱을 이용해 str(i)[-3:] == '666' 이런 식으로 끝에서부터 세 자리씩 '666'과 같은지 비교해야 되나 했다. 생각해보니 문자열은 in을 이용해 간단하게 풀 수 있는 방법이 있었다. i가 666부터 1씩 증가하는 while문이 있다. 만약 i를 str로 바꾼 문자열 내부에 '666'이 있다면 cnt를 1 증가시켜준다. cnt가 입력값인 n과 일치한다..

[문제] https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net [풀이] 분해합은 n과 n을 이루는 각 자릿수의 합을 구해야 하는데 N을 이루는 각 자릿수의 합을 구하는 부분을 브루스 포스 알고리즘으로 풀어야겠다고 생각했다. 1부터 n+1까지 반복문을 돈다. str함수를 통해 i를 자리수마다 쪼개 리스트 A에 넣는다. 숫자 전체인 i와 자리수의 합인 sum(A)를 더해 res 변수에 넣는다. 만약 res가 n과 같다면 i값..

[문제] https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net [풀이] 재밌는 문제였다. (내가 한 번에 풀면 재밌는 문제 아니면 재미없는 문제 ^^~) stack은 숫자 값을, result는 '+' 혹은 '-' 값을 담을 리스트이다. next_turn은 pop한 뒤 다시 숫자를 쌓기 시작할 때 어느 수부터 쌓는지 기억하는 변수이다. 예를 들어 1, 2, 3, 4를 a..

[문제] https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net [풀이] 이분 탐색으로 푸는 방법도 있지만 해쉬 자료구조를 이용해 풀었다. 상근이가 갖고 있는 숫자 카드를 차례대로 한 개씩 뽑아 그 숫자가 hashmap 딕셔너리의 key에 있다면 value값을 1 증가시켜주고 숫자가 딕셔너리에 없다면 해당 key값을 추가시킨다. [코드] import sys if __name__ == '__main__': n = int..