본문 바로가기

Algorithm18

math.ceil 사용하지 않고 올림하기 알고리즘 문제를 풀다가, i와 j ( 0 math.ceil로도 올림할 수 있지만 math 라이브러리를 사용하기 싫어서 다음과 같이 코드를 적었다.(100-i) // j + (1 if (100 - i) % j != 0 else 0)이는 나누기를 하여 그 몫을 구하고나머지를 계산하여 0이면 잘 나눠떨어진 것이니 그대로 두고, 나머지가 0이 아니면 소숫점 아랫수가 있는 것이므로 올림하여 1을 더해준 것이다. 괜히 복잡하고 보기 싫어서 찾아보다가 다음과 같이 적을 수 있었다!-((i-100) // j)이는 위 식이랑 완전히 같은 결과를 내놓는다.왜냐면 음수(i-100)에 대한 나눗셈을 하여서 그 몫(//)을 구하면 내림 방향으로 작동하고,그 결과에 -1을 곱하면 이는 올림한 결과가 나기 때문이다. 이를 정리.. 2025. 5. 14.
[python/leetcode 42] Trapping Rain Water 문제높이를 입력받아 비 온 후 얼마나 많은 물이 쌓일 수 있는지 계산  접근높이를 막대라고 봤을 때, 한 막대에서 다음 막대를 살펴볼 때, 더 높거나 같은 막대가 있을 때까지 물이 고일 수 있고, 그 둘 사이에 막대가 존재한다면 그 사이 막대의 높이만큼 물이 덜 고인다.다음 막대들 중 기준 막대보다 높거나 같은 막대가 있는게 계산하기 좋으니까, 최고 점을 향해 양쪽에서 접근하며 계산한다.  코드def trap(self, height: List[int]) -> int: volume = 0 left, right = 0, len(height)-1 left_max, right_max = height[left], height[right] while left  풀이.. 2024. 8. 8.
[python/leetcode 49] Group Anagrams 문제문자열 배열이 주어졌을 때, 애너그램끼리 그룹지어 출력 Anagram: 문자를 재배열하여 다른 뜻을 가진 단어로 바꾸는 것ex. ate, eat, tea  접근애너그램이면 문자열을 정렬하면 같은 문자열이 된다.따라서 주어진 배열 내 문자열들을 정렬하여 애너그램끼리 묶을 수 있다.(정렬한 문자열이 같은 것들이 애너그램)  코드def groupAnagrams(self, strs: List[str]) -> List[List[str]]: anagrams = collections.defaultdict(list) for word in strs: anagrams[''.join(sorted(word))].append(word) return anagrams.v.. 2024. 8. 7.
[python/ 백준 1620] 나는야 포켓몬 마스터 이다솜 문제 첫째 줄에는 도감에 수록되어 있는 포켓몬의 개수 N이랑 내가 맞춰야 하는 문제의 개수 M이 주어져. N과 M은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수인데, 자연수가 뭔지는 알지? 모르면 물어봐도 괜찮아. 나는 언제든지 질문에 답해줄 준비가 되어있어. 둘째 줄부터 N개의 줄에 포켓몬의 번호가 1번인 포켓몬부터 N번에 해당하는 포켓몬까지 한 줄에 하나씩 입력으로 들어와. 포켓몬의 이름은 모두 영어로만 이루어져있고, 또, 음... 첫 글자만 대문자이고, 나머지 문자는 소문자로만 이루어져 있어. 아참! 일부 포켓몬은 마지막 문자만 대문자일 수도 있어. 포켓몬 이름의 최대 길이는 20, 최소 길이는 2야. 그 다음 줄부터 총 M개의 줄에 내가 맞춰야하는 문제가 입력으로 들어와. 문제가 알.. 2024. 1. 21.
[python/ 백준 1302] 베스트셀러 문제 김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다. 오늘 하루 동안 팔린 책의 제목이 입력으로 들어왔을 때, 가장 많이 팔린 책의 제목을 출력하는 프로그램을 작성하시오. 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고, 알파벳 소문자로만 이루어져 있다. 첫째 줄에 가장 많이 팔린 책의 제목을 출력한다. 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력한다. 접근 책.. 2024. 1. 20.
[python/ 백준 1193] 분수찾기 문제 무한히 큰 배열에 다음과 같이 분수들이 적혀있다. 1/1 1/2 1/3 1/4 1/5 … 2/1 2/2 2/3 2/4 … … 3/1 3/2 3/3 … … … 4/1 4/2 … … … … 5/1 … … … … … … … … … … … 이와 같이 나열된 분수들을 1/1 → 1/2 → 2/1 → 3/1 → 2/2 → … 과 같은 지그재그 순서로 차례대로 1번, 2번, 3번, 4번, 5번, … 분수라고 하자. X가 주어졌을 때, X번째 분수를 구하는 프로그램을 작성하시오. 접근 (분자) 1 12 321 1234 54321 … (분모) 1 21 123 4321 12345 ... 위와 같은 규칙이 보인다. 개수는 1, 2, 3,,, 이니까 n이 몇 번째 시그마에 속하는지를 구하면 될 것 같다. 그리고 n이 속.. 2024. 1. 16.

티스토리툴바