문제 설명

지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

블라인드 공채를 통과한 신입 사원 라이언은 신규 게임 개발 업무를 맡게 되었다. 이번에 출시할 게임 제목은 "프렌즈4블록".같은 모양의 카카오프렌즈 블록이 2×2 형태로 4개가 붙어있을 경우 사라지면서 점수를 얻는 게임이다.

만약 판이 위와 같이 주어질 경우, 라이언이 2×2로 배치된 7개 블록과 콘이 2×2로 배치된 4개 블록이 지워진다. 같은 블록은 여러 2×2에 포함될 수 있으며, 지워지는 조건에 만족하는 2×2 모양이 여러 개 있다면 한꺼번에 지워진다.

블록이 지워진 후에 위에 있는 블록이 아래로 떨어져 빈 공간을 채우게 된다.

만약 빈 공간을 채운 후에 다시 2×2 형태로 같은 모양의 블록이 모이면 다시 지워지고 떨어지고를 반복하게 된다.

위 초기 배치를 문자로 표시하면 아래와 같다.

입력 형식

• 입력으로 판의 높이 m, 폭 n과 판의 배치 정보 board가 들어온다.
• 2 ≦ n, m ≦ 30
• board는 길이 n인 문자열 m개의 배열로 주어진다. 블록을 나타내는 문자는 대문자 A에서 Z가 사용된다.

출력 형식

입력으로 주어진 판 보를 가지고 몇 개의 블록이 지워질지 출력하라.

코드

def recur(board, ans):
    remove = []
    cnt = 0
    y_dir = [0,1,0,1]
    x_dir = [0,0,1,1]
    for y in range(len(board)-1): #지워야 할 부분 찾기
        for x in range(len(board[0])-1):
            flag = 0
            if board[y][x] == "": continue
            for i in range(1,4):
                if board[y][x] == board[y+y_dir[i]][x+x_dir[i]]:
                    continue
                else:
                    flag = 1
                    break
            if flag == 0:
                remove.append((y,x))
                
    for r in remove: # 지우기
        y, x = r
        for i in range(4):
            if board[y+y_dir[i]][x+x_dir[i]] != "":
                board[y+y_dir[i]][x+x_dir[i]] = ""
                cnt += 1
            
    for x in range(len(board[0])): # 밑으로 채우기
        tmp = []
        for y in reversed(range(len(board))):
            if board[y][x] != "":
                tmp.append(board[y][x])
        i = 0
        for y in reversed(range(len(board))):
            if i < len(tmp):
                board[y][x] = tmp[i]
            else:
                board[y][x] = ""
            i += 1
    if cnt == 0:
        return ans
    else:
        return recur(board, cnt+ans)
            
    
    
def solution(m, n, board):
    answer = 0
    board =list(map(list, board))
    answer = recur(board, 0)
    return answer

후기

보드를 처음에 완전 탐색하여 제거 가능한 블록을 찾고, 다시 완전 탐색하여 제거하고, 다시 완전 탐색하여 밑으로 당겨주었는데 처음에 한번에 모든 것을 다 하려 했더니 안되는 조건들이 있었다. 문제가 어려워 보였지만 이러한 조건만 잘 탐색하면 쉽게 풀 수 있다.

알고리즘

• 재귀
• 완전 탐색

문제 설명

지도개발팀에서 근무하는 제이지는 지도에서 도시 이름을 검색하면 해당 도시와 관련된 맛집 게시물들을 데이터베이스에서 읽어 보여주는 서비스를 개발하고 있다.이 프로그램의 테스팅 업무를 담당하고 있는 어피치는 서비스를 오픈하기 전 각 로직에 대한 성능 측정을 수행하였는데, 제이지가 작성한 부분 중 데이터베이스에서 게시물을 가져오는 부분의 실행시간이 너무 오래 걸린다는 것을 알게 되었다.어피치는 제이지에게 해당 로직을 개선하라고 닦달하기 시작하였고, 제이지는 DB 캐시를 적용하여 성능 개선을 시도하고 있지만 캐시 크기를 얼마로 해야 효율적인지 몰라 난감한 상황이다.

어피치에게 시달리는 제이지를 도와, DB 캐시를 적용할 때 캐시 크기에 따른 실행시간 측정 프로그램을 작성하시오.

입력 형식

