내일은 알고리즘

https://school.programmers.co.kr/learn/courses/30/lessons/131130

기본적인 그래프 탐색이나 사이클에 대한 개념이 있으면 쉽게 풀 수 있는 문제입니다.

지문의 설명은 결국 상자와 카드를 기준으로 사이클이 생기면 회차 한 번이 종료된다는 얘기입니다. 사이클은 어느 곳에서 시작하던지 한바퀴가 돌게 되고, 이 문제의 경우 사이클은 정확히 원형으로 들어오기만 하는 노드가 존재하지 않습니다.

따라서 입력을 1번 순회하면서 사이클을 이루는 카드의 갯수들을 카운팅해 정답의 후보에 넣어주고, 최종적으로 그 중 가장 큰 값 두개를 뽑아 곱해주면 됩니다.

만약 사이클의 갯수가 하나라면, 즉 정답의 후보가 1개라서 곱할수가 없다면 0을 return 하면 됩니다.

예제 케이스를 바탕으로 설명해보겠습니다.

입력 cards로 [8,6,3,7,2,5,1,4]가 들어옵니다. 이 입력을 앞에서부터 체크하면서 사이클을 세어줄 겁니다.

1. 0번 위치가 가리키는 상자가 8(7번 위치)입니다. 0번 위치의 값을 0으로 체크해주고 다음 위치를 7번으로 기록합니다.

7번 위치가 가리키는 상자가 4(3번 위치)입니다. 7번 위치의 값을 0으로 체크해주고 다음 위치를 3번으로 기록합니다.

3번 위치가 가리키는 상자가 7(6번 위치)입니다. 3번 위치의 값을 0으로 체크해주고 다음 위치를 6번으로 기록합니다.

6번 위치가 가리키는 상자가 1(0번 위치)입니다. 6번 위치의 값을 0으로 체크해주고 다음 위치를 0번으로 기록합니다.

0번은 이미 0으로 체크된 상태이므로 첫 사이클을 종료합니다.

이 사이클의 노드 갯수는 4입니다. 4를 정답 후보 answer에 넣어줍니다. 이 때의 상태는 아래와 같습니다.

cards [0,6,3,0,2,5,0,0]   answer [4]

2. 1번 위치가 가리키는 상자가 6(5번 위치)입니다. 1번 위치의 값을 0으로 체크해주고 다음 위치를 5번으로 기록합니다.

5번 위치가 가리키는 상자가 5(4번 위치)입니다. 5번 위치의 값을 0으로 체크해주고 다음 위치를 4번으로 기록합니다.

4번 위치가 가리키는 상자가 2(1번 위치)입니다. 4번 위치의 값을 0으로 체크해주고 다음 위치를 1번으로 기록합니다.

1번은 이미 0으로 체크된 상태이므로 두번째 사이클을 종료합니다.

이 사이클의 노드 갯수는 3입니다. 3을 정답 후보 answer에 넣어줍니다. 이 때의 상태는 아래와 같습니다.

cards [0,0,3,0,0,0,0,0]   answer [4, 3]

3. 2번 위치가 가리키는 상자가 3(2번 위치)입니다. 2번 위치의 값을 0으로 체크해주고 다음 위치를 2번으로 기록합니다.

2번은 이미 0으로 체크된 상태이므로 세번째 사이클을 종료합니다.

이 사이클의 노드 갯수는 1입니다. 1을 정답 후보 answer에 넣어줍니다. 이 때의 상태는 아래와 같습니다.

cards [0,0,0,0,0,0,0,0]   answer [4, 3, 1]

더 이상 찾을 사이클이 존재하지 않습니다. 가능한 사이클 중에서 큰 값인 4와 3을 곱한 12를 return하면 됩니다.

def solution(cards):
    answer = []

    for i in range(len(cards)):
        if cards[i] == 0:
            continue
        box = cards[i] - 1
        count = 1
        cards[i] = 0

            while True:
                if cards[box] == 0:
                    answer.append(count)
                    break

                nbox = cards[box] - 1
                count += 1
                cards[box] = 0
                box = nbox

    answer.sort(reverse=True)

    return answer[0] * answer[1] if len(answer) > 1 else 0

https://school.programmers.co.kr/learn/courses/30/lessons/17681

비트연산과 이진수를 구하는 법만 알면 쉽게 풀리는 문제입니다.

arr1과 arr2의 수에서, 두 이진수를 겹친다는것은 | , 즉 or 비트연산을 한다는 뜻입니다.

