바다에 퐁당 Ꙭ̮ ꉂ ◡̈⋆*

순열(순서 o) vs 조합(순서x)

순열(Permutation): 서로 다른 n 개의 대상에서 r 개를 뽑아 일렬로 배열한 것.

순열 알고리즘 구현 방법

1. 파이썬 모듈 사용

2. 재귀

3. 중복 for문 (리스트가 길어지면 너무 비효율적)

1. 파이썬 모듈 사용

• 파이썬 내장 itertools 패키지의 permutations 모듈 활용
• 만들어진 순열과 조합은 튜플의 형태로 리스트에 담겨서 반환된다. -> ([(0, 1, 2), ...])

from itertools import permutations

arr = [0, 1, 2, 3, 4, 5]

print(list(permutations(arr, 3)))

https://juhee-maeng.tistory.com/91

→모듈 사용하는 게 대체로 가장 빠르다고 함..

2. 재귀

2.1 DFS, 백트래킹과 상당히 유사하다.

• permutation([0,1,2,3], 2)
  = ([0],permutation([1,2,3], 1)) + ([1],permutation([0,2,3], 1)) + ([2],permutation([0,1,3], 1))+ ([3],permutation([0,1,2], 1))
• permutation([0,1,2,3], 3)
  = ([0],permutation([1,2,3], 2)) + ([1],permutation([0,2,3], 2)) + ([2],permutation([0,1,3], 2))+ ([3],permutation([0,1,2], 2))
  = ([0],{([1], permutation([2,3],1)) + ([2], permutation([1,3],1)) + ([3], permutation([1,2],1))}) + ([1]. { ~

def gen_permutations(arr, n):
    result = []

    if n == 0:
        return [[]]

    for i, elem in enumerate(arr): 
        for P in gen_permutations(arr[:i] + arr[i+1:], n-1):
            result += [[elem]+P]
              
    return result

2.2

def permutation(arr,r):
    arr = sorted(arr)
    used = [0 for _ in arr]

    def generate(chosen, used):
        if len(chosen) == r:
            print(chosen)
            return #used[i] = 0로 돌아가는데, 다시 for문 거치는 게 아니라, 바로 이어져서 i값이 유지됨.
        
        for i in range(len(arr)): #arr은 함수 외부에 정해져 있음(상수수)
            if not used[i]:
                chosen.append(arr[i])
                used[i] = 1
                generate(chosen, used)
                used[i] = 0 #순열 하나 만들고 나서, 다시 0으로 initialize
                chosen.pop() #return이 없으므로 for문이 끝난 후에도 if문 다시 돌고, if문 만족 못하므로 for문 새로 시작됨

    generate([], used)

좋은 코드라고는 하나 개인적으로 이해하는 데 시간이 걸렸음. 

arr: 리스트
r: 리스트 중 뽑을 개수

[for문 안에서]
chosen: 순열 구성하는 원소 리스트
used: chosen에 들어간 원소 index 위치에 해당 원소의 사용 여부를 0/1로 알려주는 리스트(즉 arr와 연동됨) (*디폴트는 0으로 채워짐)

• 함수 정의문에는 return의 위치가 중요함. for문이 모두 종료되었대도 return이 다른 곳에 있다면 다시 iteration 거침.
  • 여기도 for문의 상단 if문을 거쳐야 return되는데, for문이 종료되고 if문으로 돌아갔을 때 if문 조건이 성립되지 않으므로 return이 실행되지 않음. 즉, 다시 for문으로 돌아가 처음부터 실행됨. (물론 이 상황에서 used와 chosen은 이전 로그가 반영된 상태이므로 i값이 슉슉 점프하게 됨.
• generate 함수 정의문 내부에 generate가 사용된 재귀형식임.
  • 내부 generate이 실행될 때 if문 만족되면 바로 return 일어나므로, 내부 generate 실행 직전 i값이 그대로 보존된 상태로 used[i]=0 코드로 넘어감.
  • 만약 내부 generate 실행될 때 if문 만족 못 하면 for문으로 넘어가고, 결국 내부 generate가 종료되려면 내부 if문이 만족될 때까지 iter iter iter..
• if not False:
  • if not 이하가 False일 때 조건문 시행됨
  • python에서 False에 해당하는 것
    • False (Bool)
    • 0,0L,0.0과 같은 숫자 0 값
    • 다음과 같은 빈 시퀀스 :
      • 빈 목록 []
      • 빈 사전 {}
      • 빈 문자열 ''
      • 빈 튜플
      • 빈 세트
      • None개체
      • [0] 혹은 [0,0,..]은 아님.!!!
• 실행 원리 예시

permutation('ABCD', 3)

>>>

i: 0, chosen: ['A'], used: [1, 0, 0, 0]
i: 1, chosen: ['A', 'B'], used: [1, 1, 0, 0]
i: 2, chosen: ['A', 'B', 'C'], used: [1, 1, 1, 0]
['A', 'B', 'C']
i: 3, chosen: ['A', 'B', 'D'], used: [1, 1, 0, 1]
['A', 'B', 'D']
i: 2, chosen: ['A', 'C'], used: [1, 0, 1, 0]
i: 1, chosen: ['A', 'C', 'B'], used: [1, 1, 1, 0]
['A', 'C', 'B']
i: 3, chosen: ['A', 'C', 'D'], used: [1, 0, 1, 1]
['A', 'C', 'D']
i: 3, chosen: ['A', 'D'], used: [1, 0, 0, 1] ............

https://cotak.tistory.com/70

https://shoark7.github.io/programming/algorithm/Permutations-and-Combinations

https://www.delftstack.com/ko/howto/python/if-not-condition-in-python/

https://school.programmers.co.kr/learn/courses/30/lessons/42840

문제 개요

1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ...
2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5,/ 2, 1, 2, 3, 2, 4, 2, 5, ...
3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ...
*시험은 최대 10,000 문제. 문제의 정답은 1, 2, 3, 4, 5중 하나.

input
answers: 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열
ex. [1,2,3,4,5]

return
가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아서
ex. [1]
*가장 높은 점수를 받은 사람이 여럿일 경우, return하는 값을 오름차순 정렬.

나의 코드

def solution(answers):
    n = len(answers)
    fir = [1,2,3,4,5]*(n//5)+[1,2,3,4,5][:(n%5)]
    sec = [2,1,2,3,2,4,2,5]*(n//8)+[2,1,2,3,2,4,2,5][:(n%8)]
    thir = [3,3,1,1,2,2,4,4,5,5]*(n//10)+[3,3,1,1,2,2,4,4,5,5][:(n%10)]

    def compare(data):
        cnt = 0
        for idx, i in list(enumerate(data)):
            if i == answers[idx]:
                cnt +=1
        return cnt

    fir_val = compare(fir)
    sec_val = compare(sec)
    thir_val = compare(thir)

    lst = sorted([(1,fir_val), (2, sec_val), (3, thir_val)], key=lambda x: x[1], reverse=True)
    answer = [lst[0][0]]
    for (idx, val) in lst[1:]:
        if val == lst[0][1]:
            answer.append(idx)

    return answer

모범 코드

def solution(answers):
    pattern1 = [1,2,3,4,5]
    pattern2 = [2,1,2,3,2,4,2,5]
    pattern3 = [3,3,1,1,2,2,4,4,5,5]
    score = [0, 0, 0]
    result = []

    for idx, answer in enumerate(answers):
        if answer == pattern1[idx%len(pattern1)]:
            score[0] += 1
        if answer == pattern2[idx%len(pattern2)]:
            score[1] += 1
        if answer == pattern3[idx%len(pattern3)]:
            score[2] += 1

    for idx, s in enumerate(score):
        if s == max(score):
            result.append(idx+1)

    return result

• [idea] 리스트 내 원소에 특정 패턴이 반복되는 경우
  • pattern 변수 통해 반복되는 부분만 따오기
  • [idx % (패턴의 길이)] 인덱스 처리.
• for문 순환하여 세 명의 score 병렬 계산 (어차피 answers와 세 명의 대답 length가 동일함)
• score = [0,0,0] 처리 후 한꺼번에 score[x] +=1
• 마지막 출력 처리하는 건.... 나 왜 저렇게 짰지?🫢 모범코드대로 하는 게 당연할 따름. idx 순서대로 처리되니 더더욱?!

간단한 문제였다! 코드 더 효율적으로 짜기.

문제를 풀기 전 이해하고 있어야 하는 아이디어

x, y의 두 수의 합이 정해져 있을 때, 두 수의 곱(x*y)이 최소화되려면
x+y = a를 성립하는 (x,y)조합 중 (최대, 최소) 조합이어야 한다.

ex1) 합이 10인 경우

1 10 =10 (최소의 곱)
2 9 =18
3 8 =24
4 7 =28
5 6 =30

1 5 =5 (최소의 곱)
2 4 =8
3 3 =9

https://school.programmers.co.kr/learn/courses/30/lessons/86491

문제 개요

input
sizes: 모든 명함의 가로 길이와 세로 길이를 나타내는 2차원 배열 (ex. [[60, 50], [30, 70], [60, 30], [80, 40]])
*원소 개수 최소 1
*명함 가로, 세로는 최소 1, 최대 100

return
지갑의 크기 (ex. 4000)

나의 코드

def solution(sizes):
    big = []
    small = []
    for [x,y] in sizes:
        if x >= y:
            big.append(x)
            small.append(y)
        else:
            big.append(y)
            small.append(x)
    answer = max(big)*max(small)

    return answer

* 아이디어만 잘 알고 있으면 아주 간단한 문제.

https://school.programmers.co.kr/learn/courses/30/lessons/42627

문제 개요

input
: jobs = [작업이 요청되는 시점, 작업의 소요시간]을 담은 2차원 배열

return
: 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 처리하면 평균이 얼마
*소수점 이하의 수는 버림

*하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리

문제 이해

input:  [[0, 3], [1, 9], [2, 6]]

우측보다 좌측의 경우, 프로세스 총소요시간(요청부터 처리될 때까지 총시간)의 평균이 적다.

return: 9 (총 27 // 3)

문제 결론

• 대기 시간이 없는 경우와 있는 경우를 구분한다.
  • 대기 시간이 있는 경우 if문 내부에서 현재 시각 now를 조절함으로써, '대기 시간이 없는 경우'와 state를 일치시킨다.
  • 현재 시각 now 계산 식 & 프로세스 총 소요시간 계산 식을 if문 외부에서 공유: waitlst의 heappop 처리.
• 대기 시간이 없는 경우: 소요 시간이 짧은 것을 우선순위로 처리 → heappop (자동 min 정렬)
  • jobs에서 원소를 하나씩 꺼내어 waitlst에 heappush. 즉 jobs 대신 waitlst를 heap으로 처리. 
• 대기 시간이 있는 경우: jobs에서 가장 이른 것을 꺼내어 waitlst에 heappush.

자주 활용되는 아이디어이므로 확실히 기억할 것

문제 이해 프로세스

1. 작업의 요청부터 종료까지 걸린 시간 = 기다린 시간(변수) + 프로세스 진행 시간(상수)

2. '기다린 시간(변수)'은 해당 프로세스가 요청된 시각이 직전 프로세스 종료 시각보다 '이전인가' '이후인가'에 따라 계산 방법이 다르다.

→ 시각과 시간 구분하자

→ 직전 종료 시각을 어떻게 구하는가..? (생각의 무한루프 ♾️🥲)

→ 초깃값은 어차피 a가 가장 작은 값으로 결정되어 있으니 이후 점화식 잘 세우면 된다 (ps: 하드디스크가 작업을 수행하고 있지 않을 때에는 먼저 요청이 들어온 작업부터 처리)

→ 일단 '기다린 시간'을 경우에 따라 나누어보자. (경우 = if문으로 구현)

→ 처음에는 '직전 프로세스 종료 시각'을 end로 지정했는데, 오히려 헷갈려서, 현재 시각 'now'로 대체하였다 **

현재 프로세스: [a,b]

1️⃣ if 현재 시각(now) >= 현재 프로세스 요청 시각:

기다린 시간 = 기존 now - a

프로세스 총 소요시간 = (기존 now-a) + b == (업데이트 완료한 now) - a

프로세스 끝난 후 현재 시각 업데이트 now = 기존 now+b

2️⃣ elif 현재 시각(now) < 현재 프로세스 요청 시각:

기다린 시간 = 0

프로세스 총 소요시간 = b == (업데이트 완료한 now) - a

프로세스 끝난 후 현재 시각 업데이트 now = a+b

3. 그런데 어떻게 정렬하지.. (생각의 무한루프 ♾️🥲 again)

끄적이다 겨우 알아낸 사실:

- 상수인 것을 제외하고 변수인 것을 비교하자. 

- 프로세스 소요시간이 짧은 것부터 정렬해야 한다.

- 조건에 의해, 작업을 수행하고 있지 않을 때에는, 먼저 요청이 들어온 작업부터 처리해야 하므로 → 현재 시각 이전에 요청된 프로세스 먼저 처리하고 → 나머지를 처리해야 한다.

- 현재 시각 이전에 요청된 프로세스 즉 대기 중인 프로세스를 waitlst에 저장 1️⃣

- 단, 대기 중인 프로세스가 없는 경우도 있다! 2️⃣ 

▶ waitlst가 비어 있지 않은 경우 1️⃣
    → jobs 리스트에서 소요시간이 가장 짧은 것을 먼저 waitlst에 heappush
    → 단 waitlst 내부에서는 '소요시간'을 기준으로 정렬해야 하므로, for문 heappush 시 인덱스 위치를 바꾼 채로.

▶ waitlst가 비어 있는 경우(=요청이 가장 이른 다음 프로세스가 현재 시각 이후에 요청될 때) 2️⃣ 
    → 시각을 옮겨주어 다음 프로세스가 바로 시작될 수 있도록 세팅한다: now = 요청시각
    → 가장 이른 프로세스를 jobs 리스트에서 heappush, 마찬가지 인덱스 위치를 바꾼 채로.

▶ 1️⃣&2️⃣ 거친 후
→ now += 소요시간
→ 프로세스 총 소요시간: now - 요청시각
→ total.append(now - 요청시각)

▶ 서로 다른 계산식을 가지는 1️⃣&2️⃣를 잘 처리함으로써 결과적으로 동일한 state가 되도록 일치시킴
→ now 및 total 계산식을 간단히 공유할 수 있게 됨.

▶ 마무리: int(total / len(jobs)) OR total // len(jobs)

*소수점 이하의 수는 버림 조건 매우 주의
*조건 상 분모가 0이 될 수 없으므로 해당부분은 pass.

나의 코드

from heapq import heapify, heappop, heappush

def solution(jobs):
  j_len = len(jobs)
  heapify(jobs)
  now = 0
  total = []
  waitlst = [] #waitlst의 위치 중요

  while len(total)<j_len:
    while jobs and (jobs[0][0] <= now):
        next = heappop(jobs)
        heappush(waitlst, (next[1],next[0]))

    if jobs and waitlst == []:
      next = heappop(jobs) #jobs에서 다음 활동 next 직접 꺼내기
      now = next[0] #next 진행되도록 시간 세팅
      heappush(waitlst, (next[1], next[0])) #next를 waitlst에 직접 추가
    
    x,y = heappop(waitlst)
    now += x #프로세스 진행하였으므로 진행시간 포함하여 현재 시간 업데이트 
    total.append(now-y)
  
  answer = sum(total)//j_len
  return answer

• 현재 시각 now의 업데이트 아이디어 중요 ⭐
• indentation & while문 & if문 조건 엄밀하게 설정해야 함 ⭐
• 리스트를 heap으로 변환 안 하더라도, 리스트 자체로 heappop 바로 쓸 수 있구나.
• jobs는 리스트 그대로 두고, wait할 원소를 pop하기만 함 → waitlst에서 사용되지 않은 원소를 jobs로 되돌릴 필요 없음
• waitlst가 heap이며, waitlst 내에 새로운 원소가 들어올 때마다 힙정렬. (heappop, heappush 시 자동 힙정렬)
• waitlst가 비어있을 때 jobs 리스트 첫번째 원소의 시작 시간으로 now를 맞춤 

while len(total)<j_len:

• 이때 while jobs 하면 안 됨. jobs가 모두 pop되어 빈 리스트가 되더라도, waitlst에는 처리할 작업이 남아 있을 수 있음.

while jobs and (jobs[0][0] <= now):

• "jobs 리스트가 비어있지 않고" and "jobs[0][0] <= now" 동안에 계속.

if jobs and waitlst == []:

• "jobs 리스트가 비어있지 않고" and "waitlst는 비어있을 때" 한번.

heappush(waitlst, (next[1],next[0]))

• heap은 기본적으로 원소의 0index를 기준으로 정렬하므로, 이같이 인덱스 뒤집어 힙정렬 처리 필요.

다른 코드

import heapq

def solution2(jobs):
    answer, now, i = 0, 0, 0
    start = -1 
    heap = []
    
    while i < len(jobs):
        # 현재 시점에서 처리할 수 있는 작업을 heap에 저장
        for j in jobs:
            if start < j[0] <= now:
                heapq.heappush(heap, [j[1], j[0]])
        
        if len(heap) > 0: # 처리할 작업이 있는 경우
            cur = heapq.heappop(heap)
            start = now
            now += cur[0]
            answer += now - cur[1] # 작업 요청시간부터 종료시간까지의 시간 계산
            i +=1
        else: # 처리할 작업이 없는 경우 다음 시간을 넘어감
            now += 1
                
    return answer // len(jobs)

왜 틀렸을까 .. 19번 실패

19번 관련 테스트케이스 모두 통과인데,,

아래 코드!

from heapq import heapify, heappop, heappush
from collections import deque

def solution(jobs):
  j_len = len(jobs)
  heapify(jobs)

  end = 0
  total = 0
  while jobs:
    waitlst = []

    while jobs[0][0] <= end:
        a = heappop(jobs)
        waitlst.append(a)
        if len(jobs) == 0:
            break

    if waitlst:
      waitlst.sort(key=lambda x: x[1])
      waitlst = deque(waitlst)
      next = waitlst.popleft()

      end+= next[1]
      present = (end-next[0])
      for i in waitlst:
        heappush(jobs, i)

    else:
      next = heappop(jobs)
      end += (next[0]+next[1])
      present = next[1]

    total += present

  answer = int(total/j_len)
  return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42584

개요

prices: 초 단위로 기록된 주식가격이 담긴 배열

return: 가격이 떨어지지 않은 기간은 몇 초인지

[1, 2, 3, 2, 3] → [4, 3, 1, 1, 0]

나의 코드

from collections import deque

def solution(prices):
  answer = []
  idx_prices = deque(enumerate(prices))
  for _ in prices:
    idx, n = idx_prices.popleft()
    t = len(prices)-idx
    for i in range(t):
      if i == t-1:
        answer.append(t-1)
      else:
        if n > prices[idx+i+1]:
          answer.append(i+1)
          break
        else:
          continue
  return answer

정답 도출은 쉬웠으나, 시간 효율 문제 개선이 어려웠음.

• for _ in range(len(prices)-idx)에서 len 부분이 시간복잡도 심각.
  어차피 _ 사용할 거 아니라면,  for _ in prices로 대체
• 하나의 for문 안에 len(prices)-idx를 여러번 사용하였는데, 실행마다 len의 시간복잡도가 거듭되므로,
  t라는 변수에 저장한 후 t를 호출하는 게 훨씬 나음
• list 사용을 최소화할 것! reverse문도 안 먹혔던 이유 → queue와 deque를 이용하자 (pop, popleft..)
• enumerate 사용하지 않을 방법 모색해보자.

시간 초과 (실패) 코드

from collections import deque

def solution(prices):
  answer = []
  idx_prices = deque(enumerate(prices))
  for _ in range(len(prices)):
    n = idx_prices.popleft()
    try:
      small_idx = [x[0] for x in idx_prices if x[1]<n[1]][0]
      answer.append(small_idx-n[0])
    except:
      answer.append(len(prices)-n[0]-1)

  return answer

- try, except 이하가 애초에 비효율적이긴 하였음: 리스트 모두 완성 후 첫번째 원소만 사용하는 것이기 때문.

- 이외 이유는 상단에 기술.

모범 코드

1. 큐 활용

from collections import deque
def solution(prices):
    answer = []
    prices = deque(prices)
    while prices:
        c = prices.popleft()

        count = 0
        for i in prices:
            if c > i:
                count += 1
                break
            count += 1

        answer.append(count)

    return answer

2. 빠르며 깔끔

def solution(prices):
    stack = []
    answer = [0] * len(prices)
    for i in range(len(prices)):
        if stack != []:
            while stack != [] and stack[-1][1] > prices[i]:
                past, _ = stack.pop()
                answer[past] = i - past
        stack.append([i, prices[i]])
    for i, s in stack:
        answer[i] = len(prices) - 1 - i
    return answer

https://school.programmers.co.kr/learn/courses/30/lessons/42583

문제 개요

[input]
bridge_length: 트럭 수
weight: 다리가 견딜 수 있는 무게
truck_weights: 트럭 별 무게

[return]
모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지

나의 코드

def solution(bridge_length, weight, truck_weights):
    answer = 0
    road = [0]*bridge_length
    x = truck_weights.pop(0)
    sum_weight = 0 

    while len(truck_weights)>=0:
        sum_weight-=road[0]
        road.pop(0)
        road.append(0)
        if sum_weight+x <= weight:
            road[-1]=x
            sum_weight+=x
            answer+=1
            if len(truck_weights)>0:
                x = truck_weights.pop(0)
            else:
                answer+=bridge_length
                break

        else:
            answer+=1

    return answer

• 시간초과 문제
  • sum 함수가 시간초과 요인임! : 
    sum_weights=0 한 후
    루프 돌 때마다 weight을 -+= 하는 게 훨씬 좋음.
  • 리스트의 맨 처음 원소를 pop하고 싶을 때, pop(0)은 시간초과 가능하므로
    아래 두 가지 대안
    1) .popleft()
    2) truck_weights.reverse() 이후 .pop()
• TypeError: 'NoneType' object is not subscriptable
  - 코랩에서 if문에 화살표 가리키더라도,  첫 코드부터 혹은 그 코드자체가 처음부터 틀렸다는 게 아니라,
    여러 번 루프 돌린 후 해당 if문에 문제가 생겼다는 거
  - 문제의 코드: road = road[1:].append(0) 
     → None을 반환함, road[1:] 처리 후, 다음 줄에서 append. 따로 실행해야 함 (최종 코드에는 아예 pop(0)으로 대체)
  - 본 에러메시지는, 주로 리스트가 비어있는데 index에 접근하는 등, 빈 리스트에 특정 처리를 하면 발생.

모범 코드

1. 리스트.reverse 이후 pop() & deque 함수 사

from collections import deque

def solution(bridge_length, weight, truck_weights):
    bridge = deque(0 for _ in range(bridge_length))
    total_weight = 0
    step = 0
    truck_weights.reverse()

    while truck_weights:
        total_weight -= bridge.popleft()
        if total_weight + truck_weights[-1] > weight:
            bridge.append(0)
        else:
            truck = truck_weights.pop()
            bridge.append(truck)
            total_weight += truck
        step += 1

    step += bridge_length

    return step

2. 간결함

def solution(bridge_length, weight, truck_weights):
    q=[0]*bridge_length
    sec=0
    while q:
        sec+=1
        q.pop(0)
        if truck_weights:
            if sum(q)+truck_weights[0]<=weight:
                q.append(truck_weights.pop(0))
            else:
                q.append(0)
    return sec

*sum 함수 수정 필요

• "while 변수: "
  0이나 null값일 경우 False이기때문에, 빈리스트가 아니라면 True가되어 실행되는 함수
  ex) while truck_weights: / while q:

https://school.programmers.co.kr/learn/courses/30/lessons/42587

문제 개요

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

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다.

(숫자가 클 수록 더 중요한 문서)

input
-priorities: 문서의 중요도가 순서대로 담긴 배열
-location: 내가 인쇄를 요청한 문서가 현재 대기목록의 어떤 위치에 있는지.

return
내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지.

나의 코드

def solution(priorities, location):
  pri_tuple = list(enumerate(priorities))
  target_tup = pri_tuple[location]
  i=0
  while target_tup in pri_tuple:
    (max_idx,max_val) = sorted(pri_tuple, key=lambda x: x[1], reverse=True)[0]
    max_value = (max_idx,max_val)
    if pri_tuple[0][1] != max_val:
      back_lst = pri_tuple[0:pri_tuple.index(max_value)]
      del pri_tuple[0:pri_tuple.index(max_value)]
      pri_tuple.extend(back_lst)
    else:
      pri_tuple.pop(0)
      i+=1
  answer = i
  return answer

• 나의 아이디어:
  현재 리스트에서 max값을 찾고 → 리스트의 첫번째 원소~max값 직전 원소까지 그대로 슬라이싱하여
  → 리스트 맨 끝에 갖다 붙임: max값이 리스트의 맨 앞에 위치하게 됨 → 해당 max를 pop하여 제거 (i +1)
• 매개변수 location이 원본 priorities에 대한 index 값이므로, 원본 index 값을 저장하기 위해 enumerate 사용
  → priorities 리스트의 각 원소가 (idx, value)의 튜플 형태로 저장됨
• while문을 사용 (단, 무한루프의 위험 있으므로 while true는 지양하는 것이 좋음)
• max값을 찾기 위해 튜플로 이루어진 pri_tuple 리스트를 sorted함 (정렬 기준이 value값이므로, key, lambda를 이용)
• 추가 테스트케이스에서 문제가 생겼던 부분 😂
  1) while target_tup in pri_tuple에서, while문 내부의 pri_tuple이 새로 업데이트될 때 마다, 해당 while문의 pri_tuple도 함께 바뀜
  2) 따라서 max_value, max_idx, max_val도 함께 업데이트됨
  3) max_value자체가 튜플 형태이고, pri_tuple 리스트 애 max_value의 대상이 되는 원소 자체는 바뀌지만, 해당 원소 내부의 내용이 바뀌지는 않음 (초반에 enumerate로 정의되었기 때문에) → max_value의 max_idx와 pri_tuple.index(max_value)값은 엄연히 다름!!! 아예 다른 내용을 가리킴.
