미정

문제 설명

문제 이해

일단 문제 이해부터 고난이었다.

응? 왜 처음 7이 다리를 건널 때 2초가 걸리지..?

보니깐 문제가 약간 불친절하기도 하다. 그래서 문제에 부가 설명을 하자면,

bridge_length의 값이 2인 것은 다리의 길이가 2인 것이고,

다리를 1만큼 건널 때 1초가 소요되는 것이다. 음 말로 설명하자니 그래도 이해가 안간다....

그래서 그림을 그려보니 확실히 이해가 간다.!! 

그럼 이제 문제를 풀어보자.

나의  풀이

> 첫 번째 풀이

def solution(bridge_length, weight, truck_weights):
    
    answer = 0
    bridge = [0 for _ in range(bridge_length)]
    
    while bridge:
        answer += 1
        bridge.pop(0)
        if truck_weights:
            if sum(bridge) + truck_weights[0] <= weight:            
                t = truck_weights.pop(0)
                bridge.append(t)
            else:
                bridge.append(0)
                 
    return answer

트럭이 다리를 지나는 과정을 answer+=1을 통해 경과시간 계산

• answer : 경과시간
• bridge : 다리 길이와 같은 길이의 값이 0으로 된 리스트 생성
• bridge 리스트 안 (즉 다리 위에 있느 트럭의 총 무게)과 다음 대기열에 있는 트럭 무게가 다리가 감당할 수 있는 총 무게 (weight) 을 넘지 않는 조건을 만족하면 다음 트럭을 리스트에 추가한다
• 만족을 하지 못한다면 0을 추가하여 다리의 길이를 유지
• 트럭의 대기열의 길이가 0이 되면 내부 반복문 종료
• bridge 리스트의 길이가 0이 되면 반복문 종료후 경과시간 (answer) 리턴

* 시간 초과로 실패

> 두 번째 풀이

from collections import deque

def solution(bridge_length, weight, truck_weights):

    bridge = deque(0 for _ in range(bridge_length))
    truck_weights = deque(t for t in truck_weights)
    answer = 0
    bridge_weight = 0
    
    while bridge:
        answer += 1
        bridge_weight -= bridge.popleft()
        if truck_weights:
            if bridge_weight + truck_weights[0] <= weight:
                truck = truck_weights.popleft()
                bridge.append(truck)
                bridge_weight += truck
            else:
                bridge.append(0)

    return answer

• 가상의 다리 bridge를 리스트 형태로 만들어서 실제로 트럭이 지나간다고 생각하고 문제를 풀었더니 더 쉽게 해결할 수 있었다.
• bridge 가장 앞 쪽이 pop해서 사라지고 뒤에 하나가 붙는 방식으로 생각하면 자연스럽게 트럭이 이동하는 모습을 상상할 수 있다.
• 현제 다리 위의 무게와 다음 트럭의 무게를 비교해서 무게 한도를 넘지 않으면 트럭을 올려주면 된다.
• 트럭이 다 넘어가고 나면 천천히 pop에 의해서 bridge의 요소들이 하나씩 빠져 나가고 결국 트럭이 모두 지나간 형태가 된 후 종료된다.

처음 문제를 풀 때는 bridge_weight변수를 따로 두고 무게를 계산하지 않았다.

sum(brige) + truck_Weights[0] 으로 매번 sum을 사용해서 무게를 측정하였더니 시간이 많이 걸렸고 테스트5번에서 시간 초과가 나왔다. 매번 O(n) 만큼의 시간이 추가되는 것이다. 보통의 경우 sum(list)가 많은 시간을 소요하지 않아서 별 생각없었는데, 주의해야 한다는 것을 배웠다.

bridge_weight 라는 변수를 두고 bridge_weight + truck_weights[0] <= weight 이렇게 바로 계산을 진행하니 시간 초과를 해결하고 문제를 풀 수 있었다. 

문제 설명

나의 풀이

def solution(numbers):
    
    numbers_str = [str(num) for num in numbers]                
    numbers_str.sort(key=lambda x: x*3, reverse=True)       

    return str(int(''.join(numbers_str)))

중요 포인트

