미정

문제 설명

나의 풀이

def solution(phone_book):
    phone_book.sort()
    for i in range(len(phone_book)-1):
        if phone_book[i]==phone_book[i+1][:len(phone_book[i])]:
            return False
    return True

• phone_book 을 우선 정렬한 후에(문자열 정렬이기 때문에 절대적인 크기가 아닌 사전 정렬 방식으로 정렬한다.)
• phone_book[i] 가 phone_book[i+1]의 앞부분과 같으면 바로 false를 반환하게끔 코드를 짰다. 
• 여기 중요한 점은 일단 정렬이 됐다면 첫 번째부터 탐색하는데, 그 뒤 바로 인접한 전화번호의 접두어가 되는지 비교한다.
• 이때 인접한 전화번호만 비교하면 되는 이유는 사전 방식으로 문자열을 이미 정렬했기 때문이다.
• 예를 들어 12, 139, 160 식으로 정렬이 되기 때문에 12와 139를 비교했을 때 12가 139의 접두어가 되지 못한다면 12는 그 다음 전화번호인 160의 접두어도 마찬가지로 되지 못하기 때문에 비교할 필요가 없다.

## 정렬 예시 ##
i = ["12","57", "5", "9", "123","1235","567","88"]
i.sort()
print(i)

# 출력 #
>> ['12', '123', '1235', '5', '567', '57', '88', '9']

* 해시 맵을 사용한 풀이

def solution(phone_book):
    answer = True
    hash_map = {}
    for phone_number in phone_book:
        hash_map[phone_number] = 1
    for phone_number in phone_book:
        temp = ""
        for number in phone_number:
            temp += number
            if temp in hash_map and temp != phone_number:
                answer = False
    return answer

1. Hash map을 만든다

2. 접두어가 Hash map에 존재하는지 찾는다

3. 접두어를 찾아야 한다 (기존 번호와 같은 경우 제외)

1) HashMap 만들기

• HashMap이란 Key-Value의 Pair를 관리하는 클래스이다.
• Key는 phone_number / Value는 1로 설정한다.
• 기본적으로 Hash map은 위와 같이 만들어주는게 정석이다.
• 여기서 Value == 1의 의미는 숫자가 1개 존재한다는 것이다.

2) 모든 전화번호 Hashing 하기 (Hash Map에 추가하기)

• 'Hashing을 한다'라고도 표현하는데, HashMap에 전화번호를 전부 추가해보자. 
• 위 코드의 동작 방식은 다음 예시로 설명하는 것이 가장 쉽게 이해가 가능할 것이다.
• Hash Map을 보고 나면 별게 아니다. 이 문제에서는 Key 값으로 전화 번호를 관리하는 전화번호부다.

3) 각 전화번호의 접두어가 HashMap에 존재하는지 확인하기

• 존재하는 모든 전화번호가 HashMap에 등록되었다.
• 이제는 각 전화번호의 접두어가 HashMap에 존재하는지 확인하는 것이다.
• Length 1~전체 길이 - 1 까지의 substring을 떼어서, HashMap에 존재한다면, 접두어가 존재한다고 확인할 수 있다.

* zip과 startwith를 사용한 풀이

def solution(phoneBook):
    phoneBook = sorted(phoneBook)

    for p1, p2 in zip(phoneBook, phoneBook[1:]):
        if p2.startswith(p1):
            return False
    return True

• sort를 해준후 zip으로 본인(p1)과 본인의 다음값(p2)을 묶음 처리해준다.
• for문을 돌면서 startwith 함수를 이용해 p2가 p1으로 시작하는지 검사한다.

- zip( )

• zip 함수는 여러 개의 iterable자료형의 크기가 동일할 때 사용한다. ( 크기가 다를경우 순서대로 생성후 None값 삽입)
• iterable 자료형의 각각의 요소를 나눈 후 순서대로 묶어서 요소 개수만큼 새로운 iterable 자료형을 생성
• -for문과 사용을 많이 한다
  ex)    for x, y in zip(range(10), range(10)) :

- startswith( )

• startswith는 문자열이 특정문자로 시작하는지 여부를 알려줌 (true, false 반환)

문제 설명

나의 풀이

def solution(s):
    answer = []
    s = s[2:-2]
    s = s.split("},{")
    s.sort(key = len)
    for i in s:
        ii = i.split(',')
        for j in ii:
            if int(j) not in answer:
                answer.append(int(j))
    return answer

