junhwa100 님의 블로그

1. 문제 이해Dota2의 세계에는 Radiant와 Dire라는 두 진영이 존재한다. Dota2 상원은 이 두 진영에서 온 상원 의원들로 구성되어 있다. 이제 상원은 Dota2 게임의 변경 사항에 대해 결정하려고 한다.  이 변경 사항에 대한 투표는 라운드 기반 절차로 진행된다. 각 라운드에서, 각 상원 의원은 다음 두 가지 권한 중 하나를 행사할 수 있다. 1. 상대방 의원의 권한 박탈: 한 상원 의원은 다른 상원 의원이 이 라운드와 모든 이후 라운드에서 모든 권한을 잃도록 만들 수 있다. 2. 승리 선언: 만약 이 상원 의원이 권리를 가진 모든 상원 의원이 같은 진영에 속해 있음을 발견하면, 그는 승리를 선언하고 게임 변경 사항을 결정할 수 있다. 문자열 senate가 주어진다. 이 문자열은 각 상원..

1. 문제 이해RecentCounter 클래스를 구현한다.RecentCounter 클래스는 특정 시간 범위 내에서 최근 요청의 수를 계산한다.최근 요청이 0개인 상태로 카운터를 초기화한다.int ping(int t) 함수는 시간 t에 새로운 요청을 추가하고, 지난 3000밀리초 동안 발생한 요청 수를 리턴한다.구체적으로는 [t - 3000, t] 범위 내에서 발생한 요청의 수를 리턴한다.(ping 함수의 각 호출은 이전 호출보다 항상 더 큰 값을 갖는 t를 사용한다.)이해하기 어렵다..  2. 풀이 과정범위 밖에 있는 오래된 요청들은 제외한다. 큐를 사용한다. 클래스가 호출될 때, 큐를 초기화한다.def __init__(self): self.requests = deque() 새로운 요청을 큐에 추가..

1. 문제 이해주어진 인코딩된 문자열을 디코딩하여 리턴한다.인코딩된 문자열은 k[encoded_string] 형태로, 대괄호 안의 encoded_string을 정확히 k번 반복하여 디코딩한다.  2. 풀이 과정스택을 사용한다.for문을 통해 문자열을 조회한다.만약 해당 문자가 ']'가 아니라면 스택에 문자를 추가한다.만약 해당 문자가 ']'라면 '['를 찾을 때까지 스택에서 문자를 꺼낸다.이때 임시 리스트를 만들어 꺼낸 문자들을 저장한다.저장한 문자를 스택 최상단에 있는 숫자만큼 반복해서 다시 스택에 저장한다.class Solution: def decodeString(self, s: str) -> str: stack = [] for i in range(len(s)): ..

1. 문제 이해정수 리스트 asteroids가 주어진다. 이는 행에 있는 소행성들을 나타낸다.각 소행성은 절댓값이 크기를 나타내고, 부호는 방향을 나타낸다.(양수는 오른쪽, 음수는 왼쪽 방향)모든 소행성은 동일한 속도로 움직인다. 모든 충돌이 발생한 후 소행성들의 상태를 리턴한다.두 소행성이 만나면 더 작은 소행성이 폭발한다. 두 소행성의 크기가 같다면 둘 다 폭발한다.같은 방향으로 움직이는 두 소행성은 절대 만나지 않는다.  2. 풀이 과정소행성 간의 순차적 비교와 충돌 후 상태 갱신이 필요하다.스택을 사용한다. 스택이 비어 있지 않고 스택의 최상단 소행성이 양수이고, 새로 들어오는 소행성이 음수일 때 충돌이 발생한다.스택의 소행성(stack[-1])이 절댓값이 더 작으면 스택의 소행성을 삭제한다. 이..