• pop은 디폴트로 맨 마지막 값을 삭제하지만, 원하는 인덱스의 원소를 삭제할 수도 있음
• 리스트의 조작: del 리스트[삭제할 원소 슬라이싱] / 리스트.extend(연장할 리스트 내용)

https://dojang.io/mod/page/view.php?id=2281 

모범 풀이

1. any 함수의 활용

def solution(priorities, location):
    queue =  [(i,p) for i,p in enumerate(priorities)]
    answer = 0
    while True:
        cur = queue.pop(0)
        if any(cur[1] < q[1] for q in queue):
            queue.append(cur)
        else:
            answer += 1
            if cur[0] == location:
                return answer

• 원소 하나씩, 하나씩. any니까 괜찮음
• [(i,p) for i,p in enumerate(priorities)]
  list comprehension에서 튜플을 다루는 법! 단순하지만 유용함
• ⭐⭐ 파이썬의 any, all 함수 ⭐⭐
  any() : 하나라도 True인게 있으면 True
  all() : 모두 True여야 True 반환
  →  아큐먼트로 iterable한 객체를 받음. (ex list)
  →  이 객체를 돌면서 조건을 검사해 답을 True/False의 답을 반환
  any(x, y for y in y_list) = True/False
  any()는 특히 대소비교를 할 때 사용하면 sort보다 실행시간을 많이 줄일 수 있다. 예를 들어 어떤 수와 어떤 리스트의 원소들을 비교하는데 해당 수가 리스트 안의 max값보다 큰지만 알고 싶다고 하자. 이 때, sort를 사용한 뒤 비교하면 리스트를 모두 정렬하기 때문에 시간이 걸린다. 하지만 any를 쓰면 리스트 내에 해당 수보다 큰 수가 있기만 하면 바로 True를 return하고 끝내기 때문에 시간이 덜 걸린다. 
  
  if 조건과 함께 다음과 같이 사용할 수도 있다.

