프로젝트 만들기

먼저 File - > new -> project로 들어가 빈 프로젝트를 만들어 봅시다.

Single view app을 선택해주시고 프로젝트 이름을 지어주세요! 연습용이니 CustomkeyboardExample로 만듭시다.

프로젝트가 만들어 지셨나요? 사실 이미 ios앱을 예제라도 만들어 보신분이면

"뭐야.. 똑같은데?"하실 수 있습니다.

네 키보드 앱의 화면은 크게 2개로 구분지을수 있으니까요!

1. 앱 화면
2. 키보드 화면

여기서 앱 화면은 실제로 앱 아이콘을 눌러서 실행하면 등장하는 화면입니다.

기존에 다른앱은 이 화면에 기능을 구현하지만 키보드 앱은 이 화면에 키보드 기능을 구현하면 안됩니다!

대부분 키보드 설정이나 튜토리얼 등을 제공하는 용도로 사용하지만, 아이디어에 따라 여러가지 기능을 구현할수도 있겠네요.

아무튼 방금 만든 부분은 1. 앱화면 에 해당하는 부분입니다.

타겟 추가하기

그럼 이제 2.키보드 화면을 추가해줄 차례입니다.

File->New->Target으로 들어가 아래 그림과 같이 custom keyboard extension을 눌러주세요!

그 다음 이름을 지어야 하는데, 약간 혼동이 있을 수 있습니다.

이 단계에서 지어지는 이름은 2.키보드 화면 의 이름이라고 생각하시면 좋습니다.

정해진 규칙은 없지만 처음 지어지는 이름은 앱의 이름으로, 지금 지어지는 이름은 앱이름 +keyboard로 지으시는게 구분하시긴 편할것 같아요

ex) 급식체 , 급식체키보드

이름을 결정하시고 다음 버튼을 누르시면 아래와 같은 화면이 뜨는데 activate를 눌러주세용(저는 Customkeyboard로 이름지었습니다.)

그럼 다음과 같은 파일구조가 완성됩니다.

이 단계까지 오셨으면 아주 기본적인 키보드 구현은 끝났습니다.

실제로 시뮬레이터에서 구동을 시켜보시면 nextkeyboard button만 달랑 있는 키보드앱을 확인하실수가 있어요.

다음 장에선 키보드 앱 설계를 위한 기본적인 MVC 디자인 패턴을 적용해 보겠습니다.

만들기에 앞서, 기본적인 키보드 익스텐션의 구조(architecture)를 알아봅시다.

많이 어려운 내용은 없지만 아주 기초적인 swift와 xcode경험이 있어야 수월합니다.

UIInputviewController

(Basic structure of a custom keyboard, 출처 : developer.apple.com)

우리가 만들 키보드의 구조입니다. 아직 생소한것들이 많이 있으시겠지만 차근차근 알아가 봅시다.

먼저 위 그림에서 제일 중요한 것은 UIInputviewController 입니다.

사용자가 만든 앱을 모든 앱에서 접근 가능한 키보드로 만들어주는 친구 입니다.

iOS에서는 텍스트필드와 같이 키보드 입력이 필요한 상황에서는 InputView를 띄웁니다. 간단하게 말하면 키보드가 올라오는 '영역'이라고 생각하시면 됩니다.

이러한 InputView를 Control하는 컨트롤러가 바로 UIInputviewController가 되구요.

앞으로 진행할 프로젝트에서도 우리는 커스텀 뷰를 만들어서 이 Inputview의 서브뷰로 추가하는 방식으로 키보드를 구현할거에요.

textDocumentProxy

textDocumentProxy는 키보드 앱이 입력에 접근 할 수 있는 proxy입니다.

proxy라는 말이 조금 생소하시다면 '중계기' 또는 '중계인'으로 이해하셔도 좋을것 같습니다.

입력에 접근한다는 말은, 지금 커서에 위치한 곳에 텍스트를 입력하거나, 지우거나 하는 등의 행동을 얘기합니다.

그렇다면 왜 입력에 접근하는데 바로 접근하지 않고 proxy를 사용할까요?

조금만 고민해보면 보안 문제 때문인걸 알 수 있습니다.

사용자 입력에 커스텀 키보드가 마음껏 접근이 가능하다면, 대화,비밀번호,아이디,통장번호 등 스마트폰을 사용하면서 만드는 제일 민감한 정보들이 마구마구 노출 된다는 것과 같으니까요.

정리

정리해보면 가장 기본적인 구조는 이렇습니다.

1. inputview(키보드가 올라오는 영역)에 우리가 원하는 view를 띄운다.
2. 우리가 원하는 view에서 사용자의 입력이 감지 된다면 2-1. textDocumentProxy를 이용하여 입력하거나,지우거나 하는 등의 행동을 요청

Custom Keyboard

iOS에서 키보드를 커스터마이징 할 수 있게 된건 안드로이드 보다 상대적으로 오래 되지 않았습니다.

iOS8 버전부터 extension의 개념으로 커스텀 키보드 어플리케이션을 제작 할 수 있게 되었는데,

이미 사용자들은 아이폰의 키보드에 적응해버린 이후라 많이 활성화 되어있지는 않은 것 같습니다.

단적으로 안드로이드와 비교해보면 안드로이드 사용자들이 사용하는 키보드는 제각각 다른 반면(제조사 제공키보드, 써드파티 키보드 등) 아이폰 유저들은 상대적으로 기본 키보드 사용자가 월등히 많다고 생각합니다.

그래도 키보드를 커스터마이징 할 수 있다는 건 매우 매력적입니다. 우리가 스마트폰을 사용하면서 제일 많이 마주하는 앱은 아마도 키보드 앱 일테니깐요.

Apple Guidelines

iOS 개발을 위해서는 꼭 2가지 문서는 참고하는 것이 좋다고 생각합니다.