1. 문제 이해문자열 s가 주어진다.s에는 별표 *가 포함되어 있다.하나의 작업에서 문자열의 별표 하나를 선택하고 해당 별표의 왼쪽에 있는 가장 가까운 별표가 아닌 문자를 제거하고, 별표 자체도 제거한다.모든 별표가 제거된 후 남는 문자열을 리턴한다.  2. 풀이 과정스택 자료형을 사용한다.Python에서는 리스트를 스택처럼 사용할 수 있다. for문으로 문자열 s를 순회하면서 *라면 스택에 추가하지 않고, 스택의 가장 최근 요소를 제거한다.*가 아니라면 스택에 추가한다.  3. 전체 코드class Solution: def removeStars(self, s: str) -> str: stack = [] for char in s: if char == '*'..

1. 문제 이해n x n 정수 행렬 grid가 주어진다.행과 열을 비교하여 동일한 쌍의 개수를 리턴한다.(행과 열 쌍은 동일한 요소가 같은 순서로 포함된 경우에 동일하다.)  2. 풀이 과정딕셔너리를 만들어 행의 개수를 저장한다.튜플을 사용하여 특정 행 전체를 딕셔너리의 키로 만든다.d_row = defaultdict(int)for row in grid: d_row[tuple(row)] += 1 이번에는 특정 열 전체를 튜플로 묶어 딕셔너리를 조회한다.만약 딕셔너리에 해당 행이 존재한다면 그 개수만큼 카운트 변수를 증가시킨다.(쌍의 개수를 리턴하는 것이다.)for col in range(len(grid)): col_tuple = tuple(grid[row][col] for row in rang..

1. 문제 이해두 문자열 word1과 word2가 주어진다.word1과 word2가 "close"하다면 True를 리턴하고, 그렇지 않으면 False를 리턴한다.두 문자열이 다음의 연산을 통해 서로 변환될 수 있다면, 두 문자열은 "close"하다.연산 1: 두 문자의 위치를 교환한다.연산 2: 한 문자 전체를 다른 문자로 바꾸고, 그 반대로도 바꾼다.  2. 풀이 과정연산 1을 통해 순서는 중요하지 않다는 것을 인식한다.두 문자열의 문자 빈도를 각각 딕셔너리화한다.딕셔너리의 key 값들이 서로 같은지 확인한다.key 값에 상관없이 value 값들의 분포가 같은지 확인한다.return d1.keys() == d2.keys() and sorted(d1.values()) == sorted(d2.values(..

1. 문제 이해정수 리스트 arr가 주어진다.각 숫자가 몇 번씩 등장하는지 확인하고, 각 숫자의 등장 횟수가 모두 고유한지를 판단한다.  2. 풀이 과정Python의 딕셔너리 자료형을 사용한다.defaultdict을 사용한다. defaultdict에서는 새 키가 추가될 때, 기본값 0이 자동으로 설정된다. 각 숫자들의 등장 횟수는 딕셔너리의 value가 된다.value들의 개수와 set으로 중복을 제거한 value들의 개수가 같은지 비교한다.만약 같다면 등장 횟수가 고유한 것이다.  3. 전체 코드class Solution: def uniqueOccurrences(self, arr: List[int]) -> bool: d = defaultdict(int) for num in..

1. 문제 이해두 개의 정수 리스트 nums1과 nums2가 주어진다.크기가 2인 리스트 answer을 리턴한다.answer[0]은 nums1에만 있고 nums2에는 없는 모든 고유 정수의 리스트이다. answer[1]은 nums2에만 있고 nums1에는 없는 모든 고유 정수의 리스트이다.  2. 풀이 과정Python의 set 자료형을 사용한다.리스트를 set으로 변환시키고 각각 차집합을 구한다. 처음 짠 코드는 다음과 같다.class Solution: def findDifference(self, nums1: List[int], nums2: List[int]) -> List[List[int]]: nums1 = set(nums1) nums2 = set(nums2) ..

1. 문제 이해정수 리스트 nums가 주어진다.리스트의 pivot index를 리턴한다.pivot index는 해당 인덱스를 기준으로 인덱스의 왼쪽에 있는 모든 수의 합과 오른쪽에 있는 모든 수의 합이 동일한 인덱스를 의미한다.  2. 풀이 과정class Solution: def pivotIndex(self, nums: List[int]) -> int: for i in range(len(nums)): left_sum = 0 right_sum = 0 for i2 in range(i): left_sum += nums[i2] for i3 in range(i+1, len(nums)): ..