초이의 끄적끄적

프로그래머스 - 해시

# 위장 (Level2)

def solution(clothes):
    answer = 1
    dic = {}
    for name, kind in clothes:
        if kind in dic:
            dic[kind] +=1
        else: dic[kind] = 1
    for i in dic.values():
        answer *=(i+1)

    return answer-1

# 베스트 앨범 (Level3)

• Point. 딕셔너리, 딕셔너리 정렬

1. 많이 재생된 장르 먼저 수록
2. 장르 내에서 많이 재생된 노래 먼저 수록
3. 장르별로 두 개씩(하나만 있으면 하나만)

def solution(genres, plays): 
    answer = [] 
    dic = {} # 장르 : (재생횟수, 고유번호)
    dic_count = {} # 장르별 재생횟수
    
    for i, (g,p) in enumerate(zip(genres, plays)):
        if g in dic:
            dic[g].append((p,i))
            dic_count[g] += p
        else:
            dic[g] = [(p,i)]
            dic_count[g] = p
    print(dic)
    print(dic_count)

    # 많이 재생된 장르순 정렬
    sorted_dic = sorted(dic_count.items(), key=lambda x: x[1], reverse=True) 
    print(sorted_dic) 
    
    for key in sorted_dic: # key값에 ('pop', 3100)
        play_list = dic[key[0]] #key[0]으로 해야 pop나옴
        print(play_list)

        # 많이 재생된 노래순 정렬
        play_list = sorted(play_list, key = lambda x : x[0], reverse=True)
        print(play_list)
        
        for i in range(len(play_list)): # 두개만 뽑아오기
            if i == 2: 
                break 
            answer.append(play_list[i][1]) 
            
    return answer

프로그래머스 - 해시 

# 완주하지 못한 선수

• 문자열 문제는 정렬부터 하고 보자. 

def solution(participant, completion):
    participant.sort()
    completion.sort()

    for par, com in zip(participant, completion) :
        if par != com :
            return par   # 예시 1번

    return participant[-1]         # 예시 2번

# 예시 1번
A = ['a','b','b','c'] 
B = ['a','b','c']
zip(A, B)  # [('a','a'), ('b','b'), ('b','c')]  # 차이 발생

# 예시 2번 - 1
A = ['a','b','c','c']   # 마지막 값 (중복된 값이 맨 뒤에)
B = ['a','b','c']
zip(A, B)  # [('a','a'), ('b','b'), ('c','c')]

# 예시 2번 -2
A = ['a','b','c']       # 마지막 값 (하나 다른 것이 맨 뒤에)
B = ['a','b]
zip(A, B)  # [('a','a'), ('b','b')]

+ (GOOD) 풀이 

• Point. 딕셔너리를 이용한 데이터 갯수 세기 -> collections 모듈

import collections

def solution(participant, completion):
    answer = collections.Counter(participant) - collections.Counter(completion)
    return list(answer.keys())[0]

( collections : 참고 ) 

프로그래머스 - 해시

# 전화번호 목록 (Level2)

- 해시 정석대로 풀기

def solution(phone_book):
    hash = {}
    for i in phone_book: # key값으로 전화번호 등록
        hash[i] = 0
    
    for i in phone_book:
        temp = ""
        for w in i:
            temp += w
            if temp in hash and temp != i: 
                # 자기 자신이 아니고 key값에 속해있으면
                return False
    return True

+ (GOOD) 풀이

• Point. 정렬하면 접두어끼리 붙어있음
• startswith() : 접두어 찾는 함수 (갓이썬,,,)

def solution(phone_book):
    phone_book.sort() # 접두어 붙어있음
    for a, b in zip(phone_book, phone_book[1:]):
        if b.startswith(a): return False 
    return True

프로그래머스

# 두 정수 사이의 합 

def solution(a, b):
    answer = 0
    for i in range(min(a,b),max(a,b)+1):
        answer += i
    return answer

+ (GOOD) 다른 사람 풀이 -> sum을 생각 안했다ㅋㅋㅋ

def solution(a, b):
    return sum(range(min(a,b),max(a,b)+1))

# 체육복 

- 처음 내 코드

def solution(n, lost, reserve):
    for i in reserve:
        if i in lost:
            lost.remove(i)
        elif i-1 in lost:
            lost.remove(i-1)
        elif i+1 in lost:
            lost.remove(i+1)
    return n - len(lost)

• 테스트 케이스 5,7 통과 못함
• why? 여벌 체육복을 가져온 학생이 체육복을 도난당했을 수 있습니다. 이때 이 학생은 체육복을 하나만 도난당했다고 가정하며, 남은 체육복이 하나이기에 다른 학생에게는 체육복을 빌려줄 수 없습니다.
• ex) 5 [2,3,4] [1,2,3] 4 -> 2번은 2번 체육복을 써야됨 -> 중복되는건 미리 빼놓고 시작해야됨.