• 맨앞 '{{'와 맨뒤 '}}'를 잘라준다. 왜냐, 매개변수 문자열 s가 다음과 같은 형태이기 때문>>  "{{20,111},{111}}"  << 
• 그럼 자른 후, s는 20,111},{111 형태며,
• 다시 '},{'을 기준으로 split하면 괄호 문자가 모두 사라진다.
• s는 현재 ','를 포함한 문자열 원소들이다. 
• 이에 대한 결과값은 s가 "{{4,2,3},{3},{2,3,4,1},{2,3}}"인 경우, [['3'], ['2', '3'], ['4', '2', '3'], ['2', '3', '4', '1']]와 같은 배열이다.
• 이 중 가장 긴 배열을 값을 int로 변경하면 끝일 것처럼 생각이 들지만 원소들의 순서가 맞지 않다.
• 이중 for을 사용하여 answer 에 요소가 없는 경우, answer에 해당 값을 int으로 변경하여 추가하고 추가한 후 내부의 for문을 break하는 방식으로 계속적으로 추가해야만 원래 원소들의 순서를 찾아낼 수 있다.
• answer 배열에 차례대로 append해준다.

다른 사람 풀이

def solution(s):

    s = Counter(re.findall('\d+', s))
    return list(map(int, [k for k, v in sorted(s.items(), key=lambda x: x[1], reverse=True)]))

import re
from collections import Counter

정규표현식을 이용한 풀이다.

findall메소드는 정규식과 매치되는 모든 문자열을 리스트로 돌려준다. 정리하면, re 모듈의 findall을 이용해서 '하나 혹은 그 이상 연결된 숫자' 를 의미하는 정규 표현식 \d+ 을 적용하여 숫자들을 모두 찾아낸다. 그리고 collectioins 모듈의 Counter 클래스를 이용해서 숫자들이 나타난 횟수를 카운팅 한다.

• s = Counter(re.findall('\d+', s))의 결과로 Counter({'2': 4, '1': 3, '3': 2, '4': 1})이 나오고,  
• s를 카운트가 높은 순서대로 내림차순 정렬한 후, key 값인 숫자만 뽑아 int형 리스트로 만든다.
• list(map(int, [k for k, v in sorted(s.items(), key=lambda x: x[1], reverse=True)]))
• 이 풀이는 Counter를 이용해 단 한 줄로 숫자들을 카운팅 했다. 
• 값을 카운트해야 할 땐 Counter를 이용하면 코드가 간략해진다는 것을 잊지 말자!!!

문제 설명

1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다.
2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다.
3. 그렇지 않으면 J를 인쇄합니다.

나의 풀이

def solution(priorities, location):
    answer = 0
    from collections import deque

    d = deque([(v,i) for i,v in enumerate(priorities)])
    while len(d):
        item = d.popleft()
        if d and max(d)[0] > item[0]:
            d.append(item)
        else:
            answer += 1
            if item[1] == location:
                 break
    return answer

이 문제는 보자마자 큐를 사용해야겠다는 생각이 들었다. 파이썬에서는 큐를 사용할 때는 collections 라이브러리의 deque를 사용한다. 흔히 '덱' 이라고 읽는데 사실 deque은 queue와 stack을 합쳐놓은 개념의 자료구조이다.

뭐 아무튼.. deque는 스택과 같이(파이썬에서 리스트) append(), pop() 함수로 deque의 마지막에 데이터를 삽입, 삭제하고, appendleft() popleft() 로 deque의 앞 쪽에 데이터를 삽입, 삭제할 수 있다.

priorities = [2, 1, 4, 5]

d = deque([(v, i) for i, v in enumerate(priorities)])

print(d)

>> deque([(2, 0), (1, 1), (4, 2), (5, 3)])

※참고(deque란?)

여기서, 나는 deque를 사용했다. 반복문을 사용해서 가장 먼저 들어온 값부터 체크하였다.

즉 최대값보다 현재값이 작으면 맨뒤에 붙이고 크거나 같다면 순서인덱스만 추가. 현 인덱스가 타겟과 같다면 리턴했다.

deque : append, popleft

 *보통 queue는 선입선출

  *deque는 양방향 큐. 앞, 뒤 양쪽 방향에서 엘리먼트(element)를 추가하거나 제거할 수 있다

• deque.append(item): item을 데크의 오른쪽 끝에 삽입한다.
• deque.appendleft(item): item을 데크의 왼쪽 끝에 삽입한다.
• deque.pop(): 데크의 오른쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
• deque.popleft(): 데크의 왼쪽 끝 엘리먼트를 가져오는 동시에 데크에서 삭제한다.
• deque.extend(array): 주어진 배열(array)을 순환하면서 데크의 오른쪽에 추가한다.
• deque.extendleft(array): 주어진 배열(array)을 순환하면서 데크의 왼쪽에 추가한다.
• deque.remove(item): item을 데크에서 찾아 삭제한다.
• deque.rotate(num): 데크를 num만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).

