손가락놀이터

문제 후기

이전에는 중복을 없애는 것은 단순하게 dictionary를 사용해서 hash만 생각했었다. 해당 문제를 풀면서 집합의 개념을 다시 한번 확인했고 부분집합(issubset)의 활용하는 것을 알게 됐습니다.

문제 설명

후보키

프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.

그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.

후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.

• 관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집합 중, 다음 두 성질을 만족하는 것을 후보 키(Candidate Key)라고 한다.
  • 유일성(uniqueness) : 릴레이션에 있는 모든 튜플에 대해 유일하게 식별되어야 한다.
  • 최소성(minimality) : 유일성을 가진 키를 구성하는 속성(Attribute) 중 하나라도 제외하는 경우 유일성이 깨지는 것을 의미한다. 즉, 릴레이션의 모든 튜플을 유일하게 식별하는 데 꼭 필요한 속성들로만 구성되어야 한다.

제이지를 위해, 아래와 같은 학생들의 인적사항이 주어졌을 때, 후보 키의 최대 개수를 구하라.

위의 예를 설명하면, 학생의 인적사항 릴레이션에서 모든 학생은 각자 유일한 학번을 가지고 있다. 따라서 학번은 릴레이션의 후보 키가 될 수 있다.
그다음 이름에 대해서는 같은 이름(apeach)을 사용하는 학생이 있기 때문에, 이름은 후보 키가 될 수 없다. 그러나, 만약 [이름, 전공]을 함께 사용한다면 릴레이션의 모든 튜플을 유일하게 식별 가능하므로 후보 키가 될 수 있게 된다.
물론 [이름, 전공, 학년]을 함께 사용해도 릴레이션의 모든 튜플을 유일하게 식별할 수 있지만, 최소성을 만족하지 못하기 때문에 후보 키가 될 수 없다.
따라서, 위의 학생 인적사항의 후보키는 학번, [이름, 전공] 두 개가 된다.

릴레이션을 나타내는 문자열 배열 relation이 매개변수로 주어질 때, 이 릴레이션에서 후보 키의 개수를 return 하도록 solution 함수를 완성하라.

제한사항

• relation은 2차원 문자열 배열이다.
• relation의 컬럼(column)의 길이는 1 이상 8 이하이며, 각각의 컬럼은 릴레이션의 속성을 나타낸다.
• relation의 로우(row)의 길이는 1 이상 20 이하이며, 각각의 로우는 릴레이션의 튜플을 나타낸다.
• relation의 모든 문자열의 길이는 1 이상 8 이하이며, 알파벳 소문자와 숫자로만 이루어져 있다.
• relation의 모든 튜플은 유일하게 식별 가능하다.(즉, 중복되는 튜플은 없다.)

입출력 예

입출력 예 설명

입출력 예 #1
문제에 주어진 릴레이션과 같으며, 후보 키는 2개이다.

# 순열 구현
def perm(lst, n):
    arr = []
    if n > len(lst):
        return arr

    if n == 1:
        for i in lst:
            arr.append([i])
    else:
        for i in range(len(lst)):
            temp = [val for val in lst]
            temp.remove(lst[i])
            for p in perm(temp, n-1):
                arr.append([lst[i]]+p)
    return arr
# 조합 구현
def comb(lst, n):
    arr = []

    if n > len(lst):
        return arr

    if n == 1:
        for i in lst:
            arr.append([i])

    else:
        for i in range(len(lst)-n+1):
            for temp in comb(lst[i+1:], n-1):
                arr.append([lst[i]] + temp)
    return arr