• str로 형 변환 후, 사전 값으로 배열을 정렬한다.
• 여기서 사전 값으로 정렬이 된다면, [6, 10, 2]의 경우 정렬을 하면 [6, 2, 10]으로 정렬이 된다.
• sort()의 기본 정렬 기준은 오름차순이다. reverse = True 전의 sort된 결과값은 10, 2, 6이다.
• 이를 reverse = True를 통해 내림차순 해주면 6,2,10이 된다. 이것을 ‘‘.join(num)을 통해 문자열을 합쳐주면 된다.
• str로 변경한 숫자에 3을 곱한 값으로 재정렬한다. => 3을 곱하는 이유는 밑에 설명
• 반환 해줄 때, int로 변환을 해준 후 다시 str로 변경한다.
• int로 변환한 뒤, 또 str로 변환해주는 이유?
  • 모든 값이 0일 때(즉, ‘000’을 처리하기 위해) int로 변환한 뒤, 다시 str로 변환한다.
  • 정리하면, 마지막에 문자열을 -> 정수로 -> 다시 문자열로 반환하는 이유는 '00'을 '0'으로 반환하기 위함이다.!!
  • 이 과정만 추가하면 11번 케이스를 통과한다.

3을 곱하는 이유는 2번째 예시를 풀 때 이유를 알게 될 것이다.

2번 째 예시인 [3, 30, 34, 5, 9]을 계산할 때 문자열로 바꾸고 사전값으로만 정렬을 한다면 [9, 5, 34, 30, 3] 이렇게 정렬된다. 하지만 가장 큰 수가 될려면 마지막 3이 30보다 앞에 와야한다.

그래서 

number는 1000이하의 숫자이므로 최대값을 생각해 3을 곱해줬고, 3을 곱하게 되면 [999, 555, 343434, 303030, 333] 이렇게 될 것이다. 여기서 정렬을 하게 되면 [999, 555, 343434, 333, 303030]이 된다.

문제 설명

나의 풀이

def solution(record):
    answer = []
    dic = {}
    
    for sentence in record:
        sentence_split = sentence.split()
        if len(sentence_split) == 3:
            dic[sentence_split[1]] = sentence_split[2]
            
    for sentence in record:
        sentence_split = sentence.split()
        if sentence_split[0] == 'Enter':
            answer.append('%s님이 들어왔습니다.' %dic[sentence_split[1]])
        elif sentence_split[0] == 'Leave':
            answer.append('%s님이 나갔습니다.' %dic[sentence_split[1]])
            
    return(answer)

문제를 풀기 전 살펴봐야 하는 것이 있다.

▶ 모든 유저는 [유저 아이디]로 구분한다. 즉, 유저의 "uid"는 변경할 수 없는 고유값이어야 한다.
▶ "닉네임"은 변경이 가능한 값이다.
▶ 닉네임 변경과 관련한 안내문은 나타나지 않는다.
▶ 닉네임을 변경하면 기존에 채팅방에 있던 메시지의 닉네임도 모두 변한다.
▶ 닉네임은 중복이 가능하지만 uid는 고유값이기 때문에 중복될 수 없다.

1. 따라서 알고리즘을 구현하기 전에 Dictionary 형태로 uid와 닉네임을 묶어두면 다루기 편하겠다고 생각했다.
2. uid가 고유값이기 때문에 record 리스트 내의 모든 uid를 닉네임과 묶는다면, 중복되는 닉네임도 구분이 가능했다.
3. 또한 닉네임 변경 안내문을 출력할 필요가 없으므로 Dictionary 값에 각각의 값을 저장하고 출력하기만 하면 됐다.
4. 그리고 record 리스트가 시계열 순으로 등록되어 있기 때문에, for문을 사용해서 Dictionary 값에 계속해서 저장해 나가면 이전의 닉네임을 삭제하고 변경한 닉네임을 key값에 저장하는 것이 가능했다.

