공순이의 블로그

문제 출처 [문제 요약] 처음에 주어질 수의 개수 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

문제 출처 [문제 요약] 입력을 n을 받는다. 그러면 n!에서 0 이외의 다른 수가 나오기 전까지의 0의 개수 (오른쪽 끝에 있는 0의 개수) 를 출력으로 내보내면 된다. [풀이] 1부터 n까지 곱할때 나오는 2와 5의 개수를 세서 10이 몇개인지 알아내면 된다. 2*5가 10이니 2가 나온 갯수, 5가 나온 갯수중 작은 수를 돌려주면 된다. [유의할점] 100같은 수는 10이 두번 곱해진 형태이다. 이처럼 어떤수의 최대공약수가 2^x * 5^y인 경우 (2 혹은 5의 몇승인 경우) 1번만 세는게 아니라 x와 y개만큼 전부 세어주어야한다. [파이썬 3 코드] def mul5(n): num5 = 0 while n % 5 == 0: n = n // 5 num5 += 1 return num5 def mul2(..

파이썬 2023. 6. 12. 14:57

문제 출처 [문제 요약] A가 펜케익을 T번 먹을때 남는 펜케익의 부피를 가장 크게 남길때의 부피를 구하는 것이다. 한번 먹을때 1cm 만큼 팬케이크의 한 변이 줄어든다. [풀이] 우선 test case의 개수를 input으로 받는다. 각 test case는 W(width), D(depth), H(height)와 t(먹는 횟수)를 input으로 주는데 가장 남는 부피를 크게 남기려면 W, D, H의 크기를 비슷하게 맞춰주어야한다. 그래서 셋 중 가장 큰 변의 크기를 1cm 씩 iterative 하게 줄이는 풀이가 easy 한 난이도를 통과하기 무난하다. [유의할 점] test case의 개수와 input이 1칸씩 더 띄워져있기 때문에 input을 받을떼 유의할것. [파이썬 3 코드] def max_min..

파이썬 2023. 6. 12. 09:43