본문 바로가기

IT관련정보/카카오 코딩테스트 1차(2017년)

 (7)
7. 추석 트래픽(난이도: 상) - Python3.6.1 1.풀이방법 초당최대처리량을 계산해야한다. 단위가 최소 0.001초이기 때문에 처음부터 0.001초씩 증가시키면서 스캔하기에는 연산시간이 너무 오래걸리기 때문에 이렇게 풀면 안된다. 모든 로그의 시작과 끝점을 가지고 계산하면 편하다.모든 로그의 끝부분 부터 이후 1초까지 사이를 계산했다. *시간복잡도 O(n²)이 나온다. 시간되면 다른 방법을 더 찾아봐야겠다. 2.코드 import datetimefrom time import localtime,strftime def Question7(lines): start = [] end = [] maxCount = 0 for i in range(len(lines)): #1 endTime = datetime.datetime.strptime(lines[i][0:23],'..
6. 프렌즈4블록(난이도: 상) - Python3.6.1 1.풀이방법 4개의 블록을 찾아서 제거하면 된다. 하지만 바로 제거하면 다음블록에서 4개의 블록이 안지워질수도 있으므로(라이언 A블록 6개 참조) 모든블럭을 스캔후에 지워야한다.순서로 보면1.지워야 할 블록 스캔2.지울 블록이 없을경우 지운블록갯수 반환, 지울 블록이 있을경우 다음으로 이동3.블록삭제하면서 삭제할때마다 카운트 증가4.블록재정렬5.이후 계속 반복라고 보면된다. 2.코드 def Question6(m,n,board): arr = [[board[m][n] for n in range(n)] for m in range(m)] #1 count = 0 #2 while True: #3 removeList = set('') #4 for height in range(m-1): #5 for width in r..
5. 뉴스 클러스터링(난이도: 중) - Python3.6.1 1.풀이방법 딕셔너리(Dict)를 이용해서 풀어봤다. A = {1, 1, 2, 2, 3} , B = {1, 2, 2, 4, 5}A = 1:2개 B = 1:1개 2:2개 2:2개 3:1개 4:1개 5:1개 A ∩ B = {1, 2, 2} => 1:1개,2:2개 - 공통되는것중 개수가 적은쪽 기준 A ∪ B = {1, 1, 2, 2, 3, 4, 5} => 1:2개,2:2개,3:1개,4:1개,5:1개 - 모든항목 개수가 많은쪽 기준 2.코드 import collections def Question5(str1,str2): if not(len(str1) >= 2 and len(str1) = 2 and len(str2) 0 and collect2[i]>0: #교집합 카운트 if collect1[i] < collec..
4. 셔틀버스(난이도: 중) - Python3.6.1 1.풀이방법 입력된 셔틀운행횟수(n)와 셔틀운행간격(t)를 가지고 셔틀도착시간을 모두 가지고온다. n=2, t = 10 => ['09:00','09:10']timetable에 입력된 (['09:10', '09:09', '08:00']) 크루를 시간에 맞게 태운다.00:01~09:00 - 08:00(1명)00:01~09:10 - 09:09,09:10(2명) *중요*여기서 00:01로 계속 계산하는 이유는 09:00이전에 도착했지만 탑승을 못할경우 09:10버스에 태워야하기 때문이다. 셔틀에 자리가 남을경우 마지막 셔틀도착시간 09:10를 반환해준다.셔틀에 자리가 없을경우 마지막에 탑승한 크루시간 09:10에서 1분전 09:09를 반환해준다. 2.코드 def Question4(n,t,m,timeTable):..
3. 캐시(난이도: 하) - Python3.6.1 1.풀이방법 LRU(Least Recently Used)알고리즘을 사용한다.:LRU알고리즘은 페이지 교체 전략 중의 하나로 사용한지 가장 오래된 항목부터 버리는 방식이다. 같은 도시이름이라도 대소문자에 따라서 다르게 인식할 수 있으니 모두 소문자로 통일한다음 캐시에 적재한다.캐시에 새롭게 추가될 경우 cache miss - 5 , 캐시에 데이터가 있을 경우 cache hit - 1 2.코드 def Question3(cacheSize,cities): if cacheSize 30: #1 return 'out of range!' if cacheSize == 0: #2 return len(cities)*5 cities = [x.lower() for x in cities] #3 page = [0 for i in ..
2. 다트 게임(난이도: 하) - Python3.6.1 1.풀이방법 토큰화로 처리할 때는 정규표현식(re.findall)을 이용해 숫자와 문자를 나누어 처리하면 편리하다. Single(S) = ^2Double(D) = ^3Triple(T) = ^4스타상(*) = *2 or *2,*2아차상(#) = -1 각각의 문자를 문자열로 된 수식어로 변환후(# -> -1) return 할때 문자열을 수식으로 계산 후 반환한다. 2.코드 import re def Question2(dartResult): arr = re.findall('\d+\D+',dartResult) #1 for i in range(3): if '*' in arr[i]: if i == 0: #2 arr[i] += '2' else: arr[i] += '2' arr[i-1] += '*2' if 'S' in ..
1. 비밀 지도(난이도: 하) - Python3.6.1 1.풀이방법 숫자 0 - False / 나머지(1) - True0+0 = 0 -> False + False = False0+1 = 1 -> False + True = True1+0 = 1 -> True + False = True1+1 = 1 -> True + True = True비트연산자 OR( | )를 사용한다. 2.코드 def Question1(n,arr1,arr2): if n 16: #1 return 'out of range!' arr = [] for i in range(n): #2 temp_str = format(arr1[i]|arr2[i],str(n)+'b') #3 temp_str = temp_str.replace('0',' ') #4 temp_str = temp_str.re..

티스토리툴바