공순이의 블로그

문제 출처 [문제 요약] solved.ac의 난이도 점수의 절사평균을 구하는 문제이다. 처음에 총 입력 개수 N이 주어진다. 이후 점수들이 들어오는데, 30%의 절사평균을 구하면 된다. 절사평균은 극단적인 값을이 평균을 왜곡하는 것을 막기 위해 가장 작은 값들과 큰 값들을 제외하고 평균을 내는 것을 말한다. 좀 쉽게 풀어쓰면 절사평균 30%를 구하라는 말은 점수중 낮은 0.15%와 높은 0.15%를 제외하고 평균을 내어야 한다. 단 0.15*n이 소수점도 있으므로 반올림 하여 그 인원만큼 낮은 점수와 높은 점수를 제외해야 한다. 평균도 round해서 정수로 난이도를 결정한다. 점수 범위는 1부터 30이하이다. [풀이] 점수 범위가 주어졌으므로 defaultdict를 사용하였다. d = defaultdic..

파이썬 2023. 8. 18. 05:51

문제 출처 [문제 요약] 첫 줄에 입력의 개수 N이 입력으로 들어온다. 이후에 N개의 x, y좌표가 스페이스로 나누어진채 주어진다. 좌표를 y좌표가 증가하는 순으로, y좌표가 같으면 x좌표가 증가하는 순으로 출력해라. [풀이] 우선 x에 대하여 정렬한 후 y에 대하여 정렬하면 된다. lst에 좌표가 (x, y)의 tuple형태로 주어진다고 하면 lst.sort() lst.sort(key=lambda x: x[1]) [유의할 점] sort의 key가 어떤걸 기준으로 sort할지 주는거고 lambda x: x[1] 이 튜플에서 두번째(y)를 기준으로 정렬하라는 뜻이다. [파이썬 3 코드] # -*- coding: utf-8 -*- from sys import stdin if __name__ == "__mai..

파이썬 2023. 8. 18. 04:55

문제 출처 [문제 요약] 처음에 주어질 수의 개수 N이 주어진다. 그 다음부터는 N의 개수만큼 숫자가 주어진다. 주어지는 숫자는 10000이하의 자연수이며 중복이 있다. 이를 정렬해서 한 줄에 하나의 수를 프린트하는 코드를 짜면 된다. [풀이] 시간 제한이 있기에 최대한 빠른 알고리즘을 만들자. input()대신 stdin.readline()으로 입력을 받자 그리고 defaultdict()를 사용하자 (hashing이라서 넣는데 O(n)이다). 우선 dictionary = defaultdict(int)로 하면 키가 없는 경우 그 값은 0으로 설정이 된다. 이후 N만큼 룹을 돌면서 입력을 key로, value는 1씩 더해주면 된다. 그러면 dictionary에는 10000까지 수중에 존재하는 수에는 해당 ..

파이썬 2023. 8. 17. 17:52

문제 출처 [문제 요약] 입력으로 부르는 돈의 횟수 그 이후에 돈이 얼마인지 주어진다. 다만 실수로 돈을 부르는 경우가 있는데 그 때는 0을 말하면 지울 수 있다. 잘못 부른 돈을 제외한 돈들의 합을 출력으로 프린트 해야한다. [풀이] 룹(loop)을 하나만 쓰고 풀수 있는 방법을 고안해낸 결과 sum이라는 변수, 그리고 유효한 돈을 관리하는 리스트(list)인 lst를 만들었다. 여기에 지워야할 인덱스(index)를 나타내는 previdx(이전인덱스)라는 변수를 만들었다. n만큼 룹을 돌면서 숫자가 들어오는 경우: sum에 input더해줌 lst에도 input더해줌 previdx는 더해진 수를 가리키게 함 0이 들어오는 경우: sum에 previdx만큼 빼줌 lst에서도 previdx위치에 있는 inp..

파이썬 2023. 8. 17. 16:45

