도니 개발노트

1. 문제 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다. 예를 들어, 문자열 S = baabaa 라면 b aa baa → bb aa → aa → 의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다. 제한사항 문자열의 길이 : 1,000,000이하의 자연수 문자열은 모두 소문자로 이루어져 있습니다. ..

1. 문제 2. 소스코드(Python3) class MyStack(object): def __init__(self): self.lst = list() def push(self, x): self.lst.append(x) def pop(self): return self.lst.pop() def size(self): return len(self.lst) class MyQueue(object): def __init__(self, max_size): self.stack1 = MyStack() self.stack2 = MyStack() self.max_size = max_size def qsize(self): return self.stack1.size() def push(self, item): if self.qsi..

1. 문제 문제 설명 게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다. U: 위쪽으로 한 칸 가기 D: 아래쪽으로 한 칸 가기 R: 오른쪽으로 한 칸 가기 L: 왼쪽으로 한 칸 가기 캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다. 예를 들어, ULURRDLLU로 명령했다면 1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다. 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다. 이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9..

1. 문제 2. 소스코드 (Python3) from itertools import combinations def solution(m, weights): answer = 0 for i in range(len(weights)): combi = combinations(weights, i) answer += [sum(candies) for candies in combi].count(m) return answer 3. 고찰 나는 재귀함수를 이용해서 풀었는데, 조합을 이용해서 풀 수 있었다. 재귀함수는 계속해서 함수를 호출하기 때문에 아마 시간복잡도 측면에서 조합 함수를 이용하는 것이 더 효율적일 것 같다.

1. 문제 2. 소스코드 (Python3) from itertools import product def solution(monster, S1, S2, S3): p = product(range(S1), range(S2), range(S3)) case = len([x for x in p if sum(x) + 4 not in monster]) return int(case / (S1 * S2 * S3) * 1000) 3. 고찰 1) product 함수 여러 list에서 원소를 하나씩 뽑아 모든 조합을 찾을 때 사용한다. 이를 곱집합 이라고 한다. from itertools import product prod = product(list1, list2, list3) ex. list1 = [0, 1, 2], list..

1. 문제 2. 소스코드 (Python3) from itertools import combinations def solution(n): sieve = [True] * n for i in range(2, int(n ** 0.5) + 1): if sieve[i]: for j in range(i * 2, n, i): sieve[j] = False prime_numbers = [i for i in range(2, n) if sieve[i]] return [sum(c) for c in combinations(prime_numbers, 3)].count(n) 3. 고찰 1) 루트값 구하기 매번 math모듈의 sqrt(n)함수를 이용하였는데, n ** 0.5 로 구할 수 있다. 2) combinations 함수 조합..

1. 문제 2. 소스코드 (Python3) DFS 코드 (성공) def inRange(n, m, i, j): if i=n or j=m: return False return True def DFS(image, visit, n, m, i, j): # 상하좌우 di = [-1, 1, 0, 0] dj = [0, 0, -1, 1] stack = [(i, j)] while stack: i1, j1 = stack.pop() visit[i1][j1] = True for d in range(4): i2 = i1 + di[d] j2 = j1 + dj[d] if not inRange(n, m, i2, j2): continue if visit[i2][j2]: continue if image[i1][j1] == image[i2..

1. 문제 2. 소스코드 def solution(s): # len(s)개 단위로 잘라 압축하는 경우 answer = len(s) # 1 ~ len(s)-1개 단위로 잘라 압축하는 경우 for l in range(1, len(s)-1): # 첫번째 압축 문자열 comp = [1, s[:l]] # 다음 문자열들에 대해서 처리 for i in range(1, len(s)//l + bool(len(s)%l)): word = s[i*l:(i+1)*l] # 앞 문자와 같으면 숫자 +1 if word == comp[-1]: comp[-2] += 1 # 앞 문자와 다르면 새로 추가 else: comp += [1, word] # int -> string으로 변환, 1이면 삭제 for i in range(0, len(co..