def solution(relation):
    # 행, 열 정의
    row, col = len(relation), len(relation[0])

    col_arr = [num for num in range(col)]

    candidate_key = []  # 후보키 가능 리스트, 유일성 만족
    key_list = []       # 키 리스트
    result_key = []     # 결과값

    # 조합으로 가능한 키 리스트 추출.
    for num in range(1, col+1):
        key_list.extend(comb(col_arr, num))

    # 키 리스트로 후보키 유일성 체크
    for key_col in key_list:
        check_key = []
        
        # 키가 후보키인지 확인
        for rel in range(row):
            data = ""
            for num in key_col:
                data += relation[rel][num]
            if data not in check_key:
                check_key.append(data)
            else:
                break
                
        # 키가 유일성을 만족.
        if len(check_key) == row:
            # 집합 형태로 추가.
            candidate_key.append(set(key_col))

    # 최소성확인
    for key in candidate_key:
        tmp = True
        if not result_key:
            result_key.append(key)
        else:
            for chk in result_key:
                # 부분집합으로 존재하면 최소성 만족 x
                if chk.issubset(key):
                    tmp = False
                    break
            if tmp:
                result_key.append(key)
    # 최종 후보키 출력
    return len(result_key)

문제 후기

해당 문제를 보고 닉네임과 uid의 관계를 정립하는 것이 중요하다 생각하여 dictionary를 활용했습니다. 이후는 record의 순서대로 입장과 퇴장을 출력하면 됩니다.

문제 설명

오픈채팅방

카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다.

신입사원인 김크루는 카카오톡 오픈 채팅방을 개설한 사람을 위해, 다양한 사람들이 들어오고, 나가는 것을 지켜볼 수 있는 관리자창을 만들기로 했다. 채팅방에 누군가 들어오면 다음 메시지가 출력된다.

[닉네임]님이 들어왔습니다.

채팅방에서 누군가 나가면 다음 메시지가 출력된다.

[닉네임]님이 나갔습니다.

채팅방에서 닉네임을 변경하는 방법은 다음과 같이 두 가지이다.

• 채팅방을 나간 후, 새로운 닉네임으로 다시 들어간다.
• 채팅방에서 닉네임을 변경한다.

닉네임을 변경할 때는 기존에 채팅방에 출력되어 있던 메시지의 닉네임도 전부 변경된다.

예를 들어, 채팅방에 Muzi와 Prodo라는 닉네임을 사용하는 사람이 순서대로 들어오면 채팅방에는 다음과 같이 메시지가 출력된다.

Muzi님이 들어왔습니다.
Prodo님이 들어왔습니다.

채팅방에 있던 사람이 나가면 채팅방에는 다음과 같이 메시지가 남는다.

Muzi님이 들어왔습니다.
Prodo님이 들어왔습니다.
Muzi님이 나갔습니다.

Muzi가 나간후 다시 들어올 때, Prodo 라는 닉네임으로 들어올 경우 기존에 채팅방에 남아있던 Muzi도 Prodo로 다음과 같이 변경된다.

Prodo님이 들어왔습니다.
Prodo님이 들어왔습니다.
Prodo님이 나갔습니다.
Prodo님이 들어왔습니다.

채팅방은 중복 닉네임을 허용하기 때문에, 현재 채팅방에는 Prodo라는 닉네임을 사용하는 사람이 두 명이 있다. 이제, 채팅방에 두 번째로 들어왔던 Prodo가 Ryan으로 닉네임을 변경하면 채팅방 메시지는 다음과 같이 변경된다.

Prodo님이 들어왔습니다.
Ryan님이 들어왔습니다.
Prodo님이 나갔습니다.
Prodo님이 들어왔습니다.

채팅방에 들어오고 나가거나, 닉네임을 변경한 기록이 담긴 문자열 배열 record가 매개변수로 주어질 때, 모든 기록이 처리된 후, 최종적으로 방을 개설한 사람이 보게 되는 메시지를 문자열 배열 형태로 return 하도록 solution 함수를 완성하라.

제한사항

