미정

baekjoon

1 0 -1 -1 2 -1 -1 -1 -1 4 3 -1 -1 7 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

답

string = input()
alphabet = "abcdefghijklmnopqrstuvwxyz"
for i in alphabet:
    print(string.find(i), end = ' ')

find()는 문자열에서 특정 문자가 몇 번째에 위치해 있는지에 대한 값을 반환한다.(문자열에서만 가능하므로 리스트, 튜플과 같은 iterable 자료형에서는 index()함수를 사용해야 한다.)

찾는 문자가 없을 경우 -1을 반환한다.(index()함수는 AttributeError가 발생한다.)

1
1

1

5
54321

15

25
7000000000000000000000000

7

11
10987654321

46

답

n = int(input())
nums = list(map(int, input()))
sum = 0
for i in range(n):
    sum += int(nums[i])
print(sum)

A

65

C

67

0

48

9

57

a

97

z

122

답

a = input()
print (ord(a))

문제 설명

문제 이해

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

응? 왜 처음 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])