문제 설명

나의 풀이

def solution(progresses, speeds):
    answer = []
    while progresses:
        for i in range(len(progresses)):
            progresses[i] += speeds[i]
        count = 0
        while progresses and progresses[0] >= 100:
            progresses.pop(0)
            speeds.pop(0)
            count += 1
        if count >0:
            answer.append(count)
    return answer

• progresses에 speeds를 더할 때마다 100이 넘는지 않은지를 확인한다. 반복문을 통해 모든 작업이 완료될 때까지 작업을 한다.
• progresses 순서대로 배포하기 때문에 첫 번째 요소들부터 100이 넘었다면 pop으로 progresses 배열에서 제거하고 count 를 1 늘린다.
• 이 방법을 계속 반복하여 앞에서부터 100이 넘는 요소들을 빼주는데, 이러다가 100이 넘지 않은 요소가 나타나면 반복을 멈추고, count가 0이 아니고 존재한다면 answer에 append 해준다.
• progresses가 없을 때까지 반복한다.
• 모든 작업이 완료했다면 answer를 출력한다.

스택과 큐에 대한 어느정도 지식이 있어야 한다.

쉽게 그림으로 이해해보면,

큐를 사용한 문제 해결 과정

                 progresses                                     speeds                                      return

progresses[i] += speeds[i] 반복

맨 앞 작업이 100 미만 - > 모든  작업 속도 업데이트(현재 결과 리스트 : [ ])

맨 앞 작업이 100 미만 - > 모든 작업 속도 업데이트(현재 결과 리스트 : [ ])

맨 앞 작업이 100 미만 - > 모든 작업 속도 업데이트(현재 결과 리스트 : [ ])

맨 앞 작업이 100 미만 - > 모든 작업 속도 업데이트(현재 결과 리스트 : [ ])

맨 앞 작업이 100 미만 - > 모든 작업 속도 업데이트(현재 결과 리스트 : [ ])

맨 앞 작업이 100 미만 - > 작업 속도 업데이트(현재 결과 리스트 : [ ])

!!!! 맨 앞 작업이 100 이상 - > 해당 기능 배포 , 큐에서 제거, 배포된 기능 개수 1 증가

!!!!! 맨 앞 작업이 100 이상 - > 해당 기능 배포 , 큐에서 제거, 배포된 기능 개수 1 증가

오늘 배포 가능한 기능 더 이상 없음 결과 리스트에 배포된 기능 개수 추가 (현재 결과 리스트 : [2])

맨 앞 작업이 100 미만 - > 반복문 빠져나와서 progresses[i] += speeds[i] 실행

맨 앞 작업이 100 이상 - > 해당 기능 배포 , 큐에서 제거, 배포된 기능 개수 1 증가

오늘 배포 가능한 기능 더 이상 없음 결과 리스트에 배포된 기능 개수 추가 (현재 결과 리스트 : [2, 1])

작업 큐에 남은 작업 없음, 반복 탈출

문제 설명

1. yellow_hat
2. blue_sunglasses
3. green_turban
4. yellow_hat + blue_sunglasses
5. green_turban + blue_sunglasses

1. crow_mask
2. blue_sunglasses
3. smoky_makeup

나의 풀이

