처음에 그냥 막 풀었다가 시간초과 떴던 문제...

n, k = map(int, input().split())
ans = 0

jewel_lst, c_lst = [], []
for i in range(n):
    m, v = map(int, input().split())
    jewel_lst.append((m, v))        # 무게 m, 가격 v

for i in range(k):
    c_lst.append([int(input()), 1])

jewel_lst = sorted(jewel_lst, key=lambda x: (-x[1], x[0]))

for j in jewel_lst:
    c_lst.sort()
    for c in range(len(c_lst)):
        if (c_lst[c][1] == 1) and (j[0] <= c_lst[c][0]):
            c_lst[c][1] = 0
            ans += j[1]
            break
            
print(ans)

처음에 이렇게 짰었는데 아무래도 for j in jewel_lst: 이 부분 부터 시간초과 떴을 듯; (input 범위가 굉장히 컸음)

그래서 heapq 를 써보려고 했음.
일단 파이썬의 heapq는 최소힙! 최상단 노드만 (root)만 최소값을 유지! 나머지는 그냥 들어온 순서

일단 용량이 작은 가방부터 채우는게 가장 유리함. (for문을 돌면서 가방의 용량은 점점 커짐)
현재 가방의 용량보다 작은 무게인 보석은 다 후보가 되는 것이고 (heappop을 이용해서 무게가 작은 보석들을 하나 씩 꺼내고, heappush로 다른 heap에 넣어줌), 그 중에서 가장 가치가 높은 보석을 담음 (heappop을 이용해서 가장 가치가 높은 보석을 담음!)

1. 이 때, 후보인 보석들은 다음 가방에 대해서도 후보에 해당하니까 삭제하지 않음
2. 이 때, 파이썬의 heapq은 최소힙이라서 최대 가치의 보석을 뽑기 위해선 -value 값을 heap 넣어주어야 한다!

잘 제출해서 패스하긴 했는데 필요이상으로 더럽게 코드를 짠 것 같아서 알아봤다.
Level 1 인데도 깔끔하게 풀지 못 한다니...

for i in range(min(n, m), 0, -1):
    if n & i == 0 and m % i == 0:
        answer.append(i)
        break

for i in range(max(n, m), n*m+1):
    if i % n == 0 and i % m == 0:
        answer.append(i)
        break

대충 이런 식으로 하면 코드 자체는 훨씬 간결하게 짤 수 있다.
뭔가 for문을 덜 돌고 싶어서 (제출한코드에서) factor_n, factor_m을 도입해서 더해주고 그랬는데 이 문제는 그렇게까지 하지는 않아도 됐을 것 같다.ㅎㅎ

캐시

접근 법은 맞았으나 edge case를 고려하지 못 했음!
다른 사람의 힌트를 보고 겨우 해결할 수 있었음.

cache 라는 list 변수를 하나 추가하고, 현재 cache 안에 몇 개의 element가 있고, 그 개수가 cacheSize 보다 작은지를 판단하여서 캐시를 채우는 방식으로 구현을 했음.

• 작다면, cahce에 추가
• 작지 않다면 (동일하거나 크다면), 가장 앞에 있는 cache를 버리고 현재 도시를 cache에 추가

위의 방식처럼 하면, cacheSize가 0일 때도 추가하게 되고 원래보다 더 짧은 시간만 소요된다... 그래서 계속 일부 테스트케이스에서만 틀리고 있었다..

나는 그림을 진짜 열심히 그려서 풀었는데 구글링 해서 다른 풀이 보고 더 쉽게 이해함.

여기 블로그 보니까 최대공약수 방식 쓴거나 전체 구조는 비슷한데 이유가 훨씬 직관적이었음
나는 그림 진짜 많이 그려봤는데 그냥 가로 세로...ㅎㅎ......

점프와 순간 이동

[link]

아이디어만 있다면 엄청 쉽게 풀리는 문제인데 너무 어렵게 생각했던 것 같음.
여기서 일단, 목적지를 지나치면 안 되고 딱 목적지에 맞게 도착해야함!

그래서 목적지까지의 거리가 2로 나눠지면, 거리를 반으로 나누고 나눠지지 않으면 -1을 해준다.
이 때, 순간이동 하는 경우는 건전지를 사용하지 않으므로 2로 나눠지지 않을 때만 건전지 사용량을 추가해주면 된다!

# 그리디 + 그래프 (BFS)
a, b = map(int, input().split())

visited = []
queue = [a]
cnt = 0
flag = False
while queue:
    new_queue = []
    for q in queue:
        if b in queue:
            flag = True
            break
        if q not in visited:
            visited.append(q)
            if q*2 <= b:
                new_queue.append(q*2)
            if q*10+1 <= b:
                new_queue.append(q*10+1)
    cnt += 1
    queue = new_queue
        
if flag:
    print(cnt)
else:
    print(-1)

처음에는 이렇게 풀었는데 계속 시간초과 에러 났음.

1. new_queue를 새로 만들고, for문으로 queue를 도는데 일단 여기서 시간이 꽤 걸린 듯 함
2. 그래서 new_queue를 없애고, deque를 import해서 활용했음. queue에 값만 넣는게 아니라 depth 정보도 넣도록! queue = deque([a]) 에서 queue = deque([a, 1]) 이런 식으로!
3. 그래도 시간초과 나서 더 생각해보니까 굳이 visited 가 필요가 없었음. if q not in visited도 꽤 시간 소요가 됐을 것 같음.
   -> 결론적으로 deque로 바꿔서 depth정보를 값 정보와 함께 넘겨주고, visited를 제거하니까 시간초과 지옥에서 벗어날 수 있었음.

