Python/codingTest

Q. 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? A. 정답코드 def moving(l, start, end): visited = [[False] * l for _ in range(l)] moves = [(2, 1), (2, -1), (-2, 1), (-2, -1), (1, 2), (1, -2), (-1, 2), (-1, -2)] queue = [(start[0], start[1], 0)] visited[start[0]][start[1]] = True while queue: x, y, current_moves = queue.pop(0) if (x, y)..

Q. 정렬된 배열 num와 찾아야하는 target이 주어집니다. nums 배열에서 target을 찾을 수 있다면 nums의 어디에 있는지 index를 반환해주세요. 이 문제는 O(log n) 시간복잡도를 갖는 알고리즘을 사용하여 풀어야합니다. A. 이 문제는 시간복잡도가 O(log n)을 갖는 알고리즘으로 풀어야합니다. 일반적인 순차탐색은 O(n)이기에 다른 방법을 사용해야합니다. 필요한 알고리즘은 이진탐색입니다. 이진탐색을 정렬된 배열을 반으로 쪼개가며 target을 찾는 방식이여서 시간복잡도가 O(log n)입니다. class Solution: def search(self, nums: List[int], target: int) -> int: def bs(start,end): if start > end..

#5 최대 힙 Q. 최대 힙을 사용합니다. 표준입력값을 확인하여 알맞은 로직을 완성시켜주세요 정답 코드 import sys import heapq n = int(sys.stdin.readline()) heap = [] for i in range(n): x = int(sys.stdin.readline()) if x == 0: if heap: print(-heapq.heappop(heap)) else: print(0) else: heapq.heappush(heap, -x) 풀이 과정! 문제를 정리해보고 풀이 진행하겠습니다. 1. 표준입력값이 0이면 heap 배열에서 가장 큰 수를 출력하고 배열에서 제외시켜야합니다. 2. 만약 배열이 비어있는 상태에서 0이 표준입력값으로 들어오면 0을 출력하면 됩니다. 3. ..

#4 배열요소로 큰 수 만들기 Q. nums 배열에서 (nums[i]-1*nums[j]-1)식으로 만들 수 있는 가장 큰 수를 만들어주세요! 정답 코드 import heapq import sys class Solution: def maxProduct(self, nums): a,b = heapq.nlargest(2, nums)[0] -1 , heapq.nlargest(2, nums)[1] -1 return a*b nums = sys.input().readline sol = Solution() result = sol.maxProduct(nums) print(result) 풀이 과정! 이전 포스팅에서 배웠던 heapq.nlargest()함수를 통해 문제를 해결해봤습니다. 처음보시는 분이나, 다시 정보를 찾아..

#3 K번째 큰 요소 Q. 숫자로 구성된 배열 nums와 integer k가 주어집니다. nums 배열에서 k번째로 큰 요소를 찾아주세요 (sort을 사용하지 않고 구현해주세요) 정답 코드 import heapq class Solution: def findKthLargest(self, nums, k) : return heapq.nlargest(k, nums)[-1] nums = [1, 1, 1, 2, 2, 3] k = 2 sol = Solution() result = sol.findKthLargest(nums, k) print(result) # 2 nums배열에서 2번째(k)로 큰 요소 반환! import heapq 풀이 과정! 파이썬은 heapq 모듈을 통해서 힙구조의 데이터 편집에 용이합니다. 다양..

#1 그룹 애너그램 Q. 문자열로 구성된 배열인 str이 주어집니다. 이 배열에 있는 문자들 중에 같은 이니셜로 구성된 친구들끼리 묶어주세요! 정답 코드 class Solution(object): def groupAnagrams(self, strs): anagram = {} for word in strs: currentWord = "".join(sorted(word)) if currentWord in anagram: anagram[currentWord].append(word) else: anagram[currentWord] = [word] return list(anagram.values()) strs = ["eat","tea","tan","ate","nat","bat"] # 예시배열 sol = Solut..