[programmers] 가장 가까운 같은 글자, H-Index

🧩 Algorithm/프로그래머스

[programmers] 가장 가까운 같은 글자, H-Index

nerowiki 2024. 4. 24. 19:44

728x90

💡 오늘의 학습 키워드
- 가장 가까운 같은 글자
- H-Index

🥉 가장 가까운 같은 글자

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/142086

문제 설명

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

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

따라서 최종 결과물은 [-1, -1, -1, 2, 2, 2]가 됩니다.
문자열 s이 주어질 때, 위와 같이 정의된 연산을 수행하는 함수 solution을 완성해주세요.

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

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

주어진 문자열의 글자들을 순회하고 해당 글자와 이전 글자를 비교하는 문제였습니다.
그리고 이전에 나온 동일한 문자의 위치를 찾아야 합니다.
처음에는 stack을 사용하는 풀이도 생각해보았지만 이전에 나온 동일한 문자의 위치를 찾아야 하므로,
stack보다는 문자의 위치를 기록할 수 있는 자료구조를 사용해야 합니다.

생각할 수 있는 아이디어는 prev 변수를 사용해 순회하거나 딕셔너리나 해시 테이블을 활용하는 것이었습니다.
저는 prev를 사용하면 조금 더 간단하게 해결할 수 있을 거라 판단했습니다. 문제 해결과정은 다음과 같습니다.

주어진 문자열을 순회합니다.
현재 글자 이전 값들을 순회합니다.
현재 글자와 비교하여 현재 글자와 일치하는 가장 가까운 글자 인덱스를 저장합니다.
현재 글자와 일치하는 값과 현재 글자 사이 거리를 저장하고 같은 글자가 없다면 -1을 리턴합니다.

딕셔너리를 통한 풀이나 prev 변수를 통한 풀이나 시간 복잡도는 동일하지만
일반적인 경우 prev 변수를 활용한 풀이가 메모리 효율이 더 좋다고 판단했습니다.

물론 문자열에 포함된 고유 문자 수가 매우 작을 경우 딕셔너리 풀이가 더 효율적일 수 있습니다.
두 풀이 방식 모두 시간복잡도는 O(n)으로 동일하므로 자신있는 방식으로 풀이를 진행해보았습니다.

💡 내가 해결한 방식은?

def solution(s):
    answer = []
    
    for i in range(len(s)):
    	# 이전 값 중 같은 글자 저장
        prev = -1
        # 현재 글자 이전 값들 순회
        for j in range(i):
            # 현재 글자와 가장 가까운 같은 글자의 인덱스 저장
            if s[i] == s[j]:
                prev = j
                
        answer.append(i - prev if prev != -1 else -1)
        
    return answer

🥈 H-Index

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42747

문제 설명

H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다.
어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다.
위키백과1에 따르면, H-Index는 다음과 같이 구합니다.

어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고
나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다.

어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때,
이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요.

제한 사항
1. 과학자가 발표한 논문의 수는 1편 이상 1,000편 이하입니다.
2. 논문별 인용 횟수는 0회 이상 10,000회 이하입니다.

문제 회고

💡 어떤 문제가 있었고, 나는 어떤 시도를 했는지 그리고 새롭게 안 사실은 무엇인지

문제 자체는 구현으로도 해결이 가능했지만 집중하지 않으면 혼동되는 요소가 존재했던 문제였습니다.
문제 해결 과정은 다음과 같습니다.

최대 논문의 인용 횟수만큼 순회합니다.
해당 인용 횟수 이상 인용된 논문 수('c_num')를 계산합니다.
해당 인용 횟수 이상 인용된 논문 수('c_num')의 최종 값이 해당 인용 횟수보다 크거나 같은 경우 max 값을 갱신합니다.

설명을 하게되면 복잡하게 들리는 문제이므로 직접 과정을 손으로 그려보아야 실수 없이 풀 수 있는 문제였습니다.
정렬 없이 풀게 된다면 시간복잡도가 n^2이므로 입력 데이터 크기에 제한을 받게 됩니다.
따라서 sort 를 통해 시간 복잡도를 nlogn으로 정렬한 후 논문 리스트를 정렬한 후 순회 비교 해주어야 합니다.

💡 내가 해결한 방식은?

시간 복잡도 O(n^2) 방식의 풀이

def solution_1(citations):
    # citations : 과학자가 발표한 논문의 인용 횟수
    # 논문 n 편 중 h번 이상 인용된 논문이 h편 이상 나머지 h편 이하
    # h의 최댓 값? -> H-Index

    max_h = 0
    
    for i in range(1, len(citations) + 1):
        c_num = 0
        for citation in citations:
            if citation >= i:
                c_num += 1
                
        if c_num <= i:
            max_h = max(max_h, c_num)
        
    return max_h

시간복잡도 O(nlogn) 방식의 풀이

def solution_2(citations):
    citations.sort(reverse=True)
    
    for h in range(len(citations)):
        if h >= citations[h]:
            return h
    return len(citations)

map과 enumerate 메소드를 이용한 풀이

def solution_3(citations):
    citations.sort(reverse=True)
    # [3, 0, 6, 1, 5]일 경우
    # 1 3 / 2 0 / 3 6 / 4 1 / 5 5 튜플들에서 min 값은 최소한의 논문 인용 횟수입니다.
    # 그중 max 값을 answer에 저장
    answer = max(map(min, enumerate(citations, start=1)))
    return answer

✍️ TIL

기본적으로 풀이는 먼저 구현에 성공하고 시간 복잡도를 테스트한 후 새로운 자료구조를 고민하는 과정이 반복해야 한다.
풀이 이후에는 좀 더 효율적인 코드와 최대로 추상화된 숏코드 총 3개를 확인하고 모두 이해한 후 넘어가기.