티스토리

도니 개발노트

검색하기

블로그 홈

도니 개발노트

donie.tistory.com/m

donie 님의 블로그입니다.

구독자: 1

방명록 방문하기

주요 글 목록

프로그래머스 - 짝지어 제거하기 1. 문제 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙입니다. 이 과정을 반복해서 문자열을 모두 제거한다면 짝지어 제거하기가 종료됩니다. 문자열 S가 주어졌을 때, 짝지어 제거하기를 성공적으로 수행할 수 있는지 반환하는 함수를 완성해 주세요. 성공적으로 수행할 수 있으면 1을, 아닐 경우 0을 리턴해주면 됩니다. 예를 들어, 문자열 S = baabaa 라면 b aa baa → bb aa → aa → 의 순서로 문자열을 모두 제거할 수 있으므로 1을 반환합니다. 제한사항 문자열의 길이 : 1,000,000이하의 자연수 문자열은 모두 소문자로 이루어져 있습니다. .. 공감수 0 댓글수 0 2020. 12. 16.
프로그래머스 - 최대 용량이 정해진 FIFO 큐 클래스 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.. 공감수 0 댓글수 0 2020. 12. 8.
프로그래머스 - 방문 길이 1. 문제 문제 설명 게임 캐릭터를 4가지 명령어를 통해 움직이려 합니다. 명령어는 다음과 같습니다. U: 위쪽으로 한 칸 가기 D: 아래쪽으로 한 칸 가기 R: 오른쪽으로 한 칸 가기 L: 왼쪽으로 한 칸 가기 캐릭터는 좌표평면의 (0, 0) 위치에서 시작합니다. 좌표평면의 경계는 왼쪽 위(-5, 5), 왼쪽 아래(-5, -5), 오른쪽 위(5, 5), 오른쪽 아래(5, -5)로 이루어져 있습니다. 예를 들어, ULURRDLLU로 명령했다면 1번 명령어부터 7번 명령어까지 다음과 같이 움직입니다. 8번 명령어부터 9번 명령어까지 다음과 같이 움직입니다. 이때, 우리는 게임 캐릭터가 지나간 길 중 캐릭터가 처음 걸어본 길의 길이를 구하려고 합니다. 예를 들어 위의 예시에서 게임 캐릭터가 움직인 길이는 9.. 공감수 0 댓글수 0 2020. 12. 7.
프로그래머스 - FloodFill 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.. 공감수 0 댓글수 0 2020. 12. 5.
프로그래머스 - 문자열 압축 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.. 공감수 0 댓글수 0 2020. 12. 5.
프로그래머스 - 세 소수의 합 1. 문제 2. 소스코드(Python3) def Eratos(n): if n N번 반복 j에 대한 for loop -> N/i번 반복 따라서 위 함수의 시간 복잡도는 O(N^2)이다. 2) add : 세 소수를 더하는 함수 1) 알고리즘 odd의 세 원소를 꺼낸다. 세 값을 더한 결과가 주어진 수 n과 같은지 비교하여 횟수를 센다. 2) 시간복잡도 odd의 원소 개수가 N이라고 하자. odd의 세 원소에 대해 삼중 for문 -> O(N^3) 3) solution : main함수 1) 알고리즘 n이하의 소수를 모두 구하여 odd리스트에 저장한다. add함수를 이용하여 세 숫자를 더하여 n이 되는 경우의 수를 센다. 2) 시간복잡도 Eratos함수의 시간 복잡도는 O(N^2)이다. add함수는 주어진 입력이.. 공감수 0 댓글수 0 2020. 12. 4.
프로그래머스 - 대중소 괄호 짝 맞추기 1. 문제 2. 소스코드 def solution(s): stack = [] match = {'(':')', '{':'}', '[':']' } for x in s: # 여는 괄호 if x in match: stack.append(x) # 닫는 괄호 else: if not stack: return False if match[stack.pop()] != x: return False return not stack 3. 고찰 1) 알고리즘 여는 괄호이면 스택에 push 닫는 괄호이면 (1) 스택이 비어있는지 검사 (2) 스택의 top과 매치하는 괄호인지 검사한다. 문자열 s의 모든 괄호에 대해 위 과정을 반복한 후 스택이 비어있으면 True를 리턴한다. 2) 시간복잡도 문자열 s의 모든 괄호에 대해 for loo.. 공감수 0 댓글수 0 2020. 12. 4.
프로그래머스 - 좌석 구매 1. 문제 2. 소스코드 (Python3) def solution(seat): answer = len(seat) Set = {} for s in seat: index = 100000*s[0] + s[1] if index in Set: answer -= 1 else: Set.add(index) return answer 3. 고찰 1) 알고리즘 모든 seat에 대해서 set에 넣고, 이미 해당 좌석이 set에 들어있다면 정답에서 한 명씩 빼는 알고리즘. 이때 좌석은 100000 * 100000 크기로 2차원이므로 좌석의 좌표는 x좌표 * 100000 + y좌표로 계산하였다. 2) 시간복잡도 모든 seat의 원소에 대해서 for loop -> O(N) Set에 해당 좌표(index)가 있는지 확인 -> O(N.. 공감수 0 댓글수 0 2020. 12. 4.
프로그래머스 - 더 맵게 1. 문제 programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 2. 소스코드 (Python3) import heapq def solution(scoville, K): answer = 0 scoville = [s for s in scoville] heapq.heapify(scoville) while True: tmp1 = heapq.heappop(scoville) if tmp1 >= K: break if not sc.. 공감수 0 댓글수 0 2020. 12. 3.
프로그래머스 - 큰 수 만들기 1. 문제 programmers.co.kr/learn/courses/30/lessons/42883 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 2. 소스코드 (Python3) def solution(number, k): stack = [] for n in number: while stack and stack[-1] O(N) 리스트.pop() -> O(1) 리스트.append() -> O(1) 따라서 위 코드의 시간복잡도는 O(N)이다. 공감수 0 댓글수 0 2020. 12. 3.
프로그래머스 - 가장 큰 수 1. 문제 programmers.co.kr/learn/courses/30/lessons/42746 코딩테스트 연습 - 가장 큰 수 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 programmers.co.kr 2. 소스코드 (Python3) import functools def comp(a,b): if int(a+b) int(b+a): return -1 return 0 def solution(numbers): strnum = [str(n) for.. 공감수 0 댓글수 0 2020. 12. 3.
프로그래머스 - 체육복 1. 문제 programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 2. 소스코드 (Python3) def solution(n, lost, reserve): answer = 0 student = {} for x in lost: student[x] = student.get(x, 1) -1 for x in reserve: student[x] = student.get(x, 1) +1 lost = [k for k,v in student.it.. 공감수 0 댓글수 0 2020. 12. 3.
프로그래머스 - 완주하지 못한 선수 1. 문제 programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 2. 소스코드 (Python3) def solution(participant, completion): hash = {} for p in participant: hash[p] = hash.get(p, 0) + 1 for c in completion: hash[c] -= 1 ans = [k for k, v in hash.items() if v > 0.. 공감수 0 댓글수 0 2020. 12. 3.
프로그래머스_문자열 압축 1. 문제 2. 소스코드 (Python3) def solution(s): # wordlen=len(s)이면 압축문자열 길이 = len(s) answer = len(s) for wordlen in range(1, len(s)-1): #문자길이가 1~len(s)-1까지 반복. wordcnt = len(s)//wordlen #문자뭉텅이 개수 = 전체문자열길이에서 문자길이 나눈 몫 comp = False #False=압축x, True=압축o compcnt = 0 #압축되는 문자뭉텅이 개수 compstr = '' #압축된 문자열 ## j번째 문자뭉텅이 처리 for j in range(wordcnt): word1 = s[j*wordlen: (j+1)*wordlen] word2 = s[(j+1)*wordlen: (j.. 공감수 0 댓글수 0 2020. 11. 4.
프로그래머스_H-Index 1. 문제 2. 소스코드 def solution(citations): h=len(citations) while h: higher = 0 lower = 0 for c in citations: if c>=h: higher += 1 else: lower += 1 if higher>=h and: return h h-=1 return h 3. 고찰 1) 알고리즘 n편 중 h편이기 때문에 h의 초기값을 len(citations)로 설정했다. 최대값을 찾는 문제이므로 위에서부터 내려가며 h값을 찾았다. while loop를 돌면서 h번 이상 인용된 논문 개수는 higher에, 나머지 논문 개수는 lower에 세었다. higher개수가 h편 이상이면 h를 리턴하였다. h에 -1 해주었다. 2) 시간복잡도 입력 리스트 .. 공감수 0 댓글수 0 2020. 11. 3.
Quick Sort 파이썬 구현 1. 소스코드 import random def QuickSort(list): if len(list) 공감수 0 댓글수 0 2020. 11. 2.
프로그래머스_조이스틱 1. 문제 2. 소스코드 cntlist = [1000000000] #이름을 완성했을 때 횟수를 저장하는 배열 ## 'A'부터 올려가며/내려가며 문자로의 조작횟수 비교, 작은 것 선택 def count(name, idx): return min(ord(name[idx])-ord('A'), ord('Z')-ord(name[idx])+1) ## 조이스틱 def Joystick(name, naming, idx, cnt, rlcnt, rl): if rlcnt == len(name): return # 좌우 조작횟수가 이름의 길이가 되면 불필요한 좌우이동 -> 리턴 if cnt >= min(cntlist): return # 현재 cnt보다 적은 횟수로 이름을 완성할 수 있다면 이후 계산이 불필요 -> 리턴 if nam.. 공감수 0 댓글수 0 2020. 11. 2.
프로그래머스_월간 코드 챌린지 시즌1_두 개 뽑아서 더하기 1. 문제 2. 소스코드 def solution(numbers): answer = set() for i in range(len(numbers)): for j in range(i+1,len(numbers)): answer.add(numbers[i] + numbers[j]) answer = list(answer) answer.sort() return answer 3. 고찰 1) 알고리즘 인덱스를 이용해서 두 수를 뽑았다. 더한 수를 answer에 넣었는데, answer는 set을 사용하였다. set은 list와 다르게 중복 원소는 한 개만 저장하는 특징이 있다. 하지만 sort를 할 수 없어서 answer를 다시 list로 변경한 후 오름차순으로 정렬하였다. 2) 시간복잡도 이중 for문을 사용하기 때문에 .. 공감수 0 댓글수 0 2020. 11. 1.
프로그래머스_전화번호 목록 1. 문제 2. 소스코드 ( python3 ) def solution(phone_book): answer = True for i in range(len(phone_book)): for j in range(i+1, len(phone_book)): I, J = str(phone_book[i]), str(phone_book[j]) lenI, lenJ = len(I), len(J) if lenI > lenJ: if I[:lenJ] == J : return False else: if I == J[:lenI] : return False return answer 3. 고찰 1) 문제 이해 하나의 번호가 다른 번호의 앞에 오는지를 확인하는 문제이다. 처음에 문제를, 한 번호가 다른 번호에 속해있는지 확인하는 문제로 착.. 공감수 0 댓글수 0 2020. 10. 30.
프로그래머스_큰 수 만들기 1. 문제 2. 소스코드 def solution(number, k): answer = '' number = list(number) stack = [] for n in number: while stack and stack[-1] < n and k: stack.pop() k -= 1 stack.append(n) if k: stack = stack[:-k] return ''.join(stack) 3. 고찰 1) 스택 이용 새로 원소를 추가할 때 바로 앞 원소와만 비교를 하기 때문에 스택이용이 가능하다. 2) 알고리즘 문자열인 number를 문자 리스트형태로 바꿔주었다. (하나씩 for문을 돌리기 위함. 이렇게 하지 않고, 먼저 스택에 첫번째 숫자를 넣어준 뒤 for num in number[1:]: 이렇게 f.. 공감수 0 댓글수 0 2020. 10. 30.
프로그래머스_카펫 1. 문제 2. 소스코드 import math def solution(brown, yellow): answer = [] all = brown + yellow for col in range(3, int(math.sqrt(all))+1): if all % col: continue row = all // col if (row-2) * (col-2) == yellow: return [row, col] 3. 고찰 1) 알고리즘 전체 카펫 격자 개수를 all에 담았다. 세로 < 가로 이기 때문에 세로에 대해 for문을 돌렸다. 가로에 대해서 돌리려면 루트(전체 격자개수) ~ 전체격자개수로 돌리면 된다. 가로, 세로의 최소 개수는 3이다. yellow의 상하좌우에 brown이 1줄씩 있기 때문. 세로col을 3~루트.. 공감수 0 댓글수 0 2020. 10. 30.
프로그래머스_구명보트 1. 문제 2. 소스코드 def solution(people, limit): answer = len(people) HeavyIndex = 0 #무거운 사람 순서 LightIndex = len(people) - 1 #가벼운 사람 순서 people.sort(reverse = True) while HeavyIndex 공감수 0 댓글수 0 2020. 10. 29.
프로그래머스_기능개발 1. 문제 2. 소스코드 import math def solution(progresses, speeds): answer = [] now = 0 next = 0 daysleft = [math.ceil((100-progresses[i])/speeds[i]) for i in range(len(progresses))] print(daysleft) while next!=len(progresses): now = next next+= 1 count = 1 for i in range(now +1, len(progresses)): if daysleft[now] >= daysleft[i]: count += 1 next+= 1 else: break answer.append(count) return answer 3. 고찰 1.. 공감수 0 댓글수 0 2020. 10. 4.
프로그래머스_더 맵게 1. 문제 2. 소스코드 import heapq def solution(scoville, K): answer = 0 heapq.heapify(scoville) # scoville을 min heap으로 만들기 while True: first = heapq.heappop(scoville) # 가장 작은 원소 pop if first >= K: # 가장 작은 원소의 스코빌지수 >= K이면 문제 종료 #print("answer= ", answer) return answer if not scoville: # scoville이 비었으면 더 이상 못 함 return -1 # -1 리턴 second = heapq.heappop(scoville) # 두번째로 작은 원소 pop new = first + 2*second # .. 공감수 0 댓글수 0 2020. 10. 3.
프로그래머스_프린터 1. 문제 2. 소스코드 ( Python3 ) def search(priorities, next, cnt): index = next for i in range(cnt-1): index += 1 if index == cnt: index = 0 if priorities[next] < priorities[index]: next = index return next def solution(priorities, location): answer = 0 # 변수 next = 0 # 다음에 프린트할 문서 index cnt = len(priorities) # 전체 문서 개수 while True: # next 찾기 next = search(priorities, next, cnt) # 프린트 하기 answer += 1 if .. 공감수 0 댓글수 0 2020. 10. 1.
프로그래머스_다리를 건너는 트럭 1. 문제 2. 소스코드 ( Python3 ) def solution(bridge_length, weight, truck_weights): answer = 0 start = 0 # 다음에 건널 트럭 번호 finish = 0 # 다음에 다 건널 트럭 번호 on_bridge = 0 # 다리 위 트럭 무게 time = [] # 트럭이 다리 건너기 시작한 시각 time_now = 0 # 현재 시각 # 1초 후 time_now += 1 on_bridge = truck_weights[start] start += 1 time.append(time_now) # 반복 while finish != len(truck_weights): # 시간 경과 time_now += 1 # 다 건넌 트럭 OUT if time_now - .. 공감수 0 댓글수 0 2020. 9. 28.
프로그래머스_주식가격 1. 문제 2. 소스코드 (python3) def solution(prices): answer = [] for i in range(len(prices)-1): # i = 0 ~ 마지막-1 cnt = 1 for j in range(i+1, len(prices)-1): #j = i+1 ~ 마지막 if prices[i] 공감수 0 댓글수 0 2020. 9. 28.
프로그래머스_코딩테스트연습_124나라의 숫자 1. 문제 2. 소스코드 def calc(r, answer): if r==0 : answer = '1' + answer elif r==1 : answer = '2' + answer else : answer = '4' + answer #print('answer: ' , answer) return answer def solution(n): answer = '' q, r = divmod(n-1, 3) #(n-1)/3의 몫, 나머지 #print('q, r = ', q, ' ', r) while q != 0 : #몫=0이면 종료 #print('q, r = ', q, ' ', r) answer = calc(r, answer) q, r = divmod(q-1, 3) answer = calc(r, answer) #pr.. 공감수 0 댓글수 0 2020. 9. 24.
백준 #9093 문제풀기 전에 우선 python 버전 확인 1. 문제 2. 소스코드 tc = int(input()) for i in range(tc): text = input() #문장 입력받기 cnt = text.count(' ')+1 #문자개수 = 공백 개수+1 for j in range(cnt): print(text.split(' ')[j][::-1] + ' ', end='') print() 3. 고찰 - python 입력받는 방법 : 변수 = input() - 문자열 내 특정 문자 세는 함수 : 문자열.count('문자') - string을 int로 : int(string형 변수) - 문자열 자르기 : 문자열.split() - 문자열 거꾸로 : 문자열[::-1] - print 이어서 출력하기 : print("프린.. 공감수 0 댓글수 0 2020. 9. 22.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.