def solution(clothes):
    closet = {}
    answer = 1
    
    # 같은 종류의 옷끼리 묶어서 사전에 저장
    for cloth in clothes:
        if cloth[1] in closet.keys():
            closet[cloth[1]].append(cloth[0])
        else:
            closet[cloth[1]] = [cloth[0]]
    
    # 경우의 수 구하기            
    for value in closet.values():
        answer *= len(value) + 1
    
    # 아무것도 입지 않은 경우 하나 제외
    return answer-1

 ex) output: {'headgear': ['yellow_hat', 'green_turban'], 'eyewear': ['blue_sunglasses']}
     # 위와 같이 딕셔너리가 만들어진다.

•  마지막에 1을 빼주는 이유는 모두 안입은 경우를 제거한다.
• 정리하면 가능한 조합의 수는 headgear 를 두 가지중에 한가지를 입거나 혹은 둘 다 안입거나 (총 세가지)
• 그리고 eyewear 는 한 가지이므로 입거나 혹은 안입거나 (총 두가지)
• 그리고 이것들을 종류를 바꿔서 돌려입기 가능하므로, 조합의 수는 3 * 2 가 된다
• 그러나 모든 종류의 옷을 다 안입은 경우에는, 위장을 한 것이 아니므로 이 경우의 수만 빼주면 된다.

def solution(clothes):
    answer = 1
    dic = {}
    for i in clothes:
        if i[1] in dic:
            dic[i[1]] += 1
        else:
            dic[i[1]] = 1
    for i in dic.keys():
        answer *= dic[i] +1
    answer -= 1

풀이는 똑같은데 이게 더 간단한 느낌..!

문제 설명

나의 풀이

def solution(people, limit):

    people.sort()
    # 시작, 끝 인덱스
    start, end = 0, len(people)-1
    # 보트의 수
    count = 0
    while start <= end:
        # 보트의 수 증가
        count += 1
# 두 명(몸무게가 가장 적은 사람, 몸무게가 가장 많은 사람)을 태우거나
        if (people[start] + people[end] <= limit):
            start += 1
            end -= 1

# 한 명(몸무게가 가장 많은 사람)을 태우기 
        else:
            end -= 1
    return count

1. 핵심은 가장 몸무게가 많이 나가는 사람과 적게 나가는 사람을 계속해서 매칭시켜서 최대한 한번에 태워보내주면 최소값을 찾아줄 수 있다.
2. 먼저 people의 list를 정렬을 해주어야한다. 이후 가장 몸무게가 큰 사람과 가장 작은 사람의 무게를 더해 limit와 비교한 뒤, 작으면 둘다 태우고(두 명(몸무게가 가장 적은 사람, 몸무게가 가장 많은 사람)을 태우거나), 크다면 몸무게가 가장 큰 사람만 태운다.(한 명(몸무게가 가장 많은 사람)을 태운다.)

투 포인토 알고리즘을 사용해 풀어 보았다.

Greedy (탐욕법, 탐욕 알고리즘)

Greedy Algorithm은 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다.

위의 그림에서는 가장 숫자가 큰 요소를 찾는데 있어서 해당 분기점마다 보다 큰 수를 찾는 방식으로 최종 해답을 찾아가고 있다. 순간마다 큰 수를 찾아가면 최종 결과는 12이다. 하지만 실제 전체 숫자 중에서 가장 큰 수는 99이다. 이처럼 전체 문제해결에서의 최적 해답을 찾지는 못한다.

하지만 이러한 단점들을 극복하는 Greedy의 가장 큰 장점은 계산 속도에 있다. 그래서 Greedy 방법이 통하는 몇몇의 문제에서는 최적해를 빠르게 산출해낼 수 있다.

투 포인터 (Two Pointer)

• 배열 안에 있는 값들을 연속해서 더하거나 연산하는 경우에 사용 인덱스를 가리키는 두 개의 변수(포인터)를 선언하여 사용하는 특징이 있어 투 포인터라 불림
• 예를 들어 N개의 숫자가 들어있는 배열이 주어질 때, 부분 집합의 합이 특정 숫자인 M인 경우의 수를 구하는 문제에 적용한다면, 배열의 인덱스를 가리키는 startPointer와 endPointer를 생성한 후 특정 규칙에 의해 각 포인터를 움직여 배열을 탐색해 문제를 해결할 수 있으며, 그 규칙은 다음과 같습니다.1-2) 만약 startPointer의 값이 배열의 길이와 같을 경우 탐색을 종료합니다.2) 위의 세 규칙 중 해당하는 연산이 끝난 후 만약 현재까지의 합이 M과 같다면 답을 +1증가 시킵니다.
• 1-3) 나머지 경우(현재까지의 합이 M보다 작을 경우)에는 합에 startPointer가 가리키고 있는 값을 더한 후 startPointer를 +1 증가시킵니다.
• 1-1) 현재까지의 합이 M보다 크거나 같은 경우 합에서 endPoiner가 가리키고 있는 값을 뺀 후 endPointer를 +1 증가시킵니다.
• 투 포인터를 사용한다면 한 번 답이 될 수 없다고 판명된 이후의 값들을 더 이상 탐색하지 않으므로 시간 복잡도가 O(n)이 되어 완전 탐색에 비해 효율이 훨씬 좋음