• 캐시 크기(cacheSize)와 도시이름 배열(cities)을 입력받는다.
• cacheSize는 정수이며, 범위는 0 ≦ cacheSize ≦ 30 이다.
• cities는 도시 이름으로 이뤄진 문자열 배열로, 최대 도시 수는 100,000개이다.
• 각 도시 이름은 공백, 숫자, 특수문자 등이 없는 영문자로 구성되며, 대소문자 구분을 하지 않는다. 도시 이름은 최대 20자로 이루어져 있다.

출력 형식

• 입력된 도시이름 배열을 순서대로 처리할 때, "총 실행시간"을 출력한다.

조건

• 캐시 교체 알고리즘은 LRU(Least Recently Used)를 사용한다.
• cache hit일 경우 실행시간은 1이다.
• cache miss일 경우 실행시간은 5이다.

코드

def solution(cacheSize, cities):
    answer = 0
    q = [] #cache
    if cacheSize == 0:
        return 5 * len(cities)
    for i in range(len(cities)):
        tmp = ''
        for c in cities[i]: #소문자로 변환
            if ord(c) < 97:
                tmp += chr(ord(c)+32)
            else:
                tmp += c
                
        cities[i] = tmp       
        if len(q) < cacheSize: #캐시에 빈자리가 있을 때
            if cities[i] not in q: #miss
                answer += 5
                q.append(cities[i])
            else: # hit
                answer += 1
                tmp = q.pop(q.index(cities[i]))
                q.append(tmp)
        else:
            if cities[i] in q: #hit
                answer += 1
                tmp = q.pop(q.index(cities[i]))
                q.append(tmp)
            else: 
                answer += 5
                q.pop(0)
                q.append(cities[i])
    return answer

후기

LRU 알고리즘에 대한 이해가 없으면 풀 수 없는 문제이고 난이도는 쉬운 편이다. 대문자 소문자 구분이 없는 경우와 캐쉬 크기가 0일 경우만 생각하면 된다.

알고리즘

• 큐

문제 설명

이번 추석에도 시스템 장애가 없는 명절을 보내고 싶은 어피치는 서버를 증설해야 할지 고민이다. 장애 대비용 서버 증설 여부를 결정하기 위해 작년 추석 기간인 9월 15일 로그 데이터를 분석한 후 초당 최대 처리량을 계산해보기로 했다. 초당 최대 처리량은 요청의 응답 완료 여부에 관계없이 임의 시간부터 1초(=1,000밀리초)간 처리하는 요청의 최대 개수를 의미한다.

입력 형식

• solution 함수에 전달되는 lines 배열은 N(1 ≦ N ≦ 2,000)개의 로그 문자열로 되어 있으며, 각 로그 문자열마다 요청에 대한 응답완료시간 S와 처리시간 T가 공백으로 구분되어 있다.
• 응답완료시간 S는 작년 추석인 2016년 9월 15일만 포함하여 고정 길이 2016-09-15 hh:mm:ss.sss 형식으로 되어 있다.
• 처리시간 T는 0.1s, 0.312s, 2s 와 같이 최대 소수점 셋째 자리까지 기록하며 뒤에는 초 단위를 의미하는 s로 끝난다.
• 예를 들어, 로그 문자열 2016-09-15 03:10:33.020 0.011s은 "2016년 9월 15일 오전 3시 10분 33.010초"부터 "2016년 9월 15일 오전 3시 10분 33.020초"까지 "0.011초" 동안 처리된 요청을 의미한다. (처리시간은 시작시간과 끝시간을 포함)
• 서버에는 타임아웃이 3초로 적용되어 있기 때문에 처리시간은 0.001 ≦ T ≦ 3.000이다.
• lines 배열은 응답완료시간 S를 기준으로 오름차순 정렬되어 있다.

출력 형식

• solution 함수에서는 로그 데이터 lines 배열에 대해 초당 최대 처리량을 리턴한다.

코드