or 비트 연산으로 수를 바꿔주고 이진수를 구하듯 나누어 주면 됩니다. (위 코드)

또는 1을 shift 해가면서 & and 비트연산으로 해당 위치에 비트가 있는지 체크해주면 됩니다. (아래 코드)

구현에 큰 차이는 없고 만들어진 배열을 뒤집어서 출력만 하면 됩니다.

또는 문자열로 덧붙여 만들고 slice로 뒤집어줘도 됩니다.

def solution(n, arr1, arr2):
    answer = []

    for i in range(n):
        arr1[i] = arr1[i] | arr2[i]

    for i in range(n):
        num = n
        temp = []
        while num > 0:
            if arr1[i] % 2 == 1:
                temp.append("#")
            else:
                temp.append(" ")

            arr1[i] //= 2
            num -= 1
            
 #         temp = ""
#         while num > 0:
#             if arr1[i] % 2 == 1:
#                 temp += "#"
#             else:
#                 temp += " "

#             arr1[i] //= 2
#             num -= 1
#         answer.append(temp[::-1])

        answer.append(''.join(temp.__reversed__()))

    return answer

def solution(n, arr1, arr2):
    answer = []

    for i in range(n):
        arr1[i] = arr1[i] | arr2[i]

    for i in range(n):
        num = 1
        temp = []
        for j in range(n):
            if arr1[i] & (1 << j) != 0:
                temp.append("#")
            else:
                temp.append(" ")
                
#         temp = ""
#         for j in range(n):
#             if arr1[i] & (1 << j) != 0:
#                 temp += "#"
#             else:
#                 temp += " "
        
#         answer.append(temp[::-1])
        
        answer.append(''.join(temp.__reversed__()))

    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/17682

18년 (시험은 17년에 이루어졌을 겁니다.) kakao 문제였다고 합니다.

입력을 적당히 잘 쪼개고 예외를 조심하면서 문제에 주어진 대로 구현하면 풀리는 문제입니다.

다트가 3개이기 때문에 저는 다트의 인덱스 idx와 입력의 인덱스 i를 다르게 관리해줬습니다. 또 점수가 10인 경우를 주의해야 합니다.

def solution(dartResult):
    answer = [0, 0, 0]

    idx = -1
    i = 0

    while i < len(dartResult):
        
        if dartResult[i] in ["S", "D", "T"]:
            if dartResult[i] == "D":
                answer[idx] *= answer[idx]
            elif dartResult[i] == "T":
                answer[idx] = answer[idx] * answer[idx] * answer[idx]
        
        elif dartResult[i] == "*":
            answer[idx] *= 2
            if idx - 1 >= 0:
                answer[idx - 1] *= 2
        
        elif dartResult[i] == "#":
            answer[idx] *= -1
        
        else:
            idx += 1
            if dartResult[i] == "1" and i < len(dartResult) - 1 and dartResult[i + 1] == "0":
                answer[idx] = 10
                i += 1
            else :
                answer[idx] = int(dartResult[i])
        
        i += 1

    return sum(answer)

https://school.programmers.co.kr/learn/courses/30/lessons/131128

counting sort의 개념이 살짝 녹아있는 문제입니다.

수 X와 Y에 대해 각 자릿수에 0~9 사이의 숫자가 몇개가 나오는지를 체크합니다.

어떤 숫자 i에 대해 X와 Y 중에 나온 수가 적은 값을 취합니다. (더 많은쪽은 짝을 이루지 못하고 남습니다.)

숫자 i를 짝이 이루어진 수 만큼 배열에 넣고 내림차순으로 정렬하면 정답이 됩니다.

단, 배열의 길이가 0이라면 "-1"을, 배열의 길이가 0의 갯수와 같다면 (즉 0 말고 다른 수가 배열 안에 없다면) "0"을 return하는 예외처리가 필요합니다.

def solution(X, Y):

    numx = [0 for i in range(10)]
    numy = [0 for i in range(10)]
    answer = []

    for n in X:
        numx[int(n)] += 1
    for n in Y:
        numy[int(n)] += 1

    pred = min(numx[0], numy[0])
    for i in range(10):
        n = min(numx[i], numy[i])
        for j in range(n):
            answer.append(str(i))

    answer.sort(reverse=True)

    if len(answer) == 0:
        return "-1"

    return ''.join(answer) if len(answer) > pred else "0"

https://school.programmers.co.kr/learn/courses/30/lessons/12921