• record는 다음과 같은 문자열이 담긴 배열이며, 길이는 1 이상 100,000 이하이다.
• 다음은 record에 담긴 문자열에 대한 설명이다.
  • 모든 유저는 [유저 아이디]로 구분한다.
  • [유저 아이디] 사용자가 [닉네임]으로 채팅방에 입장 - Enter [유저 아이디] [닉네임] (ex. Enter uid1234 Muzi)
  • [유저 아이디] 사용자가 채팅방에서 퇴장 - Leave [유저 아이디] (ex. Leave uid1234)
  • [유저 아이디] 사용자가 닉네임을 [닉네임]으로 변경 - Change [유저 아이디] [닉네임] (ex. Change uid1234 Muzi)
  • 첫 단어는 Enter, Leave, Change 중 하나이다.
  • 각 단어는 공백으로 구분되어 있으며, 알파벳 대문자, 소문자, 숫자로만 이루어져있다.
  • 유저 아이디와 닉네임은 알파벳 대문자, 소문자를 구별한다.
  • 유저 아이디와 닉네임의 길이는 1 이상 10 이하이다.
  • 채팅방에서 나간 유저가 닉네임을 변경하는 등 잘못 된 입력은 주어지지 않는다.

입출력 예

입출력 예 설명

입출력 예 #1
문제의 설명과 같다.

def solution(record):

    queue = record.copy()  # record를 queue로 복사
    user = {}       # User uid, 닉네임 저장
    result = []     # 결과값
    chk = []        # 행동과 uid 저장 
    idx = 0         # queue 인텍스 값
    
    # 모든 값 탐색
    while idx < len(queue):
        # 행동, uid, 닉네임을 구분
        value = list(map(str,queue[idx].split()))
        # 입장한 경우
        if value[0] == "Enter":
            # 행동, uid 저장
            chk.append([value[0],value[1]])
            # dict에 uid, 닉네임 저장
            user[value[1]] = value[2]
        # 닉네임 변경한 경우
        elif value[0] == "Change":
            # dict에 닉네임 변경
            user[value[1]] = value[2]
        # 나간 경우
        else:
            # 행동, uid 저장
            chk.append([value[0], value[1]])
        idx += 1
    # 저장한 chk를 통해 차례대로 출력        
    for num in range(len(chk)):
        if chk[num][0] == "Enter":
            result.append(user[chk[num][1]] + "님이 들어왔습니다.")
        else:
            result.append(user[chk[num][1]] + "님이 나갔습니다.")
    return result

문제 후기

해당 문제는 LRU(Least Recently Used) 알고리즘을 참고하여 푸는 방식이다. 

LRU 알고리즘이란 메모리 크기를 가지고 있고 Queue 형태로 캐시 메모리에 들어가는 것이다. 이 때 캐시 메모리 안에 있다면 해당 캐시를 삭제 후 다시 queue에 넣는 방식이다. 자세한 것은 아래의 이미지를 참고한다.

해당 문제를 풀면서 메모리가 갱신되는 것을 잊고 있어서 실수가 발생했다. 다음에도 주의해야할 것 같다.

문제 설명

캐시

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

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

입력 형식

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

출력 형식

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

조건

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

입출력 예제

from _collections import deque

def solution(cacheSize, cities):
    queue = deque([0] * cacheSize)  # 캐시 생성
    answer = 0     # 정답값
    if cacheSize == 0:  # 캐시가 0이면 전부 chache miss
        return 5 * len(cities)
    for name in cities:     # 캐시 메모리에 돌리기
        name = name.lower() # 전부 소문자로
        if name in queue:   # 만약 도시가 캐시에 있다면
            queue.remove(name)  # 캐시 최신으로 교체
            queue.append(name)
            answer += 1     # cache hit

        else:
            queue.popleft() # 가장 옛날 캐시 삭제
            queue.append(name)  # 캐시에 추가
            answer += 5     # cache miss

    return answer   # 정답 리턴

문제 후기

단순히 a와 b의 숫자를 반으로 줄여가면 된다.

문제를 풀면서 틀렸던 부분은 단순히 두 값의 절대값이 1일 때 끝나도록 했는데 (4, 5)와 같이 대진이 아니더라도 절대값이 1이 발생하는 부분이 있다는 것을 실수했다.

문제 설명