Apple에서 제공하는 HIG(Human Interface Guidelines)(https://developer.apple.com/design/human-interface-guidelines/) 와 developer documentation(https://developer.apple.com/documentation/) 입니다.

먼저 HIG에서 extension guide를 살펴보면 custom keyboard에 관련된 내용을 찾을 수 있습니다.(https://developer.apple.com/design/human-interface-guidelines/ios/extensions/custom-keyboards/)

Human Interface Guidelines

HIG를 읽어보시면 키보드 앱을 만들때 다음과 같은 사항을 고려해야 합니다.

1.Make sure you really need a custom keyboard

• Systemwide 하게 사용될 키보드를 만드세요.

키보드 익스텐션은 사용자가 사용하는 앱 어디에서나 접근이 가능합니다.(은행,비밀번호 등 일부 보안이 필요한 섹션 제외) 따라서 정말 System-wide하게 작동되어야 할 키보드만 키보드 익스텐션으로 만들어야 합니다. 혹시 본인의 앱에서만 작동하는 키보드를 만들고 싶다면 키보드 익스텐션보단 custom inputview를 만드시는게 좋아요! ex) - 급식체 자동 완성 키보드 (o) , - 쇼핑몰 앱 내에서 사용가능한 내 장바구니 목록 이동 키보드(x)

2.Provide an obvious and easy way to switch between keyboards.

• 키보드 전환을 구현하세요.

어찌보면 당연한 이야기 입니다. 써드파티 키보드에서 다른 키보드로 전환이 불가능하다면...끔찍하네요.

가장 중요하게 구현해야 될 부분입니다. 실제로 애플의 가이드를 따라가다보면 만들어지는 아주 기본 키보드앱에도 딱 하나 구현되어있는 버튼이 'next keyboard' 버튼입니다.

3.Don't duplicate system-provided keyboard features.

• 기본 키보드가 제공하는 기능을 또 구현하지 마세요.

2번과 다르게 구현하지 말아야 될 부분입니다. 예시에서는 이모티콘,글로벌키,받아쓰기 버튼을 볼 수 있네요. 헉 그럼 이모티콘 키보드를 만들수 없느냐? 그건 아닙니다. 다만 특정 기종(2020년 기준 비교적 최신기종) 아이폰에서는 키보드 밑에 글로벌키랑 받아쓰기, 이모지 버튼이 나타납니다. 키보드와는 독립적인 영역으로요! 만약 이 버튼을 똑같이 만들면 사용자에게 혼란을 줄 수 있기 때문에 그런것 같습니다.

4.Consider providing a keyboard tutorial in your app

• 꼭 튜토리얼을 만드세요.

키보드 앱은 설치하면 뚝딱 추가되는것이 아닌, 사용자가 직접 추가하는 과정이 필요합니다.(일반-키보드-키보드-키보드추가) 이러한 과정을 꼭 명시하는것이 좋고, 아직 익숙하지 않을 사용자를 위해 app에서 꼭 튜토리얼을 제공하는 것이 좋습니다. 만약 제대로 안하면.. 리뷰에 '작동이 안되네요'가 쌓일지도 몰라요.

접근

레벨4 답게 어려웠습니다.

처음에 생각한 방식은 여러가지 있었습니다.

1. DFS
2. 구간합

DFS의 경우 최대 깊이가 5만(최대길이 10만 / 2) 씩이나 되는 말도안되는 방식이라 아니라고 생각했고, 구간합도 구간의 합이 이전 스티커의 사용유무에 따라 달라지기 때문에 계산이 불가능하다고 생각했습니다.

아무리 생각해도 DP밖에 없어서 DP로 접근했습니다.

2차원 DP문제에 많이 익숙해서 인지 100,000 x 100,000배열을 선언할수 없어 고민을 오래한 문제였습니다.

결론은 1차원 DP를 사용하면 됐고, 레벨4인 이유는 앞의 스티커를 땠을 때, 때지 않았을때를 구분해서 2개의 경우를 고려해야 하기 때문이었습니다.

코드에서 dp[i]는 맨 앞 스티커를 사용하였다고 가정하고 2번째 스티커를 사용하지 않은 상태에서 i까지의 최대 값 입니다.

즉 dp[0]은 첫번째 스티커를 사용했기때문에 sticker[0]의 값과 같고, dp[1]은 2번째 스티커를 사용하지 않았기 때문에 dp[0]과 값이 같아야 합니다.

이때 dp[2]부터 계산하면 dp[i] = max(dp[i-1](i번째 스티커를 사용하지 않은 최대값), dp[i-2]+sticker[i](i번째 스티커를 사용한 값))이 됩니다.

dp2는 첫번째 스티커를 사용하지 않은 경우 입니다.

두 배열 중 가장 높은 값을 return하면됩니다.

다음은 코드 전문입니다.

def solution(sticker):

    if len(sticker) == 1:
        return sticker[0]
    dp = [0 for _ in range(len(sticker))]  # use first sticker
    dp2 = [0 for _ in range(len(sticker))]  # unused first sticker

    dp[0] = sticker[0]
    dp[1] = sticker[0]

    dp2[0] = 0
    dp2[1] = sticker[1]

    for i in range(2, len(sticker) - 1):
        dp[i] = max(dp[i - 2] + sticker[i], dp[i - 1])

    value_1 = max(dp)

    for i in range(2, len(sticker)):
        dp2[i] = max(dp2[i - 2] + sticker[i], dp2[i - 1])
    value_2 = max(dp2)

    answer = max(value_1,value_2)
    return answer

접근

구간합 문제이기 때문에 미리 구간합을 구해줍니다.O(Log N)

이러면 매번 계산하지 않아도 O(1)로 구간합을 구할 수 있습니다.

기본적인 알고리즘은 다음과 같습니다.

1. 첫번째 아들이 cookie[0,1,2,3 ... ]부터 1,2,3, .. N-1 개를 고름 1-2. 두 번째 아들이 첫 번째 아들 바로 다음부터 1,2,3... 개를 고름

이렇게 하면 문제는 풀리지만 시간 초과가 납니다.

몇가지 조건만 추가하면 시간초과를 피할 수 있습니다.

1. 첫 번째 아들에게 줄 쿠키개수가 남은 모든 쿠키개수보다 크다면 검사하지 않습니다.
2. 두 아들에게 줄 쿠키의 개수가 전체구간 합을 2로 나눈 몫과 같다면 최대값이므로 더 이상 검사하지 않습니다.
3. 첫 번째 아들에게 줄 쿠키 개수가 현재 구한 최대 쿠키개수보다 작으면 검사하지 않습니다.

다음은 코드 전문입니다.

def solution(cookie):
    answer = 0

    section_sum = []
    N = len(cookie)
    for i in range(N):
        if i == 0 :
            section_sum.append(cookie[i])
        else:
            section_sum.append(cookie[i]+section_sum[i-1])


    maxi = 0
    isMaxFind = False

    for f in range(0,N):
        for l in range(1,N-f+1):
            if f == 0:
                f_sun = section_sum[f+l-1]
            else:
                f_sun = section_sum[f+l-1] - section_sum[f-1]

            s = f+l
            if f_sun > section_sum[-1] - section_sum[s-1]:
                break
            if f_sun < maxi:
                continue
            for l2 in range(1,N-s+1):
                s_sun = section_sum[s+l2-1] - section_sum[s-1]

                if f_sun == s_sun:
                    maxi = max(maxi,f_sun)
                    if maxi == section_sum[-1]//2:
                        isMaxFind = True
                    break

                elif f_sun < s_sun:
                    break
            if isMaxFind:
                break
        if isMaxFind:
            break

    answer = maxi

    return answer

접근

명령 길이가 500개 밖에 되지않고, 각 명령을 실행할 때 갔던 길인지 아닌지만 판단하면 되기 때문에 시뮬레이션으로 했습니다.

중요한건 이미 갔던 길인지 아닌지를 판단하는 과정인데

당연히 지금까지의 루트안에 이 길이 있느냐 를 판단해버리면 시간이 너무 오래걸립니다.

그냥 hash형태로 각 좌표에서 상,하,좌,우를 갔는지 안갔는지만 저장하고

실제로 이동이 가능해서 이동하였을땐 출발지점의 방향과 도착지점의 역방향을 갔다고 판단하면 됩니다.

즉 (0,0)에서 (1,0)으로 갔다면 (0,0)의 U 방향이 1, 그리고 (1,0)의 D방향도 1이 되어야합니다. (방향 상관없이 그 길은 갔다고 판단하기때문)

다음은 코드 전문입니다.

from _collections import defaultdict

def solution(dirs):
    answer = 0
    board = [[0 for _ in range(11)] for _ in range(11)]
    four_ways = [[defaultdict(lambda :0) for _ in range(11)] for _ in range(11)] # U D R L

    dir = dict()
    opposite = dict()

    dir['U'] = [-1,0]
    dir['D'] = [1,0]
    dir['R'] = [0,1]
    dir['L'] = [0,-1]

    opposite['U'] = 'D'
    opposite['D'] = 'U'
    opposite['R'] = 'L'
    opposite['L'] = 'R'
    r = 5
    c = 5
    for i in range(len(dirs)):
        nr = r+dir[dirs[i]][0]
        nc = c+dir[dirs[i]][1]

        if nr < 0 or nr > 10 or nc < 0 or nc > 10:
            continue
        else:
            if four_ways[r][c][dirs[i]] == 0:
                answer += 1
                four_ways[r][c][dirs[i]] = 1
                four_ways[nr][nc][opposite[dirs[i]]] = 1
            r = nr
            c = nc







    return answer

접근

개인적으로 많이 마주치지 못한 유형이라 신선했습니다.

이런 스타일의 문제는 규칙성 발견이 주가 된다고 생각하여 분할 정복으로 풀어봤습니다.

지문 그대로 계속 실행하다보면 뭐가 0 이고 뭐가 1인지 햇갈립니다.

그래서 모두 종이 1장을 접는 경우로 분할해봅시다.

1장을 오른쪽을 잡고 왼쪽으로 접는다면 점선(0)이 생깁니다.

이때 다시 한번 더 접는것은 종이 2장을 포개놓고 접는것과 동일하며

포개진 아래쪽 종이는 정상적인 방향, 위쪽 종이는 반대 방향으로 접히므로

0 0 1 이 됩니다.

계속 이렇게 하다보면 접히는 중간선을 중심으로 좌측에 0 우측에 1이 생긴다는 규칙을 발견할 수 있습니다.

구현이야 저처럼 dfs해도 되고, 비트마스크나 다른 방법을 사용하면 조금더 효율적일것 같기도 합니다.

다음은 코드 전문입니다.

def dfs(depth,num,ans):
    if depth >= folding_num:
        ans.append(num)
        return
    else:
        dfs(depth+1,0,ans)
        ans.append(num)
        dfs(depth+1,1,ans)


def solution(n):
    global folding_num
    folding_num = n
    answer = []

    dfs(1,0,answer)
    return answer

접근

백준에 있는 삼성기출문제 '다리 만들기2'와 아주 유사한 문제입니다.

1. BFS로 구역을 나누고
2. 각 구역을 연결하는 모든 다리를 구합니다.
3. kruskal 알고리즘을 사용합니다.

구현

전반적으로 시뮬레이션 느낌이 강했고, 짜잘하게 신경써주어야 될 부분이 있긴 했습니다.

그냥 구현하느라 위에서 1과 2를 나눴는데

실제로는 구역을 나누면서 다른구역과 마주쳤는데, 사다리를 놓아야 할 상황일때를 구해버리면 되긴합니다.

다음은 코드 전문입니다.

from collections import deque,defaultdict


def solution(land, height):
    answer = 0
    row = len(land)
    col = len(land[0])

    visited = []



    vi_co = 0

    for i in range(row):
        temp = []
        for j in range(col):
            temp.append(0)
        visited.append(temp)

    for i in range(row):
        for j in range(col):
            if visited[i][j] != 0:
                continue
            else:
                deq = deque()
                deq.append([i, j])
                vi_co += 1

                visited[i][j] = vi_co

                while len(deq) != 0:
                    r = deq[0][0]
                    c = deq[0][1]
                    deq.popleft()

                    if (r + 1) < row and (r + 1) >= 0 and c < col and c >= 0:
                        if abs(land[r][c] - land[r + 1][c]) <= height and visited[r + 1][c] == 0:
                            deq.append([r + 1, c])
                            visited[r + 1][c] = vi_co
                    if (r - 1) < row and (r - 1) >= 0 and c < col and c >= 0:
                        if abs(land[r][c] - land[r - 1][c]) <= height and visited[r - 1][c] == 0:
                            deq.append([r - 1, c])
                            visited[r - 1][c] = vi_co
                    if r < row and r >= 0 and (c + 1) < col and (c + 1) >= 0:
                        if abs(land[r][c] - land[r][c + 1]) <= height and visited[r][c + 1] == 0:
                            deq.append([r, c + 1])
                            visited[r][c + 1] = vi_co
                    if r < row and r >= 0 and (c - 1) < col and (c - 1) >= 0:
                        if abs(land[r][c] - land[r][c - 1]) <= height and visited[r][c - 1] == 0:
                            deq.append([r, c - 1])
                            visited[r][c - 1] = vi_co

    dir = [ [1,0] , [-1,0] , [0,1], [0,-1] ]
    cost = defaultdict(lambda :10000)
    is_connected = []
    for r in range(row):
        for c in range(col):
            for dr,dc in dir:
                if 0 <= r+dr < row and 0 <= c + dc < col:
                    if visited[r+dr][c+dc] < visited[r][c]:
                        continue
                    elif visited[r+dr][c+dc] > visited[r][c]:
                        cost[(visited[r][c],visited[r+dr][c+dc])] = min(cost[(visited[r][c],visited[r+dr][c+dc])],abs(land[r][c] - land[r+dr][c+dc]))


    cost = sorted(cost.items(),key=lambda x:x[1])


    global root
    root = [-1]
    for i in range(1, vi_co + 1):
        root.append(i)

    for (s,e),c in cost:
        root_x = u_find(s)
        root_y = u_find(e)

        if root_x != root_y:
            u_union(s,e)
            answer+=c


    return answer


def u_find(x):
    global root

    if root[x] == x:
        return x
    else:
        root[x] = u_find(root[x])
        return root[x]

def u_union(x,y):
    global root

    x = u_find(x)
    y = u_find(y)

    root[y] = x

접근

오랜만에 삼성 스타일의 시뮬레이션 문제 같았습니다.

주의해야 할 점은 10000의 길이와 10000의 무게를 견딜수 있는 다리를

10000의 무게를 가진 트럭 10000대가 지나갈 때, 한번에 하나의 트럭만 지나갈 수 있으므로

최대 걸리는 시간은 약 10000 * 10000 = 1억초 가 됩니다.

진짜 시뮬레이션처럼 시간을 1씩 증가시키면서 1억번 돌리면.. 아무래도 시간초과가 날 것 같습니다.

구현

다리가 더이상 무게를 견딜 수 없을 때만, 맨 앞에 가는 트럭이 하차하는 시간으로 타임워프 하는 방식이며

해당 시간에 무엇을 먼저 해주어야 하는지, 선후 관계만 잘 따지면 됩니다.

• 시간은 1초부터 시작합니다.

1. 현재 시간에 하차 해야 할 트럭이 있는지 먼저 살펴봅니다.
2. 다리에 대기 중인 가장 최근 트럭을 올릴 수 있는지 판단합니다. 2-1. 올릴 수 있다면 승차 시키고, 시간을 1 증가시킵니다. 2-2. 올릴 수 없다면 가장 먼저 하차해야 할 시간으로 타임워프 합니다.

위 알고리즘으로 진행하면 1억초가 걸리는 케이스에서도 루프를 1억번 돌지 않고, 10000번 정도 돌게 됩니다.

그리고 대기하는 트럭이 queue의 방식으로 빠져나오는것 같지만, 굳이 벡터로 주어진 데이터를 큐나 덱으로 바꾸거나, 역으로 돌리시지 말고 index를 나타내는 변수 하나만 선언하시면 됩니다.

다음은 코드 전문입니다.

#include <string>
#include <vector>
#include <queue>
#include <utility>

using namespace std;

int solution(int bridge_length, int weight, vector<int> truck_weights) {
    int time = 1;
    int loaded_weight = 0;
    int load_target_num = 0;

    queue<pair<int,int> > bridge;



    do{
        if (!bridge.empty()) {
            if (bridge.front().second == time) {
                loaded_weight -= bridge.front().first;
                bridge.pop();
            }
        }

        if ((loaded_weight < weight) && ((weight-loaded_weight) >= truck_weights[load_target_num]) && load_target_num < truck_weights.size()) { // load available

            bridge.push(pair<int, int>( truck_weights[load_target_num] , time+bridge_length ));
            loaded_weight += truck_weights[load_target_num];
            load_target_num++;
            time++;
        }else if(!bridge.empty()){ //load unavailable
            time = bridge.front().second;
        }

    }while((load_target_num < truck_weights.size()) || !bridge.empty());

    return time;
}

접근

결국 각 탑 마다 왼쪽에서 제일 가까운 나보다 높은 탑의 위치를 가지고 있으면 되기 때문에,

이를 저장하는 배열을 선언해서 풀었습니다.

카테고리가 스택인걸로 보아, 순회하면 O(N^2)이기 때문에 스택을 이용해서 최적화 하라는것 같은데,

제 방법대로 해도 O(N^2)은 피할수 있을것 같아 그냥 구현해 보았습니다.

구현

간단합니다. 내가 전송할 탑의 위치를 저장하는 배열을 answer라고 하고,

처음엔 이를 모두 0으로 초기화 합니다. 0은 전송할 수 없음을 나타냅니다.

맨 왼쪽 탑은 절대로 전송할 수 없기에 , 왼쪽에서 1번째 탑부터 조사합니다.

다음과 같은 로직입니다.

1. 만약 현재보다 하나 왼쪽 탑의 높이가 나보다 높다면 그 탑으로 전송
2. 그렇지 않다면 그 탑의 전송 위치의 높이 조사
3. 0(전송할수 없음)이면 현재 탑 또한 전송불가능

1,2를 반복한다면 마치 union find에서 find하는 과정처럼 진행이 됩니다.

즉 왼쪽의 전송위치를 살펴보는 것은 나보다 낮은 값보다는 높은 높이의 탑을 조사하는 것 입니다.

[1,2,3,4 ... , 9999] 인 경우에서는 배열을 1번씩 돌면서 모두 실패로 뜨기 때문에 O(N)일것이며,

[9999,9998, ... ,1] 같은 경우도 바로 왼쪽에다 전송하게 되므로 O(N)일 것 입니다.

익스트림 케이스를 생각해 본다해도

[100,1,2,3,4,5,6, ... 9999] 같은 경우나

[100,1,101,2,102,3 ...,9999] 과 같은 경우를 따져보아도

왼쪽을 모두 검사하는게 아니라 나보다 작거나 같은 높이보다 큰 값만 계속 찾기 때문에

O(N)을 달성 할 수 있습니다.

다음은 코드 전문입니다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> heights) {
    vector<int> answer;
    for(int i = 0 ; i < heights.size(); i++){
        answer.push_back(0);
    }

    for(int i = 1 ; i < heights.size(); i++){
        int com = i;
        while(true){
            if (heights[com-1] > heights[i]) {
                answer[i] = com;
                break;
            }else{
                com = answer[com-1];
                if (com == 0) {
                    break;
                }
            }

        }

    }

    return answer;
}