- 수정 후 코드

• Point. 집합 set과 차집합 사용

def solution(n, lost, reserve):
    set_reserve = set(reserve) - set(lost)
    set_lost = set(lost) - set(reserve)
    for i in set_reserve:
        if i-1 in set_lost:
            set_lost.remove(i-1)
        elif i+1 in set_lost:
            set_lost.remove(i+1)
    return n - len(set_lost)

프로그래머스

# 가운데 글자 가져오기

def solution(s):
    answer = ''
    if len(s)%2 == 1:
        answer = s[len(s)//2]
    else:
        answer = s[len(s)//2-1 : len(s)//2+1 ]
    return answer

# 같은 숫자는 싫어

def solution(arr):
    answer = [arr[0]]
    for i in range(1,len(arr)):
        if answer[-1] != arr[i]:
            answer.append(arr[i])
    return answer

# 수박수박수박수박수박수?

def solution(n):
    answer = ''
    for i in range(1,n+1):
        if i%2 != 0:
            answer+="수"
        else:
            answer+="박"
    return answer

+ (GOOD) 다른 사람 풀이 

def solution(n):
    return "수박"*(n//2) + "수"*(n%2)

# 문자열 내 마음대로 정렬하기

• Point. 문자열 정렬
• 처음 접근 방법 -> sorted(strings, key=lambda x:x[n]) -> n번째 숫자가 같은 경우 사전순 정렬 안됨
  • 사전순 정렬을 해주고 n번째 기준으로 정렬해주면됨

def solution(strings, n):
    return sorted(sorted(strings), key=lambda x:x[n])

+ (GOOD) 다른 사람 풀이  미.쳤.다.

• n번째 수를 글자의 앞에 붙인다음, 정렬함

def solution(strings, n):
    answer = []
    for i in range(len(strings)):
        strings[i] = strings[i][n] + strings[i]
    strings.sort()
    for j in range(len(strings)):
        answer.append(strings[j][1:])
    return answer

프로그래머스 - 완전 탐색

# 모의고사 (Level 1)

def solution(answers):
    answer = []
    math_1 = [1, 2, 3, 4, 5]
    math_2 = [2, 1, 2, 3, 2, 4, 2, 5]
    math_3 = [3, 3, 1, 1, 2, 2, 4, 4, 5, 5]
    count = [0,0,0]
    for i in range(len(answers)):
        if answers[i] == math_1[i%5]:
            count[0] +=1
        if answers[i] == math_2[i%8]:
            count[1] +=1
        if answers[i] == math_3[i%10]:
            count[2] +=1

    for i in range(3):
        if count[i] == max(count):
            answer.append(i+1)
    return answer

# 소수 찾기 (Level 2)

• itertools를 이용해 순열 구하기 permutations (참고)
  • 중복되는 수 set으로 줄여 속도 높이기
• 소수 판정 -> 시간복잡도를 위하여 1) 제곱근 2) 에라토스테네스 체 이용하기

from itertools import permutations
import math

def check(n): # 소수 판별
    k = math.sqrt(n) # 제곱근 사용
    if n < 2: 
        return False

    for i in range(2, int(k)+1):
        if n % i == 0:
            return False
    return True

def solution(numbers):
    answer = []
    for k in range(1, len(numbers)+1):
        perlist = set(list(map(''.join, permutations(list(numbers), k)))) # k개 순열 구하기
        for i in list(perlist):
            if check(int(i)):
                answer.append(int(i))

    answer = len(set(answer))

    return answer

# 카펫 (Level 2)

def solution(brown, yellow):
    xy = brown + yellow
    plus_xy = (xy - yellow + 4)//2
    
    for i in range(1,xy//2+1):
        if i + xy/i == plus_xy:
            return sorted([i,xy//i], reverse = True)

프로그래머스 - 정렬

# K번째수 (Level 1)

def solution(array, commands):
    answer = []
    for i,j,k in commands:
        answer.append(list(sorted(array[i-1:j]))[k-1])
    return answer

# 가장 큰 수 (Level 2)

• 문자열로 정렬해서 합친다
• numbers의 원소는 1,000이하 ->세자리까지 확인한다 ->  x*3
• Point. 문자열 비교연산 -> 사전과 같은 방식
  • ex) 첫번째 인덱스인 666[0]인 6과 101010[0]인 1과 222[0]인 2를 ascii숫자로 바꿔서 비교합니다. 물론 같으면, 다음 인덱스도 비교합니다. 비교한 결과 [6, 2, 10]의 순으로 정렬됩니다.

def solution(numbers):
    numbers = list(map(str, numbers))
    numbers.sort(key=lambda x: x*3, reverse=True)
    return str(int(''.join(numbers)))

# H-Index (Level 2)

• Point. enumerate를 사용해서 반복문의 index번호 가져오기
• H-지수 구하는 방법(참고)

def solution(citations):
    answer = 0
    for i, p in enumerate(sorted(citations,reverse=True)):
        if i+1 <= p:
            answer+=1
    return answer

# 11066 파일 합치기 (골드3)

• 고난이도 문제 핵심 DP식 구하기

def process():
    N, A = int(input()), [0]+list(map(int, input().split()))
    # S[i]는 1번부터 i번까지의 누적합
    S = [0 for _ in range(N+1)]
    for i in range(1, N+1):
        S[i] = S[i-1] + A[i]

    # DP[i][j] : i에서 j까지 합하는데 필요한 최소 비용
    # DP[i][k] + DP[k+1][j] + sum(A[i]~A[j])
    DP = [[0 for i in range(N+1)] for _ in range(N+1)]
    for i in range(2, N+1): # 부분파일의 길이
        for j in range(1, N+2-i): # 시작점
            DP[j][j+i-1] = min([DP[j][j+k] + DP[j+k+1][j+i-1]
                                for k in range(i-1)]) + (S[j+i-1] - S[j-1])
    print(DP[1][N])


for _ in range(int(input())):
    process()

프로그래머스 네트워크 (문제)

• Point. 덩어리 구하기 -> BFS 사용

def solution(n, computers):
    answer = 0 # 네트워크의 개수 저장
    q = [] # 탐색을 위한 큐
    visited = [0]*n # 방문한 노드 체크

    while 0 in visited: #모든값이 방문표시가 될때까지 반복
        x = visited.index(0)
        q.append(x) # 첫 노드 인덱스 추가
        visited[x] = 1 # 첫 노드 방문 표시
        
        while q: 
            node = q.pop(0) # 큐 앞에서부터 노드 꺼내기
            visited[node] = 1
            for i in range(n): #인접 노드 방문
                if visited[i] == 0 and computers[node][i] == 1:
                    # 인접노드이고 방문한적 없는 경우
                    q.append(i) # 큐에 추가
                    visited[i] = 1 #방문했음을 표시
        answer += 1 # 한 네트워크 탐색을 마치면 개수 증가
    return answer

프로그래머스 - 두 개 뽑아서 더하기 (level 1)

def solution(numbers):
    answer = []
    for i in range(len(numbers)):
        for j in range(i+1,len(numbers)):
            answer.append(numbers[i]+numbers[j])
    sort_ans = sorted(answer)
    return sorted(list(set(answer)))