손가락놀이터

먼저 어떤 문제가 나왔고 어떤 알고리즘을 사용했는지는 시험전에 서약을 통해서 공개할 수 없음을 말씀드립니다!

코테준비

이전에도 코딩테스트를 몇 번 봤고 재미로 꾸준하게 문제를 풀긴했지만 이번 시험준비는 작정하고 문제만 계속 풀었습니다. 물론 시험을 위한 것이지만 많은 재미가 있더라고요.ㅋㅋㅋㅋ

공부를 한 방식은 부스트캠프 시험이 프로그래머스를 통해서 본다고해서 프로그래머스 문제 위주로 풀었습니다. 설명회에서 일반 기업의 코딩테스트 난이도라고 하셨고 2레벨 수준이면 다 풀 수 있겠다고 생각했습니다.

결론적으로는 2레벨 수준으로 생각한 것은 대단한 착각이었지요...😅

코딩테스트 준비를 하면서 동시에 블로그도 시작했습니다!

단순하게 문제만 풀다가 다시 그 문제를 보니 까먹은 경우가 많더라고요. 잊지 않기 위해서 다음과 같은 규칙을 스스로 정하고 공부를 시작했습니다

1. 스스로 문제 풀어보기 (단, 알고리즘 구현으로 1시간이 넘어간 경우. 전체 코드 구현까지 3시간이 넘어간 경우에는 모르는것으로 생각하고 찾아보기)
2. 문제의 알고리즘을 전체적으로 다시 확인해보기(모르는 문제의 경우 해답을 알고 난 이후 다시 풀기)
3. 코드에 주석처리를 통해 어디서 어떤 코드가 왜 쓰였는지 작성하기
4. 마지막으로 블로그에 문제후기를 등록하여 어떤 방식으로 문제를 해결해나갔는지 작성

위와 같은 규칙을 지키기 힘들면서도 하나씩 해내가는게 재밌었습니다😁😁😁

공부한 알고리즘을 정리해보면 이정도입니다.

차후에 블로그에 알고리즘에 대한 설명도 작성해야겠네요. 점점 할 일이 많아지는 기분ㅋㅋㅋㅋ

• 완전탐색
• 이분탐색
• heap 정렬
• 그래프
• DFS, BFS
• DP
• 그리디, 다익스트라, 크루스칼
• 조합, 순열

코테후기

공부를 하면서 자만하던 저를 반성하고 다시 공부하게 만드는 시험이었습니다.....😅

막상 시험을 시작하니 많은 것들이 기억이 안나고 당황을 하더라고요. 전체적인 느낌은 정말 전형적인 기업 코딩테스트였던거 같아요. 교육이어서 쉽다는 생각을 하다가 멘탈이...ㅋㅋㅋ

그래도 다행히 정신차리고 풀긴 풀었네요

자만하지말고 더 열심히 공부를 시작하자!!

결과

결과는 다행히 합격입니다..... 정말 마지막 순간까지 긴장했어요ㅠㅠ 긴장하는 기분이 좋은 기분은 아니네요

그래도 11월 중순부터 시작해서 목표를 설정하고 혼자서 공부한 것에 대한 결과가 잘 나와서 너무너무 만족합니다!!

앞으로 진행되는 6개월동안 정말 영혼을 갈아서 넣으려고해요ㅋㅋㅋㅋ

같이 교육을 진행하는 모든 분들이 좋은 결과를 얻기를 바라겠습니다!!

문제 후기

1. 처음에는 단순하게 진입 지점과 진출 시점을 기준으로 카메라를 설치하려했습니다. 해당 방법으로 했더니 정답 자체가 아니어서 알고리즘이 틀린 것으로 알게 됐다.

2. 2번째로는 나가는 시점을 기준으로 카메라를 설치했다. 메모이제이션을 통해 미리 최대 길이(60,000)만큼 배열을 만들고 나가는 지점에 카메라를 기록하는 방식으로 했다. 정확성에서는 통과했지만 효율성에서 케이스 한 개가 안됐다.

3. 3번째로 새로운 카메라가 추가된 경우 미리 나머지 차량을 확인하는 방식을 선택했다. 해당 알고리즘으로 했을 때 효율성 또한 만족하는 것으로 나왔다.

문제 설명

고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다.

고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요.

제한사항

• 차량의 대수는 1대 이상 10,000대 이하입니다.
• routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적혀 있습니다.
• 차량의 진입/진출 지점에 카메라가 설치되어 있어도 카메라를 만난것으로 간주합니다.
• 차량의 진입 지점, 진출 지점은 -30,000 이상 30,000 이하입니다.