def solution(lines):
    answer = 0
    start_list = [] #시작 시간 
    end_list = []  # 종료 시간
    for line in lines: # 시작시간과 종료시간을 리스트에 넣어주기
        date, time, pro = line.split()
        pro = int(float(pro[:-1]) * 1000)
        h, m, sec = time.split(":")
        h = int(h) * 3600
        m = int(m) * 60
        s, ms = list(map(int,sec.split(".")))
        end_time = (h + m + s)*1000 + ms
        start_time = end_time - pro + 1
        start_list.append(start_time)
        end_list.append(end_time)
        
    for i in range(len(start_list)): 
        s1 = start_list[i]
        e1 = end_list[i]
        count = 1
        for j in range(i+1,len(start_list)):
            if i == j: continue
            s2 = start_list[j]
            e2 = end_list[j]
            if e1 > s2 -1000 :#현재의 종료지점이 다음의 시작시간 -1초 보다 크면 count 
                count += 1
        answer = max(count, answer)
    return answer

후기

문제 자체는 어렵지 않았으나 현재의 종료 지점이 다음의 시작 시간 -1초 보다 크면 센다는 조건을 떠올리기 쉽지 않았다.

분류

• 그리디

카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다.

이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자.

• 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다.
• 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다.

일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 알아냈다. 콘이 셔틀을 타고 사무실로 갈 수 있는 도착 시각 중 제일 늦은 시각을 구하여라.

단, 콘은 게으르기 때문에 같은 시각에 도착한 크루 중 대기열에서 제일 뒤에 선다. 또한, 모든 크루는 잠을 자야 하므로 23:59에 집에 돌아간다. 따라서 어떤 크루도 다음날 셔틀을 타는 일은 없다.

입력 형식

셔틀 운행 횟수 n, 셔틀 운행 간격 t, 한 셔틀에 탈 수 있는 최대 크루 수 m, 크루가 대기열에 도착하는 시각을 모은 배열 timetable이 입력으로 주어진다.

• 0 ＜ n ≦ 10
• 0 ＜ t ≦ 60
• 0 ＜ m ≦ 45
• timetable은 최소 길이 1이고 최대 길이 2000인 배열로, 하루 동안 크루가 대기열에 도착하는 시각이 HH:MM 형식으로 이루어져 있다.
• 크루의 도착 시각 HH:MM은 00:01에서 23:59 사이이다.

출력 형식

콘이 무사히 셔틀을 타고 사무실로 갈 수 있는 제일 늦은 도착 시각을 출력한다. 도착 시각은 HH:MM 형식이며, 00:00에서 23:59 사이의 값이 될 수 있다.

코드

def solution(n, t, m, timetable):
    answer = ''
    time_list = []
    tmp_answer = 0
    for time in timetable: #시간 변환
        hour, minute = time.split(":")
        time_list.append(int(hour)*60 + int(minute))
    start = 540 # 9시 00분
    time_list.sort() # 오름차순으로 정렬
    onBus = [0] * n
    bus = 0
    i = 0
    
    while bus < n: #탈 수 있을 때
        if onBus[bus] < m and time_list[i] <= start:
            onBus[bus] += 1
        else: #못탈때 다음 버스로 바꾸기
            bus += 1
            start += t
            continue
        i += 1 
        if i >= len(time_list):
            break
    print(onBus)
    
    last = i - 1 #마지막에 탄 사람 위치
    print(last)
    if onBus[-1] < m: #마지막 버스에 자리 있으면 그냥 거기 타기
        tmp_answer = 540 + (t * (n-1))
    else: # 마지막 버스 꽉차 있으면 야비하게 마지막 사람보다 1분 빨리 오기
        tmp_answer = time_list[last] - 1
        
    hour = tmp_answer // 60
    minute = tmp_answer % 60
    # 정답 형식에 맞추기
    if(hour < 10):
        answer += '0' 
    answer += str(hour)
    answer += ':'
    if(minute < 10):
        answer += '0'
    answer += str(minute)
        
    return answer

후기

조건이 까다로워서 처음에 잘 못 접근하면 아주 헤매게 된다.. 나는 모든 회사원이 당연히 버스를 타야한다고 생각했는데 그럴 필요 없이 마지막 사람보다 일찍 타서 마지막 사람을 못타게 만들면 된다. 문제 이해가 어려웠지만 구현하는 것은 그렇게 어렵지 않았다.

알고리즘

• 정렬
• 단순 구현

문제 설명

네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다.

1. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다.
2. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다.
3. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다.
4. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1, 공백 부분을 0으로 부호화했을 때 얻어지는 이진수에 해당하는 값의 배열이다.

네오가 프로도의 비상금을 손에 넣을 수 있도록, 비밀지도의 암호를 해독하는 작업을 도와줄 프로그램을 작성하라.

