📌 파이썬 으로 풀이

📌 문제 링크 :

📌 문제 설명 :

"명예의 전당"이라는 TV 프로그램에서는 매일 1명의 가수가 노래를 부르고, 시청자들의 문자 투표수로 가수에게 점수를 부여합니다. 매일 출연한 가수의 점수가 지금까지 출연 가수들의 점수 중 상위 k번째 이내이면 해당 가수의 점수를 명예의 전당이라는 목록에 올려 기념합니다. 즉 프로그램 시작 이후 초기에 k일까지는 모든 출연 가수의 점수가 명예의 전당에 오르게 됩니다. k일 다음부터는 출연 가수의 점수가 기존의 명예의 전당 목록의 k번째 순위의 가수 점수보다 더 높으면, 출연 가수의 점수가 명예의 전당에 오르게 되고 기존의 k번째 순위의 점수는 명예의 전당에서 내려오게 됩니다.

이 프로그램에서는 매일 "명예의 전당"의 최하위 점수를 발표합니다. 예를 들어, k = 3이고, 7일 동안 진행된 가수의 점수가 [10, 100, 20, 150, 1, 100, 200]이라면, 명예의 전당에서 발표된 점수는 아래의 그림과 같이 [10, 10, 10, 20, 20, 100, 100]입니다.

명예의 전당 목록의 점수의 개수 k, 1일부터 마지막 날까지 출연한 가수들의 점수인 score가 주어졌을 때, 매일 발표된 명예의 전당의 최하위 점수를 return하는 solution 함수를 완성해주세요.

📌 제한 사항

• 3 ≤ k ≤ 100
• 7 ≤ score의 길이 ≤ 1,000
  • 0 ≤ score[i] ≤ 2,000

📌 입출력 예

추측) 

1. 순위 리스트와 결과값 리스트를 선언한다. 

1. score 길이 만큼 for문을 돌린다.

2. 순위 리스트에 추가 

2. 추가하면 sort

3. 만약 k일 보다 

   - 작거나 같다면 : (삭제 없이) 정렬 후 순위 리스트의 길이의 -1 인덱스 값을 가져와 결과값 리스트에 추가한다.

   - 크다면 : k 인덱스 (=마지막에 붙은 배열)을 제거한다. 순위 리스트 길이의 -1 인덱스 값을 가져와 결과값 리스트에 추가한다.

4. for문을 나와 결과값 리스트를 반환

소스코드) 

* 1차) 성공

def solution(k, score):
    answer_List = []
    k_List = []
    for i in range(0, len(score)):
        k_List.append(score[i])
        k_List.sort()
        k_len = len(k_List)

        if len(k_List) > k:
            k_List.remove(k_List[0])
            answer_List.append(k_List[0])
        else :
            answer_List.append(k_List[0])

    return answer_List

리뷰) 

sort 오름차순이니 0번이 가장 낮은 수임을 생각해서 처리하면 쉽다. 추측할 때는 순간 내림차순이라 생각해서 배열 끝을 자를 생각을 했었다. 기본은 오름차순!! 앞을 잘라야한다.

📌 파이썬 으로 풀이

📌 문제 링크 :

📌 문제 설명 :

문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 합니다.

• 먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다.
• 이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다. 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리합니다.
• s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다. 남은 부분이 없다면 종료합니다.
• 만약 두 횟수가 다른 상태에서 더 이상 읽을 글자가 없다면, 역시 지금까지 읽은 문자열을 분리하고, 종료합니다.

문자열 s가 매개변수로 주어질 때, 위 과정과 같이 문자열들로 분해하고, 분해한 문자열의 개수를 return 하는 함수 solution을 완성하세요.

📌 제한 사항

• 1 ≤ s의 길이 ≤ 10,000
• s는 영어 소문자로만 이루어져 있습니다.

📌 입출력 예

추측) 

1. 첫문자를 저장한 변수x를 빈 문자열로 선언한다.

2. start_Idx를 선언한다. 

2. x 카운트와 x가 아닌 카운트를 0으로 선언한다.

2. 문자열 길이만큼 for문을 돌린다.

2. 만약 첫문자가 비어있다면

   - 첫문자 x를 변수에 대입하고, 지금 인덱스를 start_Idx에 대입한다.