접근

뻘짓 대잔치 였던 문제

의식의 흐름대로 풀다보니 비교함수는 하드코딩 스타일이 되었습니다.

결국 해답을 찾긴 했지만, 조금 더 신중하고 , 개괄적으로 생각해야 될 것 같습니다.

자꾸 정렬같은 문제를 풀 때 , 모든 케이스를 고려하려고 하는 버릇이 있는데

그렇게 하다보면 계속 하나씩 조건이 추가되며 모든 케이스를 고려 할 수 없을 가능성이 높습니다.

그보다 전체를 관통하는 알고리즘을 생각해보는 것이 좋으며,

이 문제는 간단하게 a ,b를 비교했을때 둘 중 누구에게 우선순위를 주어야 하는가로 좁혀질 수 있습니다.

조금만 고민해보면 맨 앞자리에 따라 소팅을 해야하는건 발견하기 쉽습니다.

하지만 예제에서 말해주듯이 3과 30을 비교하면 3이 우선이 되어야합니다.

이유는 330이 303보다 크기 때문이죠...

이 부분을 어떻게 처리하느냐가 관건인것 같은데 겹치는 부분을 제외한 부분이 겹치는 부분과 크냐,작냐 이런식으로 비교해보려 했던 것 같습니다.

그냥 두개를 a+b , b+a로 합쳐본 뒤 크기 비교를 하면 끝났을 것을..