문제 설명

문제를 풀기에 앞서,

citations = [6,6,6,6,6,1] 일 때, 이 과학자의 H-index는?

이 질문을 풀어보자. 답은 5이다.
이 예시를 든 이유는 일부 사람들이 h 값을 citaions 리스트 안에 있는 값 중에서 고르려고 하기 때문이다. 
즉, 우리는 H-index의 최댓값과 리스트의 길이의 관계를 고려해서 풀어야 한다.

나의 풀이

def solution(citations):
    citations.sort()
    article_count = len(citations) # 5

    for i in range(article_count): #0~4
        if citations[i] >= article_count-i:
            return article_count-i
    return 0

• if citations[i] >= article_count-i는 "주어진 h번 이상 인용된 논문이 h편 이상"이라는 조건을 그대로 풀어쓴 것이었다.
• citations[i]는 i번 논문이 인용된 횟수이고 article_count - i는 인용된 논문의 개수를 최댓값부터 하나씩 줄여나간 것이다. (최댓값을 찾아야 하므로 가장 큰 값부터 시작)
• 정렬된 citations에서 한칸씩 가다가 그 값이 나머지 길이보다 크거나 같다면 그 편수가 h다.
• 그리고 리스트는 오름차순 정렬된 상태이므로 i번째 이후는 모두 i번째보다 큰 값을 가질 것이다.

 
https://www.ibric.org/myboard/read.php?Board=news&id=270333

신박한 풀이

def solution(citations):
    citations.sort(reverse=True)
    answer = max(map(min, enumerate(citations, start=1)))
    return answer

문제 설명

문제를 풀기전, 최소공배수를 구하는 방법에 대해 알아보자.

간단한 예로 최소공배수를 구해보자.

def ex_gcd(a, b): 	# a=18, b=24라고 가정
    A = a
    B = b
    while b > 0:
        a , b = b, a % b
    gcd = a 	# 최대공약수
    return A*B // gcd

위의 예시는 최소공배수를 구하는 문제이다. 18과 24의 최소공배수를 구해보자.

밑의 그림과 같이 구하면 되고, 최소공배수는? 2*3*3*4를 해서 72가 나올 것이다.

또 하나, 최대공약수는 6이 나올 것이다.

규칙을 찾았는가?

바로 최소공배수는 최소공배수를 구할 두 수를 서로 곱하여 최대공약수로 나누면 최소공배수가 된다는 것이다.

즉, 18 과 24를 서로 곱하여 나온 수를 최대공약수(6)로 나누면 최소공배수(72)가 나온다.

본 문제에 대한 나의 풀이

def solution(arr):
    from math import gcd                           
    answer = arr[0]                                 
    for num in arr:                                
        answer = answer*num // gcd(answer, num)     
    return answer

1.  최대공약수를 구하는 gcd() 함수를 import 한다. ((gcd() 함수는 두 수의 최대공약수를 구해주는 함수))

2. answer을 arr[0]으로 초기화

3. 반복문을 처음부터 끝까지 돈다.

4. arr[0], arr[1])의 최소공배수를 구한 후 answer에 저장

5. 4번에서 구한 최소공배수, arr[2])의 최소공배수를 구한 후 answer에 저장

6. 모든 배열을 돌면서 최소공배수를 구하고, 저장하고 하는 방식을 진행 ((최소공배수 = (x*y) / gcd(x,y))

정리하자면 이렇다.

• 최소공배수를 계속해서 answer에 저장시켜 answer와 arr[index]를 통해 계속해서 최소공배수를 구해야 함
• gcd() 함수는 두 수의 최대공약수를 구해주는 함수
• // 연산자는 몫만 구하는 연산자