△△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N번의 참가자끼리 게임을 진행합니다. 각 게임에서 이긴 사람은 다음 라운드에 진출할 수 있습니다. 이때, 다음 라운드에 진출할 참가자의 번호는 다시 1번부터 N/2번을 차례대로 배정받습니다. 만약 1번↔2번 끼리 겨루는 게임에서 2번이 승리했다면 다음 라운드에서 1번을 부여받고, 3번↔4번에서 겨루는 게임에서 3번이 승리했다면 다음 라운드에서 2번을 부여받게 됩니다. 게임은 최종 한 명이 남을 때까지 진행됩니다.

이때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 궁금해졌습니다. 게임 참가자 수 N, 참가자 번호 A, 경쟁자 번호 B가 함수 solution의 매개변수로 주어질 때, 처음 라운드에서 A번을 가진 참가자는 경쟁자로 생각하는 B번 참가자와 몇 번째 라운드에서 만나는지 return 하는 solution 함수를 완성해 주세요. 단, A번 참가자와 B번 참가자는 서로 붙게 되기 전까지 항상 이긴다고 가정합니다.

제한사항

• N : 21 이상 220 이하인 자연수 (2의 지수 승으로 주어지므로 부전승은 발생하지 않습니다.)
• A, B : N 이하인 자연수 (단, A ≠ B 입니다.)

입출력 예

입출력 예 설명

입출력 예 #1
첫 번째 라운드에서 4번 참가자는 3번 참가자와 붙게 되고, 7번 참가자는 8번 참가자와 붙게 됩니다. 항상 이긴다고 가정했으므로 4번 참가자는 다음 라운드에서 2번이 되고, 7번 참가자는 4번이 됩니다. 두 번째 라운드에서 2번은 1번과 붙게 되고, 4번은 3번과 붙게 됩니다. 항상 이긴다고 가정했으므로 2번은 다음 라운드에서 1번이 되고, 4번은 2번이 됩니다. 세 번째 라운드에서 1번과 2번으로 두 참가자가 붙게 되므로 3을 return 하면 됩니다.

def solution(n,a,b):
    answer = 1  # 정답값

    while True:     # 리턴할 때 까지 반복
        # 두 값의 차이가 1의 차이가 날때
        # 주의) a와 b가 대진을 해야하는데 2,3 같이 1의 차이가 나도 대결 안하는 경우
        if abs(a - b) == 1 and a // 2 != b // 2:
            return answer   # 정답 리턴
        else:
            if a % 2 == 1:  # 홀수일 때
                a = (a + 1) // 2
            else:
                a = a // 2  # 짝수일 때

            if b % 2 == 1:
                b = (b + 1) // 2    # 홀수일 때
            else:
                b = b // 2      # 짝수일 때
            answer += 1     # 대진횟수

문제 후기

해당 문제는  말한 단어가 이전에 나왔는지 안나왔는지 확인과 이전 단어의 마지막 글자와 현재 단어의 첫번째 글자가 일치하는지 확인하는 것만 생각하면 되는 문제다.

Dictionary를 사용하여 단어가 나왔는지 안나왔는지 해결하였다.

문제 설명

1부터 n까지 번호가 붙어있는 n명의 사람이 영어 끝말잇기를 하고 있습니다. 영어 끝말잇기는 다음과 같은 규칙으로 진행됩니다.

1. 1번부터 번호 순서대로 한 사람씩 차례대로 단어를 말합니다.
2. 마지막 사람이 단어를 말한 다음에는 다시 1번부터 시작합니다.
3. 앞사람이 말한 단어의 마지막 문자로 시작하는 단어를 말해야 합니다.
4. 이전에 등장했던 단어는 사용할 수 없습니다.
5. 한 글자인 단어는 인정되지 않습니다.

다음은 3명이 끝말잇기를 하는 상황을 나타냅니다.

tank → kick → know → wheel → land → dream → mother → robot → tank

위 끝말잇기는 다음과 같이 진행됩니다.

• 1번 사람이 자신의 첫 번째 차례에 tank를 말합니다.
• 2번 사람이 자신의 첫 번째 차례에 kick을 말합니다.
• 3번 사람이 자신의 첫 번째 차례에 know를 말합니다.
• 1번 사람이 자신의 두 번째 차례에 wheel을 말합니다.
• (계속 진행)

