programmers.co.kr/learn/courses/30/lessons/42626

[코테리뷰]

문제 접근

• 가장 작은 두 개의 지수를 이용해서 새로운 지수로 바꿔주고, 모든 값이(스코피 지수가) K보다 커질 때까지 걸리는 횟수를 구해준다.

• 효율성 문제 : heapq를 이용하여 최솟값을 보다 빨리 찾을 수 있다.

Heapq 이용 시 알아야 할 3가지

1. heapq로 만들어주기 : heapq.heapify(리스트명)

   • 결과 : 해당 리스트가 heap으로 바뀐다.

2.  heapq에 원소출력하기 : heapq.heappop(힙명)

   • 결과 : 해당 힙의 원소 중 최솟값이 pop된다.

3.  heapq에 원소 입력하기 : heaq.heappush(힙명, 원소값)

   • 결과 : 해당 힙에 원소값이 추가된다.

내 코드

import heapq


def solution(scoville, K):
    answer = 0
    heapq.heapify(scoville)  # 리스트 -> 힙큐로 바꿔준다 :):)

    while scoville:
        answer += 1

        new = heapq.heappop(scoville)  # 가장 작은 값이 꺼내진다.(힙의 이름 명시하는 것 잊지 말기)
        if not scoville:
            return -1
        new += heapq.heappop(scoville) * 2
        heapq.heappush(scoville, new)
        smallest = heapq.heappop(scoville)
        if smallest >= K:
            break
        else:
            heapq.heappush(scoville, smallest)

    return answer

programmers.co.kr/learn/courses/30/lessons/42885

[코테리뷰]

접근 방식

• 그리디 = > 구명보트에 2사람이 같이 탈 수 있는 조건 : 보다 무거운 사람은 보다 가벼운 사람과 탈 수 있다는 가정 성립

• 그래서 인덱스를 앞뒤로 좁혀나가서 같이 탈 기준(limit보다 무게가 같거나 적은지)으로 비교해줌.

  • 비교 ok : 서로 인덱스 +1/-1

  • 비교 not ok : 끝의 인덱스 -1

내 코드

• sort를 해주고, deque를 사용함

from collections import deque


def solution(people, limit):

    alone, together=0,0 # 따로, 둘이 같이 타는 경우의 수 변수
    queue = deque(sorted(people)) # 오름차순으로 정렬
    lightest = queue.popleft()  # 가벼운 사람

    while lightest:
        if not queue: # 큐가 (비교대상이) 더이상 존재하지 x
            alone+=1
            break
        heaviest = queue.pop()  # 무거운 사람
        sum = lightest+heaviest # 비교할 대상 : 두 사람의 무게 합
        if sum <= limit: # 같이 탈 조건 : limit보다 적을 때 같이 타기
            together+=1
            if not queue: # empty pop - 오류 방지
                break
            else:
                lightest = queue.popleft()
        else: # 무거운 사람 혼자 보트 타기
            alone+=1
    answer=alone+together
    return answer

내코드의 문제점 :

• 큐를 이용하다보니 큐가 더이상 존재하지 않을 때 ( 비교대상이 없거나, 비교 자체가 끝났을 때의) 처리를 각각 해주어야지 제대로 된 답이 도출된다. (이 오류를 잡느라고 시간을 오래씀) & 직관적으로 코드를 볼 때 어려움! ㅜㅜ

다른 분 코드

• 내 코드보다 직관적으로 이해가능!

def solution(people, limit):
    people.sort()
    count = 0

    first = 0
    last = len(people) - 1
    while first < last:
        if people[first] + people[last] <= limit:
            first += 1

        last -= 1

        count += 1

    if first == last:
        count += 1

    return count

https://programmers.co.kr/learn/courses/30/lessons/43162

문제 설명

네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다.

컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오.

제한사항

• 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다.

• 각 컴퓨터는 0부터 n-1인 정수로 표현합니다.

• i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][j]를 1로 표현합니다.

• computer[i][i]는 항상 1입니다.

입출력 예

예시

아래와 같이 2개의 네트워크가 있습니다.

접근방법(BFS)