cur = 3
temp = [1,3,6,2]
if any(cur<num for num in temp):
	print("There exist number that is larger than 3")

2. deque의 활용 -> 효율성 향상

def solution(p, l):
    ans = 0
    m = max(p)
    while True:
        v = p.pop(0)
        if m == v:
            ans += 1
            if l == 0:
                break
            else:
                l -= 1
            m = max(p)
        else:
            p.append(v)
            if l == 0:
                l = len(p)-1
            else:
                l -= 1
    return ans

나의 풀이

import math

def solution(progresses, speeds):
  zipped = zip(progresses, speeds)
  days = [math.ceil((100-x)/y) for x, y in zipped]
  max_index = [0]
  ptr = 0
  answer = []
  for _ in range(len(days)):
    if days[max_index[-1]] >= days[ptr]:
      ptr +=1

    else:
      max_index.append(ptr)
      ptr +=1
    
  last_element = len(days)-max_index[-1]
  for x in range(len(max_index)-1):
    answer.append(max_index[x+1]-max_index[x])

  answer.append(last_element)

  return answer

모범 코드

1. math의 ceil을 사용하지 않음

def solution(progresses, speeds):
    Q=[]
    for p, s in zip(progresses, speeds):
        if len(Q)==0 or Q[-1][0]<-((p-100)//s):
            Q.append([-((p-100)//s),1])
        else:
            Q[-1][1]+=1
    return [q[1] for q in Q]

2. 군더더기 없이 담백하게 자료구조를 잘 녹여냄

def solution(progresses, speeds):
    print(progresses)
    print(speeds)
    answer = []
    time = 0
    count = 0
    while len(progresses)> 0:
        if (progresses[0] + time*speeds[0]) >= 100:
            progresses.pop(0)
            speeds.pop(0)
            count += 1
        else:
            if count > 0:
                answer.append(count)
                count = 0
            time += 1
    answer.append(count)
    return answer

a = ['a','b','c']

print(a[-1]) #c
print(a[-1:]) #['c']

b = []

print(b[-1]) #error
print(b[-1:]) #[] 에러 없이 빈 리스트 반환

def no_continuous(s):
    a = []
    for i in s:
        if a[-1:] == [i]: continue
        a.append(i)
    return a

나의 풀이

def solution(arr):
    answer = [-1]
    for i in arr:
        if i == answer[len(answer)-1]:
            continue
        else:
            answer.append(i)
    answer.pop(0)

    return answer​

https://school.programmers.co.kr/learn/courses/30/lessons/42579

문제 개요

• 장르 별로 가장 많이 재생된 노래 2개씩 => 베스트 앨범
• 곡의 고유번호는 genres의 index.

1. 장르 정렬: 곡수
2. 장르 내 곡 정렬: 재생량 / 같으면 고유번호 낮은 거 먼저.

입력 2개: 노래 장르 list, 노래별 재생횟수 list
return: 베스트앨범 내 노래 고유번호 list

코드

def solution(genres, plays):
  gen_type = set(genres)
  gen_dict = {hash(a):0 for a in gen_type} #dictionary comprehension
  
  genres = [hash(b) for b in genres] #list comprehension
  zipped = list(enumerate(list(zip(genres, plays)))) #enumerate 통해 index 반환
  
  for item in zipped:
    gen_dict[item[1][0]] += item[1][1]
  gen_dict = sorted(gen_dict.items(), key=lambda x : x[1], reverse=True) #how to sort dictionary #method 'sort' is not available
  gen_sort = [x for x in list(map(lambda x: x[0], gen_dict))] #곡 재생수가 가장 큰 순으로 장르 나열
  answer=[]
  for gen in gen_sort:
    a=[] #장르별 곡 리스트
    for zips in zipped:
      if zips[1][0]==gen:
        a.append(zips)
      else:
        continue
    a.sort(key=lambda x: x[1][1], reverse=True)
    answer+=[x for x in list(map(lambda x: x[0], a[:2]))]

  return answer

주요 도구

- 알고리즘: 해시(딕셔너리, 파이썬 hash 함수)

- dictionary comprehension: 딕셔너리 생성하여 각 장르를 key, 장르별 곡 재생수의 총합을 value로 정리함

- zip(리스트1, 리스트2)에 list를 한번 더 씌워야 함 => 각 튜플에도 다중 인덱스로 접근 가능

- index 정보를 반환해주는 enumerate에도 list를 한번 더 씌워야 함 => 마찬가지, 각 원소에 다중 인덱스로 접근 가능

- 기존에 value값이 0으로 저장된 딕셔너리에 [] 인덱스 통해 => 적절한 key값을 입력해줌

- 특정 기준으로 iterable 정렬하기: sorted & key & lambda의 조합! lambda 통해 iterable의 '각 원소'에 구체적으로 접근 가능.

- 딕셔너리 정렬: 메서드 sort 대신 함수 sorted, 단 .items() 메소드 붙여야 함!

- map & lambda 조합 역시 중요: 주어진 이터러블 '각 원소'에 '동시에' 특정 함수를 적용하고 싶을 때.

   map(함수, 이터러블) => map(lambda x: x~~, 이터러블)

   마찬가지 map 이후 list 한번 더 씌워야 함.

- continue는 for문 처음으로 다시 돌아가는 것 vs return은 for문을 포함하여 함수 전체를 종료시키는 것

- indentation 아주 중요함. 엄밀한 논리 & 초반에 정확한 설계

다른 사람의 모범 풀이

def solution(genres, plays):
    answer = []
    d = {e:[] for e in set(genres)}
    for e in zip(genres, plays, range(len(plays))):
        d[e[0]].append([e[1] , e[2]])
    genreSort =sorted(list(d.keys()), key= lambda x: sum( map(lambda y: y[0],d[x])), reverse = True)
    for g in genreSort:
        temp = [e[1] for e in sorted(d[g],key= lambda x: (x[0], -x[1]), reverse = True)]
        answer += temp[:min(len(temp),2)]
    return answer

def solution(genres, plays):
    answer = []
    dic = {}
    album_list = []
    for i in range(len(genres)):
        dic[genres[i]] = dic.get(genres[i], 0) + plays[i]
        album_list.append(album(genres[i], plays[i], i))

    dic = sorted(dic.items(), key=lambda dic:dic[1], reverse=True)
    album_list = sorted(album_list, reverse=True)



    while len(dic) > 0:
        play_genre = dic.pop(0)
        print(play_genre)
        cnt = 0;
        for ab in album_list:
            if play_genre[0] == ab.genre:
                answer.append(ab.track)
                cnt += 1
            if cnt == 2:
                break

    return answer

class album:
    def __init__(self, genre, play, track):
        self.genre = genre
        self.play = play
        self.track = track

    def __lt__(self, other):
        return self.play < other.play
    def __le__(self, other):
        return self.play <= other.play
    def __gt__(self, other):
        return self.play > other.play
    def __ge__(self, other):
        return self.play >= other.play
    def __eq__(self, other):
        return self.play == other.play
    def __ne__(self, other):
        return self.play != other.play