끝말잇기를 계속 진행해 나가다 보면, 3번 사람이 자신의 세 번째 차례에 말한 tank 라는 단어는 이전에 등장했던 단어이므로 탈락하게 됩니다.

사람의 수 n과 사람들이 순서대로 말한 단어 words 가 매개변수로 주어질 때, 가장 먼저 탈락하는 사람의 번호와 그 사람이 자신의 몇 번째 차례에 탈락하는지를 구해서 return 하도록 solution 함수를 완성해주세요.

제한 사항

• 끝말잇기에 참여하는 사람의 수 n은 2 이상 10 이하의 자연수입니다.
• words는 끝말잇기에 사용한 단어들이 순서대로 들어있는 배열이며, 길이는 n 이상 100 이하입니다.
• 단어의 길이는 2 이상 50 이하입니다.
• 모든 단어는 알파벳 소문자로만 이루어져 있습니다.
• 끝말잇기에 사용되는 단어의 뜻(의미)은 신경 쓰지 않으셔도 됩니다.
• 정답은 [ 번호, 차례 ] 형태로 return 해주세요.
• 만약 주어진 단어들로 탈락자가 생기지 않는다면, [0, 0]을 return 해주세요.

입출력 예

입출력 예 설명

입출력 예 #1
3명의 사람이 끝말잇기에 참여하고 있습니다.

• 1번 사람 : tank, wheel, mother
• 2번 사람 : kick, land, robot
• 3번 사람 : know, dream, tank

와 같은 순서로 말을 하게 되며, 3번 사람이 자신의 세 번째 차례에 말한 tank라는 단어가 1번 사람이 자신의 첫 번째 차례에 말한 tank와 같으므로 3번 사람이 자신의 세 번째 차례로 말을 할 때 처음 탈락자가 나오게 됩니다.

입출력 예 #2
5명의 사람이 끝말잇기에 참여하고 있습니다.

• 1번 사람 : hello, recognize, gather
• 2번 사람 : observe, encourage, refer
• 3번 사람 : effect, ensure, reference
• 4번 사람 : take, establish, estimate
• 5번 사람 : either, hang, executive

와 같은 순서로 말을 하게 되며, 이 경우는 주어진 단어로만으로는 탈락자가 발생하지 않습니다. 따라서 [0, 0]을 return하면 됩니다.

입출력 예 #3
2명의 사람이 끝말잇기에 참여하고 있습니다.

• 1번 사람 : hello, even, now, draw
• 2번 사람 : one, never, world

와 같은 순서로 말을 하게 되며, 1번 사람이 자신의 세 번째 차례에 'r'로 시작하는 단어 대신, n으로 시작하는 now를 말했기 때문에 이때 처음 탈락자가 나오게 됩니다.

def solution(n, words):

    word_dict = {}  # 이전에 나온 단어인지 확인용 dictionary
    idx = 0         # 번호 순서 확인 변수
    count = 1       # 사람이 몇 번째 단어가 틀렸는지 확인 변수
    last_word = words[0][0] # 처음 시작 단어 첫 글자

    while True:

        if idx == len(words):   # 만약 모든 단어를 진행했다면 틀린 사람 없음
            return [0,0]
        if words[idx] not in word_dict and words[idx][0] == last_word:  # 단어가 이전에 안나왔고 앞 단어의 마지막 글자와 일치
            word_dict[words[idx]] = 1   # dictionary에 추가
            last_word = words[idx][-1]  # 마지막 글자 저장
            idx += 1

            if idx % n == 0:    # 만약 n번째 사람이 대답 했다면 단어 + 1
                count += 1
        else:
            if (idx+1) % n:     # 만약 n번째가 아니면 n으로 나눈 나머지 번째 사람
                return [(idx+1) % n, count]
            else:               # n 번째 사람.
                return [n, count]

문제 후기