- BFS 란? 

  - 너비 우선탐색 : 가까운 노드부터 탐색하는 알고리즘

  - 보통, 선입선출인 큐 자료구조를 이용

- 동작방식?

  1) 탐색 시작 노드를 큐에 삽입하고, 방문처리를 한다.

  	bfs.append(visited.index(0)) # 시작노드 (방문하지 않은 노드를 찾아서) 큐 삽입
        while bfs: 
            node=bfs.pop(0) # 시작노드 꺼내기
            visited[node]=1 # 방문처리  
       

  2) 큐에서 노드를 꺼내, (1)인접 노드 중에서 (2)방문하지 않은 노드를 모두 큐에 삽입하고, 방문처리를 한다. 

          for i in range(n): # 자료 탐색
                if visited[i]==0 and computers[node][i]==1: # 큐 삽입 조건 : (1),(2)
                    bfs.append(i) # 큐 삽입

  3) 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 

- 필요한 자료구조?

  - 큐 (본 문제에서는 리스트를 사용)

  - 방문여부 리스트

def solution(n, computers):

    answer=0 # 정답 변수
    bfs=[] # 스택 준비
    visited=[0]*n # 방문여부 리스트

    while 0 in visited: # 방문이 다 되어질 때까지!(visited에 0 이 없을 때까지)
        bfs.append(visited.index(0)) # 방문하지 않은 노드 인덱스를 찾아서 추가
        
        while bfs: # bfs 리스트에 노드가 있을 때
            node=bfs.pop(0) # 앞에서부터 node pop!
            visited[node]=1 # 방문처리해주기

            for i in range(n): # 인접 노드를 방문하기
                if visited[i]==0 and computers[node][i]==1: # 아직 방문하지 않았고, 서로 연결되어 있을 때
                    bfs.append(i) # 연결된 i를 추가해주기

        # 연결되어 있는 노드의 방문이 끝났다면,
        answer+=1 # 카운트해주기
    return answer

# 정답 확인
print(solution(n=3,computers=[[1, 1, 0], [1, 1, 0], [0, 0, 1]]))

참고: list 자료형으로도 append와 pop을 통해 queue를 이용할 수 있지만, deque를 쓰면 더 빠르게 이용가능합니다. 

- from collections import deque

- bfs=deque()

- deque.popleft()

programmers.co.kr/learn/courses/30/lessons/42587

문제 설명

일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린터를 개발했습니다. 이 새롭게 개발한 프린터는 아래와 같은 방식으로 인쇄 작업을 수행합니다.

예를 들어, 4개의 문서(A, B, C, D)가 순서대로 인쇄 대기목록에 있고 중요도가 2 1 3 2 라면 C D A B 순으로 인쇄하게 됩니다.

내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 알고 싶습니다. 위의 예에서 C는 1번째로, A는 3번째로 인쇄됩니다.

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

주는 location이 매개변수로 주어질 때, 내가 인쇄를 요청한 문서가 몇 번째로 인쇄되는지 return 하도록 solution 함수를 작성해주세요.

제한사항

• 현재 대기목록에는 1개 이상 100개 이하의 문서가 있습니다.

• 인쇄 작업의 중요도는 1~9로 표현하며 숫자가 클수록 중요하다는 뜻입니다.

• location은 0 이상 (현재 대기목록에 있는 작업 수 - 1) 이하의 값을 가지며 대기목록의 가장 앞에 있으면 0, 두 번째에 있으면 1로 표현합니다.

입출력 예

입출력 예 설명

예제 #1

- 문제에 나온 예와 같습니다.

예제 #2

- 6개의 문서(A, B, C, D, E, F)가 인쇄 대기목록에 있고 중요도가 1 1 9 1 1 1 이므로 C D E F A B 순으로 인쇄합니다.

문제 풀이

접근방식

• 방법 : 우선순위가 높은 것부터 인쇄하되, 적은 것은 뒤로 append해서 나중에 pop!

• 자료구조 이용 : collection의 deque와 stack기능을 하는 list

• 오류 나는 것들 하나씩 실행해보면서 찾아서 수정하기

• 런타임 에러

  • ValueError : max() arg is an empty sequence : 큐가 empty해서 나는 오류

  • TypeError: 'int' object is not subscriptable : 타입 비교가 잘못 되어서 나는 오류 (현재 코드에서는 필요 없어서 제거) 