입출력 예

입출력 예 설명

-5 지점에 카메라를 설치하면 두 번째, 네 번째 차량이 카메라를 만납니다.

-15 지점에 카메라를 설치하면 첫 번째, 세 번째 차량이 카메라를 만납니다.

def solution(routes):
    
    chk_camera = [0] * len(routes)      # 총 확인해야하는 차량 수
    count = 0   # 결과값
    routes.sort(key=lambda x:x[1])      # 진출 지점으로 정렬

    for car in range(len(routes)):
        # 만약 해당 차량이 카메라 테스트에서 통과한 경우 패스
        if chk_camera[car]:
            continue
        # 해당 차량이 지나가는 카메라가 없으므로 새로 만듬.
        camera = routes[car][1]
        count +=1
        
        # 새로 만든 카메라가 이후 차량 중에서 지나가는 차량이 있는지 확인
        for num in range(car + 1, len(routes)):
            if routes[num][0] <= camera <= routes[num][1]:
                chk_camera[num] = True

    return count

문제 후기

해당 문제를 보고 닉네임과 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

문제 후기

문제를 보고 가장 먼저 고민한 것은 15(1111)과 30(11110)과 같이 다음 오는 숫자가 자릿수가 증가하는 경우였습니다.

다른 것은 어떻게 하면 쉽게 숫자를 넘겨줄 수 있을까라는 생각을 했고 Queue와 배열을 고민하다 문제를 풀면서 queue의 의미가 없다고 생각하여 배열을 사용했습니다. 

해결 방식은 위에서부터 1인경우 pass하고 0이 나왔다면 0과 1의 자리를 바꾸고 뒤는 가장 작은 수를 배치하는 것입니다.

1001110 에서 1001110 -> 1010110로 바꾸고 뒤의 110은 가장 작은 수로 변경해야하므로 0의 갯수만큼 먼저 합치고, 그 이후 1을 합쳐서 1010011이 되는 방식입니다.

문제 설명

자연수 n이 주어졌을 때, n의 다음 큰 숫자는 다음과 같이 정의 합니다.

• 조건 1. n의 다음 큰 숫자는 n보다 큰 자연수 입니다.
• 조건 2. n의 다음 큰 숫자와 n은 2진수로 변환했을 때 1의 갯수가 같습니다.
• 조건 3. n의 다음 큰 숫자는 조건 1, 2를 만족하는 수 중 가장 작은 수 입니다.

예를 들어서 78(1001110)의 다음 큰 숫자는 83(1010011)입니다.

자연수 n이 매개변수로 주어질 때, n의 다음 큰 숫자를 return 하는 solution 함수를 완성해주세요.

Python 코드

def solution(n):
    arr = [] # n을 2진수로 변환
    res = [] # n 다음 숫자의 2진수

    # n 숫자를 2진수로 변환
    while n >= 2:
        if n % 2 == 0:
            arr.append(0)
        else:
            arr.append(1)
        n = n // 2
    arr.append(1)



    tmp = [] # 임의의 배열
    zero, one = 0,0 #
    val = 1 #
    result = 0 # 결과값.

    # n의 2진수로부터 시작
    for idx in range(len(arr)-1):
        k = arr[idx]

        # 만약 해당 값이 1이고 그 다음 값이 0인 경우 서로 변경.
        if k == 1 and arr[idx+1] == 0:
            # zero와 one을 이용하여 바꾼 부분 뒤를 가장 작은 수로 만듬.
            for i in range(one):
                res.append(1)
            for j in range(zero):
                res.append(0)

            res.append(arr[idx+1]) # 1과 0을 서로 변경.
            res.append(1)

            # 나머지 부분을 합침.
            res.extend(arr[idx+2:])

            # 2진수 -> 10진수
            for x in res:
                result += val * x
                val *= 2
            return result

        # 바꾸기 전의 1의 갯수
        elif k == 1:
            one += 1

        # 바꾸기 전의 0의 갯수
        elif k == 0:
           zero += 1

    # 만약 위에서 return이 안된 경우, 더이상 바꾸는 것으로 증가 안되는 경우
    for j in range(one):
        tmp.append(1)
    for i in range(zero):
        tmp.append(0)

    # 2번째에 0을 추가하여 1의 갯수도 같으면서 다음 큰 수
    tmp.append(0)
    tmp.append(1)

    for x in tmp:
        result += val * x
        val *= 2
    return result