코드 전문입니다..ㅠ

from functools import cmp_to_key
def compare(x,y):
    t1 = int(x+y)
    t2 = int(y+x)

    if t1 > t2:
        return -1
    elif t1 < t2:
        return 1
    else : return 0



def solution(numbers):
    answer = ''
    for i in range(len(numbers)):
        numbers[i] = str(numbers[i])


    numbers.sort(key = cmp_to_key(compare))
    answer = ''.join(numbers)
    s = 0
    for i in range(len(answer)):
        if answer[i] == '0':
            s += 1
        else:
            break
    if s != 0:
        answer = answer[s - 1:]

    return answer

접근

처음에 dfs가 아니라 해쉬로 접근하려 했습니다.

ticket의 출발지점을 key로 도착지점을 value로 가지는 해쉬맵을 만들고

만약 출발지점이 같지만, 도착지점이 다른 티켓이 있을 경우를 대비해서 value를 vector으로 선언했습니다.

2개 이상의 루트가 존재하면 알파벳 순으로 여행해야 하므로 저 vector의 길이가 2 이상이라면 정렬만 하면 된다고 생각했으나 ...

접근2

50.0점이 나왔습니다. 애초에 그렇게 쉬울 것 같지도 않았습니다.

문제는 그때그때 알파벳순으로 여행하는것이 꼭 최선의 경로가 아니라는 점 이었습니다.