특정 알고리즘을 사용하기보다 2의 제곱을 사용한다는 것을 빨리 파악하면 되는 문제 같습니다. 2의 제곱 중 가장 큰 수 빼주고 또 남은 수에서 2의 제곱 중 가장 큰 수 빼주고... 반복으로 진행됩니다.

문제 설명

OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈트는 건전지로 작동되는데, 순간이동을 하면 건전지 사용량이 줄지 않지만, 앞으로 K 칸을 점프하면 K 만큼의 건전지 사용량이 듭니다. 그러므로 아이언 슈트를 착용하고 이동할 때는 순간 이동을 하는 것이 더 효율적입니다. 아이언 슈트 구매자는 아이언 슈트를 착용하고 거리가 N 만큼 떨어져 있는 장소로 가려고 합니다. 단, 건전지 사용량을 줄이기 위해 점프로 이동하는 것은 최소로 하려고 합니다. 아이언 슈트 구매자가 이동하려는 거리 N이 주어졌을 때, 사용해야 하는 건전지 사용량의 최솟값을 return하는 solution 함수를 만들어 주세요.

예를 들어 거리가 5만큼 떨어져 있는 장소로 가려고 합니다.
아이언 슈트를 입고 거리가 5만큼 떨어져 있는 장소로 갈 수 있는 경우의 수는 여러 가지입니다.

• 처음 위치 0 에서 5 칸을 앞으로 점프하면 바로 도착하지만, 건전지 사용량이 5 만큼 듭니다.
• 처음 위치 0 에서 2 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 2) x 2에 해당하는 위치로 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 3 만큼 듭니다.
• 처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동됩니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 2) x 2 만큼 이동할 수 있으므로 위치 4로 이동합니다. 이때 1 칸을 앞으로 점프하면 도착하므로 건전지 사용량이 2 만큼 듭니다.

위의 3가지 경우 거리가 5만큼 떨어져 있는 장소로 가기 위해서 3번째 경우가 건전지 사용량이 가장 적으므로 답은 2가 됩니다.

제한 사항

• 숫자 N: 1 이상 10억 이하의 자연수
• 숫자 K: 1 이상의 자연수

입출력 예

입출력 예 설명

입출력 예 #1
위의 예시와 같습니다.

입출력 예 #2
처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동합니다. 이때 1 칸을 앞으로 점프하면 위치3으로 이동합니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 3) x 2 이동할 수 있으므로 위치 6에 도착합니다. 이 경우가 건전지 사용량이 가장 적으므로 2를 반환해주면 됩니다.

입출력 예 #3
위와 같은 방식으로 합니다.

def solution(n):
    ans = 0     # 결과값

    while n > 0:    # n이 0이 될 때까지
        calculation = 1     # 2의 제곱으로 계산하는 수
        while n >= calculation:     # n보다 작은 2의 제곱
            tmp = calculation       # 가장 큰 2의 제곱 값 저장하기
            calculation = calculation * 2   # 2의 제곱

        n -= tmp    # n보다 작은 가장 큰 2의 제곱 빼주기
        ans += 1    # 결과값 + 1

    return ans      # 결과값 리턴

문제 후기

처음 보자마자 조합과 소수 구하기를 적용해야 풀어야 한다고 생각했습니다. 조합의 경우 itertools의 combination보다 코드로 구현하는 것이 더 빨라 코드로 구현하였습니다.

소수 구하기 경우 에라토스테네스의 체를 이용하여 시간을 단축시켰습니다.

문제 설명

주어진 숫자 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 구하려고 합니다. 숫자들이 들어있는 배열 nums가 매개변수로 주어질 때, nums에 있는 숫자들 중 서로 다른 3개를 골라 더했을 때 소수가 되는 경우의 개수를 return 하도록 solution 함수를 완성해주세요.

제한사항

• nums에 들어있는 숫자의 개수는 3개 이상 50개 이하입니다.
• nums의 각 원소는 1 이상 1,000 이하의 자연수이며, 중복된 숫자가 들어있지 않습니다.

입출력 예

from math import sqrt