• 5번째 코드를 보면 Dictionary에 데이터를 저장하는 코드를 먼저 구현했다.
• 'Leave'의 경우 닉네임 변경과 관련된 내용이 없기 때문에 'Enter'와 'Change'에 해당하는 값만 조정했다. (len(sentence_split == 3)

Dictionary에 저장된 값을 확인하면 다음과 같다.

{'uid1234': 'Prodo', 'uid4567': 'Ryan'}

출력 값에서 알 수 있듯이 각각의 고유 uid에 해당하는 닉네임이 딕셔너리 형태로 저장되었다.
주어진 배열 record가 시계열로 저장된 것이기 때문에 위와 같은 코드로 구현할 수 있었다.
위와 같이 구현한다면 각각의 uid가 가진 최종 닉네임 값이 Dictionary에 저장된다.

!! 최종적으로 변경된 아이디가 화면에 출력되면 되기 때문에 닉네임이 'Change'되는 과정은 고려하지 않아도 된다.

다른 사람 코드 

def solution(record):
    answer = []
    namespace = {}
    printer = {'Enter':'님이 들어왔습니다.', 'Leave':'님이 나갔습니다.'}
    for r in record:
        rr = r.split(' ')
        if rr[0] in ['Enter', 'Change']:
            namespace[rr[1]] = rr[2]

    for r in record:
        if r.split(' ')[0] != 'Change':
            answer.append(namespace[r.split(' ')[1]] + printer[r.split(' ')[0]])

    return answer

간결해서 가독성이 높았다.

문제 설명

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

나의 풀이

import heapq

def solution(scoville, k):
    heap = []
    for num in scoville:
        heapq.heappush(heap, num)
    mix_cnt = 0
    while heap[0] < k:
        try:
            heapq.heappush(heap, heapq.heappop(heap) + (heapq.heappop(heap) * 2))
        except IndexError:
            return -1
        mix_cnt += 1
    return mix_cnt

힙 문제라고 명시되어 있어서 힙을 사용했다. 파이썬에서 힙은 heapq 라이브러리를 사용한다.

heapq는 일반적인 리스트와 다르게, 가지고 있는 요소를 push, pop 할때마다 자동으로 정렬해주는 녀석이다.

따라서, 앞서 문제가 되었던 정렬 비용을 감소시킴으로써 효율성 이슈를 해결했다.

• (4) heapq로 사용할 리스트를 초기화한다.
• (5~6) 기존 리스트에 있던 요소들을 heapq에 넣어준다. heappush 라는 메소드를 이용한다.
• 맨 앞의 요소를 가져올때 heappop 메소드를 이용한다는 사실을 제외하고 나머지는 똑같다.

간단히 heappop() 으로 힙에 데이터를 뺄 수 있고, heappush() 으로 데이터를 넣을 수 있다.

그리고 heapify()로 리스트를 힙으로 만들 수 있다. (오름차순 정렬과 비슷)

힙(Heap)이란?

• 힙은 최소 힙과 최대 힙이 있는데 최소 힙은 루트 노드에 최솟값이 있는 것이고, 최대 힙은 루트 노드에 최대값이 있는 것이다.
• 파이썬의 heapq에서는 최소힙만 지원된다. (다행히 이 문제는 최소힙을 이용하는 문제이다.)
• 힙의 루트 노드는 0번 인덱스이다. 즉, 최소값이 0번 인덱스에 존재하는 것이다.
• 그렇기 때문에 위 문제를 보면 최소 K 이상이 되는지 확인하려면 최소값인 루트노드. 0번 인덱스만 확인하면 된다.
• 문제의 조건에서 모든 음식의 스코빌 지수를 K이상으로 만들 수 없는 경우 -1을 return 한다고 했기 때문에 scoville에 음식이 단 하나 남았는데도 scoville 지수가 K보다 작다면 -1을 리턴한다.
• 가장 작은 두 값을 찾기 위해 heappop()을 두 번 수행한다.
• 그리고 num1 + num2 * 2 를 계산해서 heappush로 다시 넣어준다.
• 이 과정이 수행되면 count를 1씩 증가시킨다

문제 설명

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

+4+1-2+1 = 4
+4-1+2-1 = 4

• deque를 이용한 BFS 풀이

from collections import deque
def solution(numbers, target):
    answer = 0
    queue = deque()
    n = len(numbers)
    queue.append([numbers[0],0])
    queue.append([-1*numbers[0],0])
    while queue:
        temp, idx = queue.popleft()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer

1. 이진 트리의 형태로 구성될 수 있고, 모든 노드를 말단까지 탐색 한 후 target에 만족하는 값이 되는지를 검사해야한다.

따라서 BFS를 사용했다. (DFS도 사용 가능)

2. 다음에 계산할 값을 각각 +, -하고 2개의 노드를 생성해 queue에 담아준다.

# stack을 이용한 dfs여도 마찬가지! 
def solution(numbers, target):
    answer = 0
    queue = [[numbers[0],0], [-1*numbers[0],0]]
    n = len(numbers)
    while queue:
        temp, idx = queue.pop()
        idx += 1
        if idx < n:
            queue.append([temp+numbers[idx], idx])
            queue.append([temp-numbers[idx], idx])
        else:
            if temp == target:
                answer += 1
    return answer

이 문제는 아래 링크에서 참고하였다!!

출처 https://velog.io/@ju_h2/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-level2-%ED%83%80%EA%B2%9F%EB%84%98%EB%B2%84-BFSDFS

다른 사람 풀이

def solution(numbers, target):
    sup = [0]
    for i in numbers:
        sub=[]
        for j in sup:
            sub.append(j+i)
            sub.append(j-i)
        sup = sub
    return sup.count(target)

def solution(numbers, target):
    if not numbers and target == 0 :
        return 1
    elif not numbers:
        return 0
    else:
        return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])

문제 설명

나의 풀이

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만큼 회전한다(양수면 오른쪽, 음수면 왼쪽).