무조건 알파벳순으로 여행하면, 모든 티켓을 사용하지 않았음에도 더 이상 여행할곳이 없는 경우가 생깁니다. 따라서 백트랙킹으로 되돌아가야 하는 문제였습니다.

계속 세그 폴트가 뜨길래 처음엔 티켓이 너무 많나 라고도 생각했습니다.

실제로 여행지의 개수제한만 있지, 티켓의 제한은 없고, 모든 여행지를 돌아다닐수 있게만 티켓이 주어지기 때문에

티켓은 무한대가 가능합니다.

예를 들어 여행지가 1,2,3이 있다면

1->2 , 2->1 이런 티켓이 1000억개가 있고 2->3 티켓이 하나 있기만 하면 모든 조건이 만족됩니다..

조건에 티켓 개수의 제한이라도 있었으면 하는 바램이었습니다.

아무튼 세그폴트나 런타임 에러가 나는건 티켓장수의 문제가 아니라

알파벳 순으로 진행하다보면 더 이상 진행할 수 없음에도, 무조건 티켓장수 만큼 여행을 해야하기에

잘못된 메모리 참조가 일어나는 것 이었습니다.

다음부터는.. 풀기 전에 최대한 많은 예외를 생각해봐야 겠습니다. 실제 테스트에서는 제가 틀린줄도 몰랐을테니까요

다음은 코드 전문입니다.

#include <string>
#include <vector>
#include <unordered_map>
#include <utility>
#include <algorithm>
using namespace std;
unordered_map<string, vector<string>> src_dst;
unordered_map<string, int> un_used;
vector<string> path;
vector<vector<string>>* t;
bool dfs(string src);
vector<string> solution(vector<vector<string>> tickets) {

    t = &tickets;

    for(int i = 0 ; i < tickets.size(); i++){
        src_dst[tickets[i][0]].push_back(tickets[i][1]);
        un_used[tickets[i][0]+tickets[i][1]] += 1; // need to check
    }

    path.push_back("ICN");
    dfs("ICN");


    return path;
}

bool dfs(string src){
    bool isFail = true;
    if ((t->size())+1 == path.size()) {
        return true;
    }else if(src_dst[src].empty()){
        return false;


    }else{
        if (src_dst[src].size() > 1 ) {
            sort(src_dst[src].begin(),src_dst[src].end());
            for(int j = 0 ; j < src_dst[src].size(); j++){

                if (un_used[src+src_dst[src][j]] != 0) {
                    path.push_back(src_dst[src][j]);
                    un_used[src+src_dst[src][j]] -= 1;
                    if(!dfs(src_dst[src][j])){
                        isFail = true;
                        path.pop_back();
                        un_used[src+src_dst[src][j]] += 1;
                    }else{
                        isFail = false;
                        break;
                    }
                }
            }
        }else{

            path.push_back(src_dst[src][0]);
            un_used[src+src_dst[src][0]] -= 1;
            if(!dfs(src_dst[src][0])){
                un_used[src+src_dst[src][0]] += 1;
                path.pop_back();
                isFail = true;
            }else{
                isFail = false;
            }



        }

    }
    if (isFail) {
        return false;
    }
    else return true;
}