에라토스테네스의 체에 대한 지식이 있다면 쉽게 풀리는 문제입니다.

우리가 찾아야 하는것은 넓은 범위의 소수입니다. 즉, 천만개의 숫자에 대해 일일히 소수를 판정하지 않고, 소수가 아닌 수를 지워가면 됩니다.

2부터 n까지 숫자를 탐색하면서 이전에 나누어지지 않았다면, 즉 소수라면 answer를 1 더해주고 소수의 배수들을 전부 체크해줍니다. (어떤 소수의 배수라면 소수가 아닙니다. 소수는 1과 자신으로만 나누어진다는 명제의 대우입니다.)

n까지 모두 순회한다면 우리가 목표로 하는 소수의 갯수를 알 수 있습니다.

def solution(n):
    answer = 0
    divided = [False for i in range(n+1)]

    for i in range(2, n + 1):
        if not divided[i]:
            answer += 1
            d = i * 2
            while d <= n:
                divided[d] = True
                d += i

    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/12915

lambda를 이용한 정렬을 할 줄 안다면 정말 쉽게 풀 수 있는 문제입니다.

단어의 n번째 글자를 기준으로 정렬해줍니다. 만약 n번째 글자가 같다면 단어를 기준으로 정렬해 줍니다.

def solution(strings, n):
    strings.sort(key=lambda x: (x[n], x))
    return strings

sort(key=lambda x: (x[n], x))

정렬의 key를 lambda식으로 표현해 주는데, 우선 순위는 x[n] 즉 어떤 단어 x의 n번째 글자이고 그 값이 같다면 x 즉 어떤 단어 자체를 기준으로 정렬하겠다는 뜻입니다.

https://school.programmers.co.kr/learn/courses/30/lessons/12926

문자의 아스키코드 변환을 쓸줄 알면 쉽게 풀 수 있는 문제입니다. (각 알파벳 별로 배열을 하드코딩해도 됩니다.)

문자를 아스키코드 값으로 변환해주고, 대 소문자를 구분한 뒤 'a'또는 'A'가 가진 값인 65나 97을 빼줍니다.

그럼 이제 이 알파벳이 몇번째 알파벳인지 알 수 있습니다. 문제에서 주어지는 n값을 더해 뒤로 밀어주고, 혹시 z를 넘어가는 경우를 처리해주기 위해 26으로 나눈 나머지를 취합니다.

ex)

Y는 25번째 알파벳입니다. ord('Y') = 89가 나오고 여기서 ord('A')인 65를 빼주면 25번째 알파벳이라는걸 알 수 있는 24가 남습니다. (A가 0입니다.)

N이 3이라면 24 + 3 = 27이 되고, 이 값을 26으로 나눈 나머지는 1입니다.

Y를 3번 뒤로 밀면 Y Z A B = B가 되고 ord('A')에 1을 더한 66을 chr()해줘도 B가 나옵니다.

def solution(s, n):
    msg = list(s)

    for i in range(len(msg)):
        if msg[i] == " ":
            continue
        else:
            c = ord(msg[i])
            msg[i] = chr(((c + n - 65) % 26) + 65) if c < 97 else chr(((c + n - 97) % 26) + 97)

    return ''.join(msg)

https://school.programmers.co.kr/learn/courses/30/lessons/12930

기본적인 인덱스 관리와 문자열 다루기를 안다면 풀 수 있는 문제입니다.

아이디어는 간단합니다. 단어별 인덱스와 문장의 전체 인덱스를 따로 관리해줍니다.

공백을 만난다면 단어가 끝났음을 의미하기 때문에 단어별 인덱스를 0으로 초기화 시켜줍니다.

공백이 아니라면? 홀짝에 따라 upper(), lower()를 사용해서 대소문자를 바꾸면서 단어별 인덱스를 1씩 늘려주면 됩니다.

문장의 인덱스는 모든 과정마다 늘려줍니다.

문제에서 짝수번째, 홀수번째의 설명이 좀 애매한데, 우리가 알고 있는 배열의 index처럼 0번째 부터 시작한다고 이해하면 예시케이스와 같이 진행됩니다. 

def solution(s):
    msg = list(s)

    idx = 0

    for i in range(len(msg)):
        if msg[i] == " ":
            idx = 0
        elif idx % 2 == 0:
            msg[i] = msg[i].upper()
            idx += 1
        else:
            msg[i] = msg[i].lower()
            idx += 1

    return ''.join(msg)