내일은 알고리즘

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

Java로 푼 문제를 Python으로 다시 작성한 문제입니다.
풀이방법과 주의사항, Java 정답 코드를 보고 싶으신 분은 아래 링크를 확인해주세요!

https://nodingco.tistory.com/189

def solution(number):
    answer = 0

    for i in range(len(number)):
        for j in range(i + 1, len(number)):
            for k in range(j + 1, len(number)):
                if number[i] + number[j] + number[k] == 0:
                    answer += 1

    return answer

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

기본적인 반복문 중첩으로 풀이할 수 있는 완전탐색 문제입니다.

선택한 번호가 겹치지 않도록 반복문의 시작 범위를 잘 잡아주고 모든 경우에 대해 세 번호의 합이 0이 되는 경우를 세어주면 됩니다.

class Solution {
    public int solution(int[] number) {
        int answer = 0;
        
        for(int i = 0; i < number.length; i++){
            for(int j = i + 1; j < number.length; j++){
                for(int k = j + 1; k < number.length; k++){
                    if(number[i] + number[j] + number[k] == 0){
                        answer += 1;
                    }
                }
            }
        }
        
        return answer;
    }
}

https://school.programmers.co.kr/learn/courses/30/lessons/131130?language=java 

Python으로 푼 문제를 Java로 다시 작성한 문제입니다.
풀이방법과 주의사항, Python 정답 코드를 보고 싶으신 분은 아래 링크를 확인해주세요!

https://nodingco.tistory.com/185

기본적인 구현은 비슷하지만 정답 체크를 달리했습니다.

Python과 달리 Java는 배열에 값을 추가하기가 곤란하기 때문에 ArrayList LinkedList 같은 자료구조를 추가로 써야하는데, 귀찮기 때문에... 

answer1과 answer2로 정답 후보 두개를 관리해줬습니다.

새로운 값이 answer1보다 크거나 같다면 answer1을 answer2로, 새로운 값을 answer1로 넣어주면 됩니다.

(두 값이 같아도 갱신해줘야 합니다! 예를 들어 기존 후보가 4와 3이고 새로운 값이 4일때도 answer1을 2로 밀어줘야 4와 4로 16이라는 올바른 값을 return할 수 있습니다.) 

answer1보단 작지만 answer2보다 크다면 새로운 값을 answer2로 넣어주면 됩니다.

초기값을 -1로 넣어줬으므로, answer1 * answer2가 0보다 작다면 둘 중 하나가 -1이라는 소리고 사이클이 하나뿐이라는 얘기니 0을 return합니다. 아니라면 후보가 두개 이상이었다는 소리니 answer1 * answer2fmf return하면 됩니다.

class Solution {
    public int solution(int[] cards) {
        int answer1 = -1;
        int answer2 = -1;
        
        for(int i = 0; i < cards.length; i++){
            if(cards[i] == 0)
                continue;
            
            int box = cards[i] - 1;
            int nbox = -1;
            int count = 1;
            cards[i] = 0;
            
            while(true){
                if(cards[box] == 0){
                    if(count >= answer1){
                        answer2 = answer1;
                        answer1 = count;
                    }else if(count > answer2){
                        answer2 = count;
                    }
                    break;
                }
                
                nbox = cards[box] - 1;
                count ++;
                cards[box] = 0;
                box = nbox;
            }
            
        }
        
        if(answer1 * answer2 < 0){
            return 0;
        }
        
        return answer1 * answer2;
    }
}

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

슬라이딩 윈도우(혹은 투포인터), 맵 자료구조의 개념을 알면 쉽게 풀 수 있는 문제입니다.

가입한 날로부터 10일간 할인을 받을 수 있는 것을 이용해 1~10일동안 살 수 있는 품목을 카운팅합니다.

만약 2~11일 동안 살 수 있는 품목이 궁금하다면, 10일간을 전부 찾을게 아니라 카운팅한 값에서 1일의 할인상품을 빼주고,  11일의 할인상품을 더해주면 됩니다.

우리가 원하는 상품목록이 있기 때문에 그 상품들만 찾아주면 되고 카운팅과 범위 처리는 예외가 나지 않도록 적당히 잘 해주면 됩니다. (설명이 좀 그런데 정말 적당히 잘 하면 됩니다. ㅋㅋ;;)

def solution(want, number, discount) -> int:
    answer = 0
    product = {}
    idx = 0

    for w in want:
        product[w] = idx
        idx += 1

    for i in range(10):
        if discount[i] in product:
            number[product[discount[i]]] -= 1

    for i in range(len(discount)):
        if checklist(number):
            answer += 1

        if discount[i] in product:
            number[product[discount[i]]] += 1
        
        if i + 10 < len(discount) and discount[i + 10] in product:
            number[product[discount[i + 10]]] -= 1

    return answer


def checklist(number) -> bool:
    for n in number:
        if n > 0:
            return False
    return True

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"