2. 만약 x와 현재 문자열이

   - 같으면 x 카운트를 1 올린다.

   - 다르면 x가 아닌 카운트를 1올린다.

3. 만약 x카운트가 x가 아닌 카운트와 같으면

   - 리스트에 s의 문자열에서 start_Idx부터 현재 Idx까지 문자열을 잘라 넣는다

     그리고 start_Idx랑 x 카운트, x가 아닌 카운트를 모두 초기화한다.

for문을 나와 리스트의 길이를 반환한다. 

소스코드) 

* 1차) 실패 

def solution(s):
    x = ""
    start_Idx = 0
    x_Cnt = 0
    x_Not_Cnt = 0
    answer_list = []
    for i in range(0, len(s)):
        if x == "":
            x = s[i]
            start_Idx = i
            x_Cnt += 1
            continue

        if x == s[i]:
            x_Cnt += 1
        else :
            x_Not_Cnt += 1

        if x_Cnt == x_Not_Cnt:
            answer_list.append(s[start_Idx: i+1])
            x_Cnt = 0
            x_Not_Cnt = 0
            x = ""

    return len(answer_list)

* 2차) 성공

def solution(s):
    x = ""
    start_Idx = 0
    x_Cnt = 0
    x_Not_Cnt = 0
    answer_list = []
    for i in range(0, len(s)):
        if x == "":
            x = s[i]
            start_Idx = i
            x_Cnt += 1
            continue

        if x == s[i]:
            x_Cnt += 1
        else :
            x_Not_Cnt += 1

        if x_Cnt == x_Not_Cnt:
            answer_list.append(s[start_Idx: i+1])
            x_Cnt = 0
            x_Not_Cnt = 0
            x = ""

    if x_Cnt != 0 or x_Not_Cnt != 0:
        answer_list.append(s[start_Idx: i + 1])

    return len(answer_list)

리뷰) 

뭔가 중간중간 아쉽게 놓치는 부분이 있다. 그런 부분은 처음부터 체크할 수 있게 문제를 꼼꼼히 읽어야 겠다 .

문제설명 4번째꺼를 처음에 처리해주지 못해서 실패! 이런거 빠뜨리면 안된다고

📌 파이썬 으로 풀이

📌 문제 링크 :

📌 문제 설명 :

문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다.
예를 들어, s="banana"라고 할 때,  각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다.

• b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다.
• a는 자신보다 두 칸 앞에 a가 있습니다. 이는 2로 표현합니다.
• n도 자신보다 두 칸 앞에 n이 있습니다. 이는 2로 표현합니다.
• a는 자신보다 두 칸, 네 칸 앞에 a가 있습니다. 이 중 가까운 것은 두 칸 앞이고, 이는 2로 표현합니다.

따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.

문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.

📌 제한 사항

• 1 ≤ s의 길이 ≤ 10,000
  • s은 영어 소문자로만 이루어져 있습니다.

📌 입출력 예

추측 의사코드) 

1) 방법

1. 전체 문자열을 잘라 배열을 만든다

2. for문을 전체 문자열을 돌린다.

3. 인덱스 이전의 길이 값을 구한다.

4. 가장 가까운 값의 인덱스를 저장할 변수same_Idx를 정의한다.

5. 길이 값을 -2하여 0부터 지금 인덱스 전까지 for문을 돌려 현재 인덱스와 동일한 문자열의 마지막 인덱스를 받아 same_Idx에 저장한다.

6. 만약 동일한 문자열이 없다면 same_Idx에 -1 저장한다. 

6. for문을 나와 만약 same_Idx = -1

   - 이라면 : 반환할 리스트에 -1을 저장

   - 아니라면 : 현재 인덱스에서 동일한 문자열 인덱스를 뺄셈하여 그 값을 리스트에 저장

7. for문을 나와 저장된 리스트를 반환한다.

소스코드) 

* 1차) 실패 : 정확성 10

def solution(s):

    answer_List = []

    for i in range(0,len(s)):
        same_Idx = 0;
        if i == 0:
            answer_List.append(-1)
            continue
            
        for x in range(0,i):
            if s[i] == s[x]:
                same_Idx = x;

        if same_Idx == 0 :
            answer_List.append(-1)
        else :
            answer_List.append(i-same_Idx)

    return answer_List