def solution(nums):
    answer = 0  # 정답값

    for one in range(len(nums)-2):  # 첫번째 숫자
        for two in range(one+1, len(nums)-1):   # 두번째 숫자
            for three in range(two + 1, len(nums)): # 세번째 숫자
                chk_num = nums[one] + nums[two] + nums[three]   # 숫자의 합
                prime = True    # 소수 판별

                if chk_num % 2 == 0 or chk_num % 3 == 0 or chk_num % 5 == 0:    # 2,3 5의 배수인 경우 패스
                    prime = False
                else:
                    # 에라토스테네스의 체 적용
                    for factor in range(2, int(sqrt(chk_num)))+1:
                        if chk_num % factor == 0:
                            prime = False
                            break
                        else:
                            pass
                if prime:
                    # 소수인 경우 정답 + 1
                    answer += 1

    return answer

문제 후기

이전 2020 카카오 여름인턴에서 2번문제로 나왔던 문제입니다. 그 때 당시에도 풀긴 풀었지만 꽤 오랜 시간이 걸렸었는데 다시 풀어보니 이전보다 빨리 풀기는 했습니다. 이전에는 연산자의 경우도 코드로 했지만 경우의 수가 6개만 나와서 전부 입력했습니다.

해당 문제는 수식을 어떻게 하면 잘 구분하는지, 문자열 사용을 잘하면 되는 것 같습니다. 앞에서부터 하는 수식이다보니 Queue를 활용하여 풀었습니다.

문제 설명

IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다.
이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 같은 방식으로 결정하려고 합니다.
해커톤 대회에 참가하는 모든 참가자들에게는 숫자들과 3가지의 연산문자(+, -, *) 만으로 이루어진 연산 수식이 전달되며, 참가자의 미션은 전달받은 수식에 포함된 연산자의 우선순위를 자유롭게 재정의하여 만들 수 있는 가장 큰 숫자를 제출하는 것입니다.
단, 연산자의 우선순위를 새로 정의할 때, 같은 순위의 연산자는 없어야 합니다. 즉, + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,-처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다. 수식에 포함된 연산자가 2개라면 정의할 수 있는 연산자 우선순위 조합은 2! = 2가지이며, 연산자가 3개라면 3! = 6가지 조합이 가능합니다.
만약 계산된 결과가 음수라면 해당 숫자의 절댓값으로 변환하여 제출하며 제출한 숫자가 가장 큰 참가자를 우승자로 선정하며, 우승자가 제출한 숫자를 우승상금으로 지급하게 됩니다.

예를 들어, 참가자 중 네오가 아래와 같은 수식을 전달받았다고 가정합니다.

"100-200*300-500+20"

일반적으로 수학 및 전산학에서 약속된 연산자 우선순위에 따르면 더하기와 빼기는 서로 동등하며 곱하기는 더하기, 빼기에 비해 우선순위가 높아 * > +,- 로 우선순위가 정의되어 있습니다.
대회 규칙에 따라 + > - > * 또는 - > * > + 등과 같이 연산자 우선순위를 정의할 수 있으나 +,* > - 또는 * > +,- 처럼 2개 이상의 연산자가 동일한 순위를 가지도록 연산자 우선순위를 정의할 수는 없습니다.
수식에 연산자가 3개 주어졌으므로 가능한 연산자 우선순위 조합은 3! = 6가지이며, 그 중 + > - > * 로 연산자 우선순위를 정한다면 결괏값은 22,000원이 됩니다.
반면에 * > + > - 로 연산자 우선순위를 정한다면 수식의 결괏값은 -60,420 이지만, 규칙에 따라 우승 시 상금은 절댓값인 60,420원이 됩니다.

참가자에게 주어진 연산 수식이 담긴 문자열 expression이 매개변수로 주어질 때, 우승 시 받을 수 있는 가장 큰 상금 금액을 return 하도록 solution 함수를 완성해주세요.

[제한사항]

• expression은 길이가 3 이상 100 이하인 문자열입니다.
• expression은 공백문자, 괄호문자 없이 오로지 숫자와 3가지의 연산자(+, -, *) 만으로 이루어진 올바른 중위표기법(연산의 두 대상 사이에 연산기호를 사용하는 방식)으로 표현된 연산식입니다. 잘못된 연산식은 입력으로 주어지지 않습니다.
  • 즉, "402+-561*"처럼 잘못된 수식은 올바른 중위표기법이 아니므로 주어지지 않습니다.
• expression의 피연산자(operand)는 0 이상 999 이하의 숫자입니다.
  • 즉, "100-2145*458+12"처럼 999를 초과하는 피연산자가 포함된 수식은 입력으로 주어지지 않습니다.
  • "-56+100"처럼 피연산자가 음수인 수식도 입력으로 주어지지 않습니다.
• expression은 적어도 1개 이상의 연산자를 포함하고 있습니다.
• 연산자 우선순위를 어떻게 적용하더라도, expression의 중간 계산값과 최종 결괏값은 절댓값이 263 - 1 이하가 되도록 입력이 주어집니다.
• 같은 연산자끼리는 앞에 있는 것의 우선순위가 더 높습니다.

입출력 예

입출력 예에 대한 설명

입출력 예 #1
* > + > - 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.
100-200*300-500+20
= 100-(200*300)-500+20
= 100-60000-(500+20)
= (100-60000)-520
= (-59900-520)
= -60420
따라서, 우승 시 받을 수 있는 상금은 |-60420| = 60420 입니다.

입출력 예 #2
- > * 로 연산자 우선순위를 정했을 때, 가장 큰 절댓값을 얻을 수 있습니다.
연산 순서는 아래와 같습니다.(expression에서 + 연산자는 나타나지 않았으므로, 고려할 필요가 없습니다.)
50*6-3*2
= 50*(6-3)*2
= (50*3)*2
= 150*2
= 300
따라서, 우승 시 받을 수 있는 상금은 300 입니다.

from _collections import deque

def solution(expression):
    # 6개의 연산자 우선순위
    priority = [['+','-','*'],['+','*','-'],['-','+','*'],['-','*','+'],['*','-','+'],['*','+','-']]
    answer = 0      # 리턴하는 결과값
    
    arr = []     # 수식을 저장하는 베열.
    num = ''    # 숫자를 판별.
    
    # 문자열인 수식을 배열에 저장
    for ch in expression:
        if ch.isnumeric():
            num += ch
        else:
            # 문자인 경우 숫자를 배열에 저장하고 연산자도 저장
            arr.append(int(num))
            num = ''
            arr.append(ch)
    # 마지막 숫자 베열에 저장
    arr.append(int(num))

    # 우선순위에 따라서 총 6번 계산.
    for formular in priority:
        queue = deque(arr)  # 배열을 Queue에 삽입.
        
        # 연산자 우선순위로 계산
        for operator in formular:
            # 해당 연산자 계산한 이후 수식.
            calculate = deque([])
            # Queue에 값이 없을때 까지
            while queue:
                chk = queue.popleft()   # Queue에 값을 하나씩 pop.

                if chk == operator:     # 만약 연산자일때 연산자마다 계산
                    if chk == '+':

                        num1 = calculate.pop()  # 연산자 이전 숫자
                        num2 = queue.popleft()  # 연산자 다음 숫자
                        calculate.append(num1+num2) # 연산자 계산
                    elif chk == '-':
                        num1 = calculate.pop()  # 연산자 이전 숫자
                        num2 = queue.popleft()  # 연산자 다음 숫자
                        calculate.append(num1 - num2)   # 연산자 계산
                    else:
                        num1 = calculate.pop()  # 연산자 이전 숫자
                        num2 = queue.popleft()  # 연산자 다음 숫자
                        calculate.append(num1 * num2)   # 연산자 계산
                else:
                    calculate.append(chk)   # 숫자인 경우 저장

            queue = calculate.copy()    # 완료된 수식을 다시 Queue에 저장하여 계산

        result_num = queue.pop()    # 수식 최종값
        answer = max(answer, abs(result_num))    # 수식값의 절대값이 크다면 결과값 수정


    return answer   # 결과값 출력