# location에 있는 문서가 몇번째로 인쇄되는지 리턴
# priorities가 높은 문서부터 인쇄한다.
from collections import deque


def solution(priorities, location):

    queue=deque() # 큐 구현을 위해 deque 라이브러리 사용

    for i in range(len(priorities)):
        queue.append([i, priorities[i]]) # 인덱스와 함께 큐에 넣어준다. 

    stack=[] # 최종 인쇄된 순서를 기록하기 위한 리스트
    while queue: # 큐가 있을 때
        first=queue.popleft() # 왼쪽에서부터 pop 해준다. 
        if queue: # 뒤에 더 있을 때
            best=max(list(queue),key=lambda x:x[1]) # ValueError: max() arg is an empty sequence -> queue가 empty일 때 포착 필요
            if first[1]>=best[1]: # pop 한게 우선순위가 더 높으면
                if stack.count(first)==0: # 아직 first 원소가 안들어갔다면 (여기도 중복 방지)
                    stack.append(first)
            else: # 우선 순위 높은게 뒤에 있으면
                queue.append(first)
                if stack.count(best)==0: # 아직 best 원소가 안들어갔다면 (중복 방지)
                    stack.append(best)
        else: # 마지막 요소일 때
            stack.append(first)
    print(stack)

    # 주어진 loaction 인덱스에 해당하는 원소가 몇 번째로 출력되는지 확인하는 작업!
    for i in range(len(stack)):
        if location == stack[i][0]:
            return (i+1) # 0번째 인덱스부터 있으므로 +1을 해준다. 


print(solution(priorities=[1, 1, 9, 1, 1, 1],location=0))

실행 결과

문제 설명

문자열 s에 나타나는 문자를 큰것부터 작은 순으로 정렬해 새로운 문자열을 리턴하는 함수, solution을 완성해주세요.
s는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 간주합니다.

제한 사항

• str은 길이 1 이상인 문자열입니다.

입출력 예

코드 풀이

접근방식

• 큰것부터 정렬하기 때문에 reverse=True인 sorted를 사용하자.

기본개념