입력 형식

입력으로 지도의 한 변 크기 n 과 2개의 정수 배열 arr1, arr2가 들어온다.

• 1 ≦ n ≦ 16
• arr1, arr2는 길이 n인 정수 배열로 주어진다.
• 정수 배열의 각 원소 x를 이진수로 변환했을 때의 길이는 n 이하이다. 즉, 0 ≦ x ≦ $2^n - 1$을 만족한다.

출력 형식

원래의 비밀지도를 해독하여 '#', 공백으로 구성된 문자열 배열로 출력하라.

코드

def trans(num, n): #2진수로 바꾸기
    arr = []
    while(n > 0): # 길이를 맞춰야 하기 때문에 다 끝나도 0 계속 추가
        tmp = num % 2
        num = num // 2
        arr.insert(0, tmp)
        n -= 1
    return arr
        
def solution(n, arr1, arr2):
    answer = []
    for i in range(n):
        s = ""
        a1 = trans(arr1[i],n)
        a2 = trans(arr2[i],n)
        for j in range(n):
            tmp = a1[j] + a2[j]
            if tmp == 0:
                s += ' '
            else:
                s += '#'
        answer.append(s)
    
    return answer

후기

단순 구현 문제라 어렵지 않았다. 2진수를 구할 때 길이를 유지하며 구하는 방법이 핵심이다.

분류

• 구현

다트 게임

카카오톡에 뜬 네 번째 별! 심심할 땐? 카카오톡 게임별~

카카오톡 게임별의 하반기 신규 서비스로 다트 게임을 출시하기로 했다. 다트 게임은 다트판에 다트를 세 차례 던져 그 점수의 합계로 실력을 겨루는 게임으로, 모두가 간단히 즐길 수 있다.갓 입사한 무지는 코딩 실력을 인정받아 게임의 핵심 부분인 점수 계산 로직을 맡게 되었다. 다트 게임의 점수 계산 로직은 아래와 같다.