접근

정말 기본 dfs 문제입니다. 잔실수 안하면 금방 풀 수 있습니다. 레벨3이라고 되어 있는데, 조금은 이해가 되지 않습니다.

그냥 visit배열을 사용해서 한번 변환한 문자열로는 다시 변환하지 않는 것만 처리해주시고,

문자열이 1개만 다르다는걸 제대로 판단하시면 됩니다.

가끔 이 문제에서 문자열이 3글자만 올수있다고 생각하시는 분들도 계시지만, 문자열은 3~10글자로 올수 있습니다.

그리고 교집합으로 푸시면 안됩니다. 순서도 같아야 하는데,len(set(a) & set(b)) == 1 로 푸시면

'asd'와 'csa'가 한글자만 바뀌었다고 판단하게 됩니다.

코드 전문입니다.

visit = []
res = []
def solution(begin, target, words):
    answer = 0

    co = 0
    for i in range(len(words)):
        visit.append(0)


    def dfs(word,depth):
        if word == target:
            res.append(depth)
            return
        else:
            for i in range(len(words)):
                if visit[i] == 1:
                    continue

                co = 0
                for j in range(len(word)):
                    if word[j] != words[i][j]:
                        co += 1
                if co == 1:
                    visit[i] = 1
                    dfs(words[i],depth+1)
                    visit[i] = 0

    dfs(begin,0)
    if len(res) != 0 :
        answer = min(res)
    return answer

접근

dfs/bfs 항목에 있는 문제이지만, 보자마자 union find와 그래프가 떠올랐습니다.

굳이 따지자면 양방향 그래프인데, 그냥 union find만으로도 해결이 가능할 것 같았습니다.

따라서 각 노드를 순회하면서 자기보다 높은 번호의 노드와 연결되어 있다면 두 집합을 union시켰습니다.

문제

조금 실수해서 실패한 부분이 있었습니다.

최종 네트워크의 개수를 root가 몇개 있는지를 조사하는 방식으로 했는데,

두 노드가 모두 각자의 네트워크가 있고, 이 두 노드를 연결해야 할 때 union만 시켜준다면 최종결과에서 다시 한번더 부모노드를 찾아주어야 합니다.

예를들어 1번 노드가 3,4,5,6 에 연결되어있고,

2번 노드가 5,6에 연결되어 있다면

최종적으로는 1,2,3,4,5,6이 모두 연결된 하나의 네트워크를 구성해야 하지만

마지막에 다시 부모노드를 찾아 주지 않는다면

3,4번의 부모는 1번 노드이고, 1번노드의 부모는 2번노드이며

5,6번 노드의 부모는 2번노드가 되어

최종적으로 root의 개수는 1,2 인 2개가 나오게 됩니다.

다음은 코드 전문입니다.

#include <string>
#include <vector>
#include <set>
using namespace std;

int u_find(int x);
void u_union(int x,int y);


int root[200];
int height[200];
int solution(int n, vector<vector<int>> computers) {
    int answer = 0;
    set<int> res;
    for(int i = 0 ; i < n; i++){
        root[i] = i;
        height[i] = 0;
    }

    for(int i = 0 ; i < n ; i++){
        for(int j = i+1 ; j < n ; j++){

            if (computers[i][j] == 1) {
                u_union(i, j);
            }
        }
    }


    for(int i = 0 ; i < n; i++){
        root[i] = u_find(i);
        res.insert(root[i]);
    }
    answer = int(res.size());
    return answer;
}
int u_find(int x){
    if (root[x] == x) {
        return x;
    }else{
        return root[x] = u_find(root[x]);
    }
}
void u_union(int x,int y){

    x = u_find(x);
    y = u_find(y);


    if( x == y) return;

    if (height[x] <height[y]) {
        root[x] = y;
    }else{
        root[y] = x;
        if (height[x] == height[y]) {
            height[x]++;
        }
    }
}

접근

가능한 모든 경우의 수를 탐색하는 dfs 문제입니다.

numbers의 길이가 최대 20이므로 dfs의 깊이는 최대 20이며 트리로 보았을 때 리프노드의 최대 개수는 2^20 = 약 100만 입니다.

끝까지 연산을 해보아야 되는 문제 같아서 백트랙킹 방식으로 가지치기는 하지 않았습니다.

이런 문제를 풀 때 괜히 모든걸 구현할 필요는 없고, 그때 그때 합이 얼마인지만 알면 됩니다.

예전에 비슷한 문제에서 괜히 연산자 조합을 따졌다가 고생한 경험이 있어서 손쉽게 해결할 수 있었습니다.

다음은 코드 전문입니다.

#include <string>
#include <vector>

using namespace std;

void dfs(int depth,int tot);

vector<int> nums;
int t,co;
int solution(vector<int> numbers, int target) {
    int answer = 0;
    nums = numbers;
    t = target;
    co = 0;
    dfs(0, 0);
    answer = co;
    return answer;
}
void dfs(int depth,int tot){
    if (depth == int(nums.size())) {
        if (tot == t) {
            co++;
        }
        return;
    }
    else{
        dfs(depth+1, tot+nums[depth]);

        dfs(depth+1, tot-nums[depth]);

    }

}

접근

카테고리를 소인수 분해라고 달았지만 풀이에는 쓰지 않았습니다.

규칙을 살펴보면 다음과 같은 규칙이 있습니다.

카펫의 가로 길이는 세로 길이와 같거나, 세로 길이보다 깁니다.

만약 저 조건이 없다면 가능한 답이 1개 이상 나올 수 있습니다.

예를 들어 brown = 10 , red = 2 라는 예제에서 위 조건이 없다면

red가 중간에서 가로로 뻗어있는 모양일 때 [4,3]이 답이며

red가 중간에서 세로로 뻗어있는 모양일 때 [3,4]도 답이 됩니다.

따라서 위 조건은 빨간 블록은 정사각형 혹은 가로 모양의 직사각형 이다. 라는 조건으로 해석이 가능합니다.

그럼 다시 빨간 블록으로 돌아와서, 가능한 빨간블록의 경우는 여러가지가 나올 수 있습니다.

예를들어 red = 24 라면

24 x 1 12 x 2 8 x 3 6 x 4 로 표현이 가능하며