• 문자열 -> 리스트로 : list({문자열}
• 리스트 -> 문자열로 : "".join({리스트})

def solution(s):
    return "".join(sorted(list(s),reverse=True))

- 참고 : list1.sort() 적용 x, sorted(list1) ok

문제 설명

0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요.

예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다.

0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요.

제한 사항

• numbers의 길이는 1 이상 100,000 이하입니다.

• numbers의 원소는 0 이상 1,000 이하입니다.

• 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다.

입출력 예

코드 분석

처음 시도

• permutation을 사용해서 모든 경우의 수를 구했다.
• 결과: sample은 ok, test case는 전부 시간 초과가 나왔다..!

# 주어진 numbers에서 정수를 이어붙여서 만들 수 있는 가장 큰 수를 찾는다.
# 정수를 붙이는 순열 이용 => 그 중 가장 큰 수 찾기
from itertools import permutations


def solution(numbers):
    answer_list = []
    all_list=list(permutations(numbers,len(numbers)))
    for i in range(len(all_list)):
        temp=""
        for j in range(len(all_list[i])):
            temp = temp +str(all_list[i][j])
        answer_list.append(temp)
    print(answer_list)
    answer=max(answer_list)
    return answer

수정한 코드

point

• 문자열끼리 비교했다.
  • ASCII문자열로 비교가 되어서 앞에서부터 큰 수로 정렬이 가능하다.
  • map(str, {리스트})를 통해 형변환
• sorted로 정렬해줄 때, key값에 lambda 함수를 이용해서 세 자리의 값을 모두 비교해주어서 정렬했다.
  • 내림차순으로 정렬하기 때문에 reverse=True를 해준다.
• "".join(array)를 이용해서 문자열을 합쳐주었다.

# permutation 모든 경우의 수를 구하려고 하니 시간 초과 오류가 났다.
# 다른 방식으로 접근하는 것이 필요하다.

# 문자열을 내림차순으로 정렬한 다음, join 해주는 방식이다!
# 주의 : 처음에는 문자열로 비교할 것 !!(가장 큰 자릿수부터 비교 가능)


def solution(numbers):
    # 정수 type을 문자열 type으로 변경해주기 (map을 통한 형변환!)
    arr = list(map(str, numbers))

    # 문자열 크기대로 sorting하기
    # lambda : 1000이하의 정수이므로, x를 세 번 곱해주어 비교한다.
    array=sorted(arr, key=lambda x:x*3, reverse=True)

    # join으로 각각의 문자열들을 빈틈없이 붙여주기
    # int로 바꾸어주고, 다시 str으로 바꿔주기
    return str(int("".join(array)))

결과

문제 출처 : 프로그래머스 - programmers.co.kr/learn/courses/30/lessons/42839

문제 설명

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.

각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

• numbers는 길이 1 이상 7 이하인 문자열입니다.

• numbers는 0~9까지 숫자만으로 이루어져 있습니다.

• 013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

입출력 예 설명

• 예제 #1

  [1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

• 예제 #2

  [0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

• 11과 011은 같은 숫자로 취급합니다.

코드 풀이

접근방식

1. 순열조합 라이브러리를 이용해서 경우의 수를 구하기

• nPm : n개의 숫자를 m개로 순열!(순서 상관 있는 것= 순열)

• 현재 필요한 순열 : nP1, nP2, ....nPn 까지 모두

  • 그래서 all_numbers list에 append해줌.

• 코드 :

all_numbers.append(list(permutation({해당 리스트이름},m))

• 출력 결과 : [[('1',), ('1',), ('0',)], [('1', '1'), ('1', '0'), ('1', '1'), ('1', '0'), ('0', '1'), ('0', '1')], [('1', '1', '0'), ('1', '0', '1'), ('1', '1', '0'), ('1', '0', '1'), ('0', '1', '1'), ('0', '1', '1')]]

2. 각 순열마다 문자열로 바꾸어주어서 int 정수형으로 저장해주기

• 이 때, 중복되는 부분을 제거해주기 위해 set 집합 자료형을 이용해줌.

• 3중 for문 -> 완전 탐색 하는 부분

• 출력 결과 : [0, 1, 10, 11, 101, 110]

3. 집합자료형 set 을 list로 바꿔주기

• set은 인덱싱이 불가하여 각 원소마다의 접근이 어렵기 때문에 list로 바꾸어주어야 한다.

• 방법 : sorted(set이름) 사용함. (더 많은 방법은 아래 link 참고)

{list이름}=sorted({set이름})

4. 소수인지를 판별해준다.

• math 라이브러리의 제곱근 math.sqrt(n) 을 이용해서 반복 횟수를 줄여준다. !!

• 나머지가 0 : 즉 나누어 떨어진다면, point 변수를 통해 계수에서 제외한다.

from itertools import permutations
import math


def solution(numbers):
    answer = 0
    all_numbers = []
    # numbers 길이만큼 순열 구하기! 1<=n<=len(numbers)
    for n in range(1, len(numbers) + 1):
        all_numbers.append(list(permutations(numbers, n)))

    # list를 문자열로 바꾸어서 집합 set()에 넣기 (중복 x)
    set_numbers=set()
    for i in range(len(all_numbers)):
        for j in range(len(all_numbers[i])):
            temp='' # 각 순열 별로 문자열로 만들어주기
            for k in range(len(all_numbers[i][j])):
                temp = temp + all_numbers[i][j][k]
            # 저장한 문자열을 int형으로 set에 넣어주기 (0이 앞에 나오는 것 제거해줌)
            set_numbers.add(int(temp))

    # 소수 판별 및 count!
    # 인덱싱을 위해 set 데이터를 list로 옮겨주기
    last_list = sorted(set_numbers)
    # print(last_list)
    for n in last_list:
        if n==2:
            answer=answer+1
        elif n>2:
            point = True
            for i in range(2,int(math.sqrt(n))+1):
                if n%i==0:
                    point=False
                    break
            if point==True:
                answer=answer+1
    return answer

print(solution("17"))

결과

- 참고 :www.geeksforgeeks.org/python-convert-set-into-a-list/