문제 출처 [문제 요약] 다음과 같은 벌집 모양의 방들이 있다. 각 방의 번호들은 중앙의 1부터 시작해 1씩 늘어난다. 숫자 n이 입력으로 주어졌을때 최소로 지나가는 방의 개수를 출력해야한다. [풀이] 원소의 보어 모형과 비슷하게 생각하고 풀었다. 벌집의 한 가운데를 level1, 그 주변에 맞닿아있는 방들을 level2라고 하면 방이 늘어나는 개수는 아래 그림과 같이 6의 배수로 늘어난다. level2 모서리 = 6 * 1(level1) level3 모서리 = 6 * 2(level2) 현재 레벨까지 포함되는 방의 최대 번호를 nums라는 변수로 두자. 그러면 입력으로 주어진 n보다 nums가 같거나 클 때까지 룹(loop)을 돌림으로써 n이 방을 몇 번 거쳐야하는지 계산 할 수 있다. 룹 안에서는 nu..

파이썬 2023. 8. 16. 17:33

문제 출처 [문제 요약] 분해합이란 어떤 자연수 N이 있으면 N의 각 자릿수와 N을 더한 값이다. ex) 어떤 자연수 N이 245라고 하면, N의 분해합은 2+4+5+245 = 256 수식으로 나타내면 N(분해합) = M(생성자) + int(str(M)[0]) + … + int(str(M)[len(M-1)]), 간단하게 아래처럼 된다. 생성자란 분해합을 만드는 수이다. 위에서 말하던 어떤 자연수 N이 생성자다. 생성자는 여러개가 있기도, 없기도 한데 분해합이 입력으로 들어오면 가장 작은 생성자를 출력하는게 목표이다. 생성자가 없으면 0을 출력한다. [풀이] 분해합은 생성자의 각 자릿수와 생성자를 더하기 때문에 생성자보다 크다. 이 점을 이용해 분해합을 구하는 함수를 간단히 만든다음 룹을 생성자 - 1 만..

파이썬 2023. 8. 16. 16:10

문제 출처 [문제 요약] 원형 테이블에 n명의 사람들이 순서대로 앉아있다. 양의 정수 k가 주어지면 k번째에 앉은 사람을 제거하고, 재거한 사람 이후부터 다시 k번째에 앉아있는 사람을 제거한다. 이와 같은 방식으로 모두를 제거할때 제거하는 순서를 적으면 된다. 입력은 n k로 주어진다. 예를들어 입력이 7 3이라고 하자. 그리고 어떤 사람을 지울지 가리키는 변수를 편의상 idx(index 인덱스)라고 정의했다. 총 7명의 사람들이 원형으로 앉아있고, 스탭(step)은 3이어서 idx는 3씩 더해진다. 움직이는 칸을 편의상 스탭이라고 불렀다. 위 그림과 같은 상황에서 1부터 3칸을 세어보자. 그러면 처음으로 제거되는 숫자는 3이다. 제거된 수 이후부터 3칸을 더 가면 6, 또 3칸을 세어 원형 테이블의 마..

파이썬 2023. 8. 14. 20:11

문제 출처 [문제 요약] 길이가 제각각인 랜선 k개가 주어진다. 이를 길이가 동일한 n개의 랜선으로 잘라야 할때 가장 크게 자를 수 있는 길이를 출력하면 된다. * 자를때 손실되는 길이 없음 ** 기존 주어진 k개의 랜선으로 n개의 랜선을 만들 수 없는 경우는 없다고 가정 (답이 항상 있다) *** 단위는 정수 [풀이] 이분 탐색 문제이다. 간단하게 1부터 아직 어딘지 모를 최대 길이 limit가 있다고 가정을 하자. 보통 수열에서의 이분탐색은 범위를 가리키는 시작점(start)과 끝점(end)가 있고 찾아야 하는 수 정답(ans)이 있다면 start와 end의 딱 절반 지점인(이 문제에서는 중앙값인) half가 ans보다 큰지 작은지를 비교하면서 점점 그 범위를 좁혀 나가는 방식이다. half가 ans..

파이썬 2023. 7. 21. 15:35