1. 다트 게임은 총 3번의 기회로 구성된다.
2. 각 기회마다 얻을 수 있는 점수는 0점에서 10점까지이다.
3. 점수와 함께 Single(S), Double(D), Triple(T) 영역이 존재하고 각 영역 당첨 시 점수에서 1제곱, 2제곱, 3제곱 ($점수^1$ , $점수^2$ , $점수^3$ )으로 계산된다.
4. 옵션으로 스타상(*) , 아차상(#)이 존재하며 스타상(*) 당첨 시 해당 점수와 바로 전에 얻은 점수를 각 2배로 만든다. 아차상(#) 당첨 시 해당 점수는 마이너스된다.
5. 스타상(*)은 첫 번째 기회에서도 나올 수 있다. 이 경우 첫 번째 스타상(*)의 점수만 2배가 된다. (예제 4번 참고)
6. 스타상(*)의 효과는 다른 스타상(*)의 효과와 중첩될 수 있다. 이 경우 중첩된 스타상(*) 점수는 4배가 된다. (예제 4번 참고)
7. 스타상(*)의 효과는 아차상(#)의 효과와 중첩될 수 있다. 이 경우 중첩된 아차상(#)의 점수는 -2배가 된다. (예제 5번 참고)
8. Single(S), Double(D), Triple(T)은 점수마다 하나씩 존재한다.
9. 스타상(*), 아차상(#)은 점수마다 둘 중 하나만 존재할 수 있으며, 존재하지 않을 수도 있다.

0~10의 정수와 문자 S, D, T, *, #로 구성된 문자열이 입력될 시 총점수를 반환하는 함수를 작성하라.

입력 형식

"점수|보너스|[옵션]"으로 이루어진 문자열 3세트.예)  1S2D*3T

• 점수는 0에서 10 사이의 정수이다.
• 보너스는 S, D, T 중 하나이다.
• 옵선은 *이나 # 중 하나이며, 없을 수도 있다.

출력 형식

3번의 기회에서 얻은 점수 합계에 해당하는 정수값을 출력한다.예) 37

코드

def solution(dartResult):
    answer = 0
    num = 0
    num_list = []
    for i, c in enumerate(dartResult): #한 글자 씩 보면서 확인
        if c >= '0' and c <= '9': 
            if i != 0:  # 숫자면 그전의 계산값 리스트에 넣어주기
                num_list.append(num)
            num = int(c)
            if dartResult[i-1] == '1': #0일때 그 전이 1이면 10으로 바꾸기
                num = 10
                num_list.pop() #위에서 이미 1을 리스트에 넣었기 때문에 다시 빼주기
        if c == 'D':
            num = num ** 2
        if c == 'T':
            num = num ** 3
        if c == '*':
            num *= 2
            if len(num_list) != 0:
                num_list[-1] *= 2
        if c == '#':
            num *= -1
    num_list.append(num) #마지막 계산값도 넣어주기
    answer = sum(num_list)
       
    return answer

후기

숫자 '10'의 대한 처리와 옵션의 유무를 처리하는 것이 핵심인 문제이다. 난이도 자체는 어렵지 않았는데 10에 대한 처리를 잘못해서 헤맸다.

알고리즘

• 구현

문제 설명

카카오에 입사한 신입 개발자 네오는 "카카오계정개발팀"에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. "네오"에게 주어진 첫 업무는 새로 가입하는 유저들이 카카오 아이디 규칙에 맞지 않는 아이디를 입력했을 때, 입력된 아이디와 유사하면서 규칙에 맞는 아이디를 추천해주는 프로그램을 개발하는 것입니다.다음은 카카오 아이디의 규칙입니다.

• 아이디의 길이는 3자 이상 15자 이하여야 합니다.
• 아이디는 알파벳 소문자, 숫자, 빼기(``), 밑줄(_), 마침표(.) 문자만 사용할 수 있습니다.
• 단, 마침표(.)는 처음과 끝에 사용할 수 없으며 또한 연속으로 사용할 수 없습니다.

"네오"는 다음과 같이 7단계의 순차적인 처리 과정을 통해 신규 유저가 입력한 아이디가 카카오 아이디 규칙에 맞는 지 검사하고 규칙에 맞지 않은 경우 규칙에 맞는 새로운 아이디를 추천해 주려고 합니다.신규 유저가 입력한 아이디가 new_id 라고 한다면,

1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. 2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다. 3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다. 4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다. 5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다. 6단계 new_id의 길이가 16자 이상이면, new_id의 첫 15개의 문자를 제외한 나머지 문자들을 모두 제거합니다. 만약 제거 후 마침표(.)가 new_id의 끝에 위치한다면 끝에 위치한 마침표(.) 문자를 제거합니다. 7단계 new_id의 길이가 2자 이하라면, new_id의 마지막 문자를 new_id의 길이가 3이 될 때까지 반복해서 끝에 붙입니다.

예를 들어, new_id 값이 "...!@BaT#*..y.abcdefghijklm" 라면, 위 7단계를 거치고 나면 new_id는 아래와 같이 변경됩니다.

1단계 대문자 'B'와 'T'가 소문자 'b'와 't'로 바뀌었습니다."...!@BaT#*..y.abcdefghijklm" → "...!@bat#*..y.abcdefghijklm"

2단계 '!', '@', '#', '*' 문자가 제거되었습니다."...!@bat#*..y.abcdefghijklm" → "...bat..y.abcdefghijklm"

3단계 '...'와 '..' 가 '.'로 바뀌었습니다."...bat..y.abcdefghijklm" → ".bat.y.abcdefghijklm"

4단계 아이디의 처음에 위치한 '.'가 제거되었습니다.".bat.y.abcdefghijklm" → "bat.y.abcdefghijklm"

5단계 아이디가 빈 문자열이 아니므로 변화가 없습니다."bat.y.abcdefghijklm" → "bat.y.abcdefghijklm"

6단계 아이디의 길이가 16자 이상이므로, 처음 15자를 제외한 나머지 문자들이 제거되었습니다."bat.y.abcdefghijklm" → "bat.y.abcdefghi"

7단계 아이디의 길이가 2자 이하가 아니므로 변화가 없습니다."bat.y.abcdefghi" → "bat.y.abcdefghi"

따라서 신규 유저가 입력한 new_id가 "...!@BaT#*..y.abcdefghijklm"일 때, 네오의 프로그램이 추천하는 새로운 아이디는 "bat.y.abcdefghi" 입니다.

[문제]

신규 유저가 입력한 아이디를 나타내는 new_id가 매개변수로 주어질 때, "네오"가 설계한 7단계의 처리 과정을 거친 후의 추천 아이디를 return 하도록 solution 함수를 완성해 주세요.

[제한사항]

new_id는 길이 1 이상 1,000 이하인 문자열입니다.new_id는 알파벳 대문자, 알파벳 소문자, 숫자, 특수문자로 구성되어 있습니다.new_id에 나타날 수 있는 특수문자는 -_.~!@#$%^&*()=+[{]}:?,<>/ 로 한정됩니다.

코드

def solution(new_id):
    answer = ''
    new_id = new_id.lower()
    for n in new_id:
        
        if (ord(n) >= 97 and ord(n) <= 122) or (ord(n) >= 48 and ord(n) <= 57) or n == '-' or n == '_' or n == '.':
            answer += n

    while '..' in answer:
        index = answer.find('..')
        if index != -1:
            answer = answer[:index] + answer[index+1:]
    if answer[0] == '.' :
        answer = answer[1:]
    if len(answer) == 0 :
        answer = 'a'
    if answer[-1] == '.' :
        answer = answer[:-1]
    if len(answer) >= 16:
        answer = answer[:15]
    if answer[-1] == '.' :
        answer = answer[:-1]
    if len(answer) <= 2:
        while len(answer) < 3:
            answer += answer[-1]
        
        
    return answer

print(solution("=.="))

후기

그냥 단순 구현이였는데 생각보다 사소한 함정이 많아서 시간을 단축하려면 처음부터 잘 이해해야 했다.

알고리즘

• 단순 구현

문제 설명

[본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]

"스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든 방이 비어 있으며 "스카피"는 다음과 같은 규칙에 따라 고객에게 방을 배정하려고 합니다.

1. 한 번에 한 명씩 신청한 순서대로 방을 배정합니다.
2. 고객은 투숙하기 원하는 방 번호를 제출합니다.
3. 고객이 원하는 방이 비어 있다면 즉시 배정합니다.
4. 고객이 원하는 방이 이미 배정되어 있으면 원하는 방보다 번호가 크면서 비어있는 방 중 가장 번호가 작은 방을 배정합니다.

예를 들어, 방이 총 10개이고, 고객들이 원하는 방 번호가 순서대로 [1, 3, 4, 1, 3, 1] 일 경우 다음과 같이 방을 배정받게 됩니다.

전체 방 개수 k와 고객들이 원하는 방 번호가 순서대로 들어있는 배열 room_number가 매개변수로 주어질 때, 각 고객에게 배정되는 방 번호를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• k는 1 이상 10 이하인 자연수입니다.
• 12
• room_number 배열의 크기는 1 이상 200,000 이하입니다.
• room_number 배열 각 원소들의 값은 1 이상 k 이하인 자연수입니다.
• room_number 배열은 모든 고객이 방을 배정받을 수 있는 경우만 입력으로 주어집니다.
  • 예를 들어, k = 5, room_number = [5, 5] 와 같은 경우는 방을 배정받지 못하는 고객이 발생하므로 이런 경우는 입력으로 주어지지 않습니다.

코드

import heapq
import sys
sys.setrecursionlimit(10000)

#빈 방 찾기
def findParent(x, parents):
    if x not in parents.keys(): # 방이 비었을 때 그 방의 부모를 다음방으로 한다.
        parents[x] = x + 1
        return x
    
    p = findParent(parents[x], parents)
    parents[x] = p + 1
    return p

def solution(k, room_number):
    answer = []
    parents = {}
    for n in room_number:
        x = findParent(n, parents)
        answer.append(x)
    return answer

print(solution(10, [1,3,4,1,3,1]))

후기

처음에 parents를 딕셔너리가 아닌 리스트로 했는데 답은 다 맞는데 자꾸 런타임 에러가 떴다. 이유를 보니 k의 값이 너무 크면 그만큼의 리스트를 만드는데 시간이 오래 걸리고 메모리가 부족 할 수 있기 때문이라고한다. 따라서 딕셔너리를 통해 사용하는 방에 대한 정보만 갖고 있어야 하는 게 중요한 것 같다. 그리고 sys.setrecursionlimit으로 재귀 깊이를 늘려야 런타임 에러가 안난다고 한다.

알고리즘

• Union & Find

시간 복잡도

• O(NlogN)