* 2차) 성공 : 메모리: 11 MB, 시간: 3600.46 ms 

def solution(s):

    answer_List = []
    for i in range(0, len(s)):
        same_Idx = 0
        cnt = 0
        if i == 0:
            answer_List.append(-1)
            continue
            
        for x in range(0, i):
            if s[i] == s[x]:
                cnt += 1
                same_Idx = x

        if same_Idx == 0 and cnt == 0:
            answer_List.append(-1)
        else:
            answer_List.append(i - same_Idx)

    return answer_List

리뷰) 

1차에서 동일한 문자열이 인덱스를 기본 0으로 잡아주고 있어서 동일한 문자열 인덱스가 0일때랑 동일한 문자열이 없을 때를 구분 못함. 그것을 수정해주니 성공.

근데 테스트 5,7,9,11,30 이 3000ms 이상이 나온다. 더 개선해봐야겠다. 

📌 파이썬 으로 풀이

📌 문제 링크 :

📌 문제 설명 :

숫자로 이루어진 문자열 t와 p가 주어질 때, t에서 p와 길이가 같은 부분문자열 중에서, 이 부분문자열이 나타내는 수가 p가 나타내는 수보다 작거나 같은 것이 나오는 횟수를 return하는 함수 solution을 완성하세요.

예를 들어, t="3141592"이고 p="271" 인 경우, t의 길이가 3인 부분 문자열은 314, 141, 415, 159, 592입니다. 이 문자열이 나타내는 수 중 271보다 작거나 같은 수는 141, 159 2개 입니다.

📌 제한 사항

• 1 ≤ p의 길이 ≤ 18
• p의 길이 ≤ t의 길이 ≤ 10,000
• t와 p는 숫자로만 이루어진 문자열이며, 0으로 시작하지 않습니다.

📌 입출력 예

추측 의사코드) 

1. 받은 문자열 t를 먼저 p의 길이따라 먼저 잘라 배열로 만든다

2. 결과값 카운트를 받을 변수 cnt를 하나 선언한다.

3. 그 배열을 for문으로 돌린다.

4. t 인덱스마다의 값과 p를 비교해야하는 데 둘다 숫자형태의 "문자열"이므로 숫자로 변환한다.

5. 배열의 인덱스 하나 값이 p 값보다 작거나 같다면

    - cnt값을 올린다

6. cnt를 반환한다. 

+ 길이가 같은 부분 문자열이라는 것을 주의

소스코드) 

* 1차) 성공 : 메모리: 10.3 MB, 시간: 0.05 ms

def SmallSubstring(t, p):

    cnt = 0
    # len 길이 구하는 식
    unit = len(p)
    # range(min, max, gap) gap은 숫자들 사이에 차이를 두고 만든다.
    # 한줄 포문 앞에 실행문 두고 뒤에 for문을 둔다.
    # 리스트 표현식에는 리스트 안에 if문과 for을 넣을 수 있음
    b = [t[i:i+unit] for i in range(0,len(t))]
    print(b)

    for one in b:
        if int(one) <= int(p) and len(one) == len(p):
            cnt += 1

    return cnt

리뷰) 

한줄 for문과 리스트 표현식을 배운 문제. 파이썬에서 별도로 문자열을 자르는 메소드가 있는지 찾아보다가 알게됬다.

리스트 표현식이 특히 신기했다. 리스트 안에 바로 for문이나 if문을 넣을 수 있다니!!!

확실히 간결하긴 한데 가독성 적으로는 아직 익숙하지 않아서 그런가 잘 눈에 안들어온다 ㅎㅎ 

하나 추가하자면 b에 넣어준 for문 방식으로 하면 마지막은 길이가 모자란 값이 들어가고 그 값은 길이가 같은 부분 문자열이 아니므로 카운트 대상에서 제외한다. 

📌 파이썬으로 풀이

📌 문제 링크 :

📌 문제 설명 :

위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

📌 제한 사항

• 삼각형의 높이는 1 이상 500 이하입니다.
• 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

📌 입출력 예

추측) 