멀리 뛰기

이 문제는 보고 DP 인건 알겠는데 어떻게 처리할지 막막했던 문제...
처음에는 가야할 칸이 n칸이라고 하면, 아래와 같은 경우가 되나? 라고 생각했는데 그러면 중복되는 가짓수를 어떻게 처리해줘야하나!! 이 생각만 계속 했었다.

• (1칸 가는 방법 + n-1칸 가는 방법)
• (2칸 가는 방법 + n-2칸 가는 방법)
• ...

이걸 한 n=5인 경우까지만 직접 생각해보면 피보나치와 동일하게 진행되는 것을 알 수 있다. 이에 대해 조금 더 살을 붙이자면,
n칸까지 가는 방법은 크게 2가지로 나눠서 볼 수 있다. 두 가지 방법은 중복되지 않음!

• n-1 번째 칸에서 1칸을 뛰어서 n칸에 도착
• n-2 번째 칸에서 2칸을 뛰어서 n칸에 도착

따라서, n-1번째 칸에서 오는 방법 + n-2번째 칸에서 오는 방법으로 구성되므로 d[n] = d[n-1] + d[n-2] 가 된다!

문제점 💣

시간 초과

원인

• 그 이유가 방문 여부를 알기 위해서 visited 를 그냥 빈 리스트로 선언하고 방문할 때 마다 visited에 추가했음.
• 그리고 노드가 방문한 적 있는 노드인지 아닌지를 판단하기 위해서 if not node[0] in visited: 이런 식으로 구현함.
  => 그러다 보니, visited 안에 있는 모든 element와 node[0]을 비교해야함
  => 그래서 시간 초과난 듯

해결방법 🔮

cost list를 선언해서 (어차피 가장 멀리 있는 노드 알아야하니까 필요함), 그걸 visited 용으로도 사용함.
cost를 길이가 n인 list로 선언함. (리스트의 각 요소는 n+1로 모두 초기화)
=> 그래서 만약 방문한 노드의 cost값, 즉 cost[node[0]-1] == n+1 이라면 한 번도 방문한 적 없는 노드라는 뜻!

사실 위의 방식 말고, 그냥 visited를 길이가 n인 boolean list로 선언하고 if visited[node[0]-1]: 으로 해도 시간초과는 안 났을 듯 함.

이분 탐색, binary search

일단, 프로그래머스에서의 이분 탐색은 대부분 정답 범위의 최소, 최대를 정의하고 범위를 줄여나가면서 정답이 어디에 위치해 있을지를 찾음.

1. 정답 범위의 최소(하한)은 left, 정답 범위의 최대(상한)은 right 으로 정의한다.
2. mid = (left + right) // 2를 정의
3. while 문을 이용해서 범위를 줄여나가는데, while 문 조건은 보통 while left <= right:
4. 특정 조건에 따라서 범위를 점차 줄여나간다. 범위는 보통 아래 2개 중 하나로 좁혀진다.
   1. [left, right] => [left, mid-1]
   2. [left, right] => [mid+1, right]

관련 문제: Problem-Solving/Programmers/Kit/BinarySearch

프로그래머스 12940

잘 제출해서 패스하긴 했는데 필요이상으로 더럽게 코드를 짠 것 같아서 알아봤다.
Level 1 인데도 깔끔하게 풀지 못 한다니...

for i in range(min(n, m), 0, -1):
    if n & i == 0 and m % i == 0:
        answer.append(i)
        break

for i in range(max(n, m), n*m+1):
    if i % n == 0 and i % m == 0:
        answer.append(i)
        break

대충 이런 식으로 하면 코드 자체는 훨씬 간결하게 짤 수 있다.
뭔가 for문을 덜 돌고 싶어서 (제출한코드에서) factor_n, factor_m을 도입해서 더해주고 그랬는데 이 문제는 그렇게까지 하지는 않아도 됐을 것 같다.ㅎㅎ

프로그래머스 62048

나는 그림을 진짜 열심히 그려서 풀었는데 구글링 해서 다른 풀이 보고 더 쉽게 이해함.

여기 블로그 보니까 최대공약수 방식 쓴거나 전체 구조는 비슷한데 이유가 훨씬 직관적이었음
나는 그림 진짜 많이 그려봤는데 그냥 가로 세로...ㅎㅎ......

프로그래머스 12899

되게 많이 본 듯한 유형이었는데 오랜만에 해서 그런지 꽤나 헤맸음
방향은 바로 잡았는데 구현할 때 애먹음
로직 자체는 숫자를 1, 2, 4 3개만 사용하니까 3개로 조합해서 n번째로 큰 숫자를 구하는 것! 자릿수가 커질 수록 3의 거듭제곱으로 만들 수 있는 가짓수가 생기니까, 3, 9, 27, 81 ... 자릿수와 특정 자리 수 중에 몇 번째로 큰지를 알아내고! (여기까지는 쉽게 함)
그걸 이용해서 조합하는게 일이였다!
개인적으로 answer += available[r // 3**(cnt-1) - 1] 이 부분에서 -1을 해준게 포인트라구 생각한다. 파이썬의 리스트 인덱싱 특성도 잘 이용할 수 있고

프로그래머스 72411

여기서 포인트는 flat list 만들기라고 생각한당

flat_lst = [sub_c for c in combi for sub_c in c]

flat_lst = []
for c in combi:
    for sub_c in c:
        flat_lst.append(sub_c)

위의 두 개는 같은 코드!

프로그래머스 17677

다중집합이 포인트! 근데 이건 그렇게 어렵지 않아서 코드 보면 될 듯 하다!