이때 필요한 갈색블록의 개수는 빨간 블록의 총 가로길이를 a, 세로길이를 b 라 하였을때 (2a) + (2b) +4 가 됩니다. (빨간색 가로길이 만큼 위,아래 , 세로길이만큼 왼쪽,오른쪽, 비어있는 귀퉁이 4블록)

따라서 red를 가능한 2개의 자연수 곱셈으로 나타낼수 있는 모든 경우 중에서

좌측이 우측보다 큰 경우만 고려하면 됩니다.

이때 (2a) + (2b) +4 == brown을 만족하면 정답이며 정답은

[(a+2) , (b+2)]가 됩니다.

소인수 분해를 사용해야 되나 했지만 red의 최대값이 200만 이므로 만약 200만부터 1씩 감소하면서(혹은 1부터 1씩 증가하면서) 검사한다 해도 1초안에 처리가능한 연산이라고 생각되어 그냥 진행했습니다.

다음은 코드 전문입니다.

#include <string>
#include <vector>

using namespace std;

vector<int> solution(int brown, int red) {
    vector<int> answer;

    for(int i = red ; i >= (red/i) ; i--){
        if (red%i != 0) {
            continue;
        }
        if (((2*i)+(2*(red/i))+4) == brown) {
            answer.push_back(i+2);
            answer.push_back((red/i)+2);
            break;
        }

    }

    return answer;
}

접근

그냥 완전 탐색입니다. 숫자야구는 프로그래밍 기초단계 배울 때 많이 접하는 것 같습니다.

다만 숫자 야구 룰을 모르면 약간 문제를 오독 할 수 있습니다. 문제에서

'각자 서로 다른 1~9까지 3자리 임의의 숫자를 정한 뒤 서로에게 3자리의 숫자를 불러서 결과를 확인합니다. 그리고 그 결과를 토대로 상대가 정한 숫자를 예상한 뒤 맞힙니다.'

라는 문장의 첫 부분을 보면 각 자리의 숫자가 서로 중복이 안된다는 것인지, 각자의 숫자가 중복이 안된다는 것인지 약간 햇갈립니다. 저만 그랬을수도 있지만요...

각 자리의 숫자는 중복이 불가능 하므로 1,2,3,4,5,6,7,8,9에서 3개를 뽑는 순열 9P3 을 하면 됩니다.

구현

가능한 모든 순열을 고려하면서 각 순열에 대하여 모든 질문에 부합하는지 검사하면 됩니다.

먼저 스트라이크 부터 판단하면,

자리수와 숫자가 모두 일치하는지 보고, 그러한 숫자가 몇가지 있는지 보면 됩니다.

만약 모두 일치하는 숫자가 스트라이크 숫자와 다르다면 해당 질문에 부합하지 않는다고 판단하여 그 순열은 정답이 될수 없다고 판단합니다.

이때 중요한건 볼을 판단하기 위해서는 스트라이크라고 판단 된 숫자는 고려하지 않아야 합니다. 따라서 스트라이크라고 판단된 숫자는 -1로 처리했습니다.

볼 판단은 스트라이크로 걸러진 숫자가 아니라면 다른 자리의 숫자 2개와 숫자가 동일한지 보면 됩니다.

스트라이크와 마찬가지로 볼에 해당하는 숫자는 몇개 인지 카운트해서 질문의 볼 숫자와 비교합니다.

다음은 코드 전문입니다.

from itertools import permutations

def solution(baseball):
    answer = 0
    res = []
    num = ['1','2','3','4','5','6','7','8','9']
    permute  = permutations(num,3)
    for n in permute:

        isCorrect = True
        for q in baseball:
            temp = list(n)
            temp_q = str(q[0])
            co_str = 0
            co_ball = 0
            for i in range(3): # is strike?
                if temp_q[i] == temp[i]:
                    co_str += 1
                    temp[i] = '-1'

            if co_str != q[1]:
                isCorrect = False
                break

            for i in range(3):
                if temp[i] == '-1':
                    continue
                if temp[i] == temp_q[(i+1)%3] or temp[i] == temp_q[(i+2)%3]:
                    co_ball += 1

            if co_ball != q[2]:
                isCorrect = False
                break

        if not isCorrect:
            continue
        else:
            res.append(n)




    answer = len(res)
    return answer

접근

주어진 숫자(최대 7개)로 만들수 있는 모든 숫자를 검사해야 합니다.

1개만 고른 순열, 2개만 고른 순열, 3개만 고른 순열 ... N개만 고른순열(N = len(numbers))을 모두 검사해주면 됩니다.

이후 해당 숫자가 소수인지 아닌지 판단한 후 소수라면 결과에 넣으면 됩니다.

가장 중요한 부분은 소수인지 아닌지 판단하는 부분입니다.

당연히 2부터 해당 숫자까지 순회하면서 나눠지는지 보면 되겠지만, 최대로 올 수 있는 숫자가 9999999(999만9999) 이므로 다른 방법을 생각해내야 합니다.

어렴풋이 에라토스테네스의 체가 생각났고, 2부터 sqrt(해당숫자)까지만 검사해보면 소수인지 아닌지 알 수 있다는 증명이 생각나서 적용했습니다.

구현

가능한 숫자순열을 생성하고 int로 바꾸는 과정이 귀찮아서 파이썬으로 풀었습니다.

소수로 판단되는 숫자는 set에 넣어서 011이나 11처럼 다른 순열이지만 같은 숫자인 경우를 고려했습니다.

접근에선 루트를 이용한다 하였지만 sqrt는 실수를 다루기 때문에 성능,정확도 문제가 있다고 판단하여 그냥 제곱했을때 해당숫자보다 작을때까지 루프를 돌렸습니다.

다음은 코드 전문입니다.

from itertools import permutations

def isPrime(num):

    i = 2
    while((i*i) <= num):
        if num%i == 0:
            return False
        i += 1
    return True



def solution(numbers):
    answer = 0
    num_list = []
    res = set()
    for i in range(len(numbers)):
        num_list.append(numbers[i])



    for i in range(1,len(numbers)+1):
        permute = permutations(num_list,i)
        for p in permute:
            temp = ""
            for n in p:
                temp+=n
            int_temp = int(temp)
            if int_temp <= 1 :
                continue
            if isPrime(int_temp):
                res.add(int_temp)


    answer = len(res)
    return answer

접근

그냥 다중 정렬 문제라고 생각하고 풀었습니다.

구현

총 3개의 자료구조를 사용했습니다.

1. 장르를 key로, 재생회수를 value로 가지는 map
2. pair(장르,재생회수)를 원소로 가지는 vector
3. 장르를 key로, 고유번호를 원소로가지는 vector를 value로 가지는 map

정렬 순서는 다음과 같습니다.

1을 2로 복사 한 후 , 2를 재생회수 기준 내림차순 정렬합니다.

3의 각 value인 vector를 2를 참고하여 정렬합니다. 이때 재생회수 순으로 내림차순 하며 만약 같다면 고유번호 순으로 오름차순 합니다.

이후 2를 참고하여 재생회수가 높은 장르부터 3에 value에 들어있는 상위 2개 원소를 answer에 담습니다. 만약 길이가 1이면 한개만 담습니다.

다음은 코드 전문입니다.

#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <utility>

using namespace std;
map<string,int> play_n;
vector<pair<string,int>> v;
map<string,vector<int>> g_n;
vector<int> p;
bool cmp1(pair<string, int> x, pair<string, int> y);
bool cmp2(int x,int y);
vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    p = plays;
    for(int i = 0 ; i < genres.size(); i++){
        play_n[genres[i]] += plays[i];
        g_n[genres[i]].push_back(i);
    }

    for(auto iter = play_n.begin(); iter != play_n.end(); ++iter){
        v.push_back(pair<string, int>(iter->first,iter->second));
    }

    sort(v.begin(), v.end(), cmp1);

    for(int i = 0; i < v.size(); i++){
        sort(g_n[v[i].first].begin(), g_n[v[i].first].end(), cmp2);

        for(int j = 0 ; j < 2; j++){
            answer.push_back(g_n[v[i].first][j]);
            if (g_n[v[i].first].size() == 1) {
                break;
            }
        }


    }


    return answer;
}

bool cmp1(pair<string, int> x, pair<string, int> y){
    return x.second > y.second;
}
bool cmp2(int x,int y){
    if (p[x] == p[y]) {
        return x < y;
    }else{
        return p[x] > p[y];
    }

}

후기

최단 시간에 풀었습니다. 다만 문제에서 주어진 조건을 처음에 놓쳤습니다.

1. 상위 2개의 노래만 고른다는 것
2. 한개만 들어있는 장르는 한개만 고른다는 것

다음부터 구현 후 문제에 조건을 모두 체크해보아야 겠습니다.

접근

처음 접근은 비트마스크를 사용하는 방식 이었습니다.

예를 들어 스파이가 가지고 있는 옷의 종류가 4가지라면

다음과 같은 경우의 수가 나옵니다.

1번째 옷만 입은경우, 2번째 옷만 입은경우, 3번째 옷만 입은경우 ... 1번째와 2번째 옷만, 1번째와 3번째 옷만 ... ... 1234번째 옷 모두 입은 경우

이를 비트마스크로 표현하면

0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 0 ... 1 1 1 1

입니다.

즉 1~(2^N)-1 (N가지 종류의 옷) 까지의 모든 경우의 수를 체크해서, 해당 수가 1이면 해당하는 옷 종류의 개수를 곱해주면 됩니다.

예를 들어 4가지 종류의 옷을 각각 1,2,3,4개 가지고 있다면

0 0 1 1 의 경우에 3*4 = 12개의 경우의 수가 나옵니다.

하지만 이 경우 테스트케이스 1번이 시간초과가 납니다.

익스트림 케이스를 살펴보면, 모두 각기다른 30가지의 옷을 1가지씩 가지고 있다면

가능한 경우의 수는 2^30-1 = 약 10억번의 루프를 돌게되며 각 루프당 해당하는 종류의 옷을 입을 수 있는 경우인지, 아닌지를 판단해야 하기 때문에

시간 복잡도는 O(2^N*N)이 됩니다.

사실 그냥 O(2^N)만 돌려봐도 시간초과가 납니다.

그래서 다른 방법을 찾아봤습니다.

다음은 비트마스크 코드 전문입니다.

#include <string>
#include <vector>
#include <unordered_map>
#include <math.h>

using namespace std;

unordered_map<string, int> clothes_num;
int cpow(int base,int n);
int solution(vector<vector<string>> clothes) {
    int answer = 0;
    int N;
    int t_res = 1;
    for(int i = 0 ; i < clothes.size(); i++){
        clothes_num[clothes[i][1]]++;
    }

    N = int(clothes_num.size());

    for(int i = 1  ; i <= int(cpow(2, N))-1 ; i++){

        int judge = 1;
        t_res = 1;
        for(unordered_map<string, int>::iterator iter = clothes_num.begin(); iter != clothes_num.end(); ++iter){


            if ((judge & i) != 0) {
                t_res *= iter->second;
            }

            judge = judge << 1;
        }
        answer += t_res;
    }
    return answer;
}

접근2

조금만 생각해보면 10억개가 되는 케이스를 모두 고려할 필요없이 경우의 수만 계산해주면 됩니다.

확률과 통계 단원을 배우고 있는 고3수험생 이라면 오히려 쉬웠을 문제 같습니다.

만약 A종류의 옷이 3개가 있다면 경우의 수는 이 3가지를 입는경우 + 이 종류를 입지 않는 경우 1 = 4가지 경우가 됩니다.

이런식으로 모든 종류 옷의 개수에 1을 더해준 후 모두 곱하면 이를 모두 고려한 개수가 나오며

여기서 1을 빼주면 모두 입지않은 경우를 제외하기 때문에 정답이 됩니다.

다음은 코드 전문입니다.

#include <string>
#include <vector>
#include <unordered_map>
#include <math.h>

using namespace std;

unordered_map<string, int> clothes_num;

int solution(vector<vector<string>> clothes) {
    int answer = 1;

    for(int i = 0 ; i < clothes.size(); i++){
        clothes_num[clothes[i][1]]++;
    }

    for(unordered_map<string, int>::iterator iter = clothes_num.begin(); iter != clothes_num.end(); ++iter){
        answer *= ((iter->second)+1);
    }
    return answer-1;
}

후기

역시 뻘짓으로 30분정도 시간이 낭비가 되었긴 했지만, 비트마스크 방식으로 풀어본게 결과와는 상관없이 마냥 나쁘지는 않은 것 같습니다.