DP 알고리즘에 대한 영상을 보면서 이미 힌트를 봐버림 ㅠ

새로운 2차원 배열을 사용하여 반복되는 패턴에 따라 더한 값을 넣어 최종적으로 마지막 인덱스 배열에서 최대값을 출력하면 될 듯 하다. 반복될 작은 패턴 부분을 먼저 설명하자면 꼭대기 숫자를 그대로 새로운 트라이앵글 배열 같은 위치에 저장하고 다음 행의 왼쪽 숫자를 더해 새로운 트라이 앵글 배열에서의 왼쪽 숫자 위치에 저장, 오른쪽 숫자도 동일한 방식으로 저장하는 패턴이 돌아가게 하면 될 듯하다. 

겹치는 부분에 대해서는 더 큰 숫자가 남게 해서 더한 결과가 최대값들만 저장되게 하여, 이전 경우의 수 중 가능성이 없는 것은 먼저 배제하고 가장 높은 숫자가 될 수 있는 결과만을 가지고 패턴을 반복하는 방식으로 진행.

이렇게 함으로써 반복되는 식을 줄이고, 경우의 수를 줄이는 방식으로 하면 될거 같다. 

소스코드) 

* 1차) 실패 : 장렬한 올 런타임 에러

def solution(triangle):
    
    new_Triangle = [[0], [0, 0], [0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0, 0]]

    for idx in range(0, len(triangle)-1) :
        if idx == 0 :
            # 시작값은 바로 넣어주기
            new_Triangle[0] = triangle[0]

        for idx2, value2 in enumerate(triangle[idx]):
            #중간숫자
            first_Int = new_Triangle[idx][idx2]

            #왼쪽
            plus_Int1 = triangle[idx+1][idx2]
            sum1 = first_Int + plus_Int1
            if new_Triangle[idx+1][idx2] < sum1 :
                new_Triangle[idx+1][idx2] = sum1

            #오른쪽
            plus_Int2 = triangle[idx+1][idx2+1]
            sum2 = first_Int + plus_Int2
            if new_Triangle[idx+1][idx2+1] < sum2 :
                new_Triangle[idx + 1][idx2 + 1] = sum2
                
    # 마지막 결과중에서 가장 큰 값 리턴
    return max(new_Triangle[len(new_Triangle)-1])

* 2차) 바보다. 다양한 높이의 배열이 들어올건데 예시만 생각하고 배열을 하드코딩

def solution(triangle):
    
    # 더해준 값 넣어줄 다차원 배열 만들기
    new_Triangle = []
    for idx in range(0, len(triangle)) :
        list = []
        for idx2 in range(0, len(triangle[idx])) :
            list.append(0)
        new_Triangle.append(list)
        
    # 삼각에서 왼쪽값 오른쪽 값 더해서 다차원 배열에 넣어주기    
    for idx in range(0, len(triangle)-1) :
        if idx == 0 :
            # 시작값은 바로 넣어주기
            new_Triangle[0] = triangle[0]

        for idx2, value2 in enumerate(triangle[idx]):
            #중간숫자
            first_Int = new_Triangle[idx][idx2]

            #왼쪽
            plus_Int1 = triangle[idx+1][idx2]
            sum1 = first_Int + plus_Int1
            if new_Triangle[idx+1][idx2] < sum1 :
                new_Triangle[idx+1][idx2] = sum1

            #오른쪽
            plus_Int2 = triangle[idx+1][idx2+1]
            sum2 = first_Int + plus_Int2
            if new_Triangle[idx+1][idx2+1] < sum2 :
                new_Triangle[idx + 1][idx2 + 1] = sum2
                
    # 마지막 결과중에서 가장 큰 값 리턴
    return max(new_Triangle[len(new_Triangle)-1])

리뷰) 

먼저 힌트를 봐버렸지만 역시 직접 구현하는 것은 또 다른 이야기인 듯 하다. 뭔가 구현하고 보니까 이게 최선이 아닌거 같기도 ㅎㅎㅎ DP에 관련해서는 정말 다양한 방법이 많기 때문에 많은 문제를 풀어보면서 사고를 맞춰나가는 게 중요하다고 한다. 문제를 정말 다양하게 풀어봐야할 듯 하다.

참고 영상: