초이의 끄적끄적

프로그래머스

# 가운데 글자 가져오기

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()

#12849 본대 산책 (실버1)

• 한 건물에서 바로 인접한 다른 건물로 이동 하는 데 1분이 걸린다. 준영이는 산책 도중에 한번도 길이나 건물에 멈춰서 머무르지 않는다. 준영이는 할 일이 많아서 딱 D분만 산책을 할 것이다. (산책을 시작 한 지 D분 일 때, 정보 과학관에 도착해야 한다.) 이때 가능한 경로의 경우의 수를 구해주자.
• D 가 주어진다 (1 ≤ D ≤ 100,000) 
• 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력 한다.
• 참고

# 0 분에 어떤 지점에 도착할 수 있는 상태
# 0 : 정보과학과 1 : 전산관 2 : 미래관 3 : 신양관
# 4 : 한경직기념관 5 : 진리관 6 : 학생회관 7 : 형남공학관
DP = [1,0,0,0,0,0,0,0]

def nxt(state):
    tmp = [0 for _ in range(8)]
    tmp[0] = state[1] + state[2]
    tmp[1] = state[0] + state[2] + state[3]
    tmp[2] = state[0] + state[1] + state[3] + state[4]
    tmp[3] = state[1] + state[2] + state[4] + state[5]
    tmp[4] = state[2] + state[3] + state[5] + state[7]
    tmp[5] = state[3] + state[4] + state[6]
    tmp[6] = state[5] + state[7]
    tmp[7] = state[4] + state[6]
    return tmp

for i in range(int(input())):
    DP = nxt(DP)

print(DP[0]%1000000007)

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

• 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)))

# 1915 가장 큰 정사각형 (골드5)

• n×m의 0, 1로 된 배열이 있다. 이 배열에서 1로 된 가장 큰 정사각형의 크기를 구하는 프로그램을 작성하시오.
• Point. DP로 풀기... .. 노이해... 다시 풀어보기

N, M = map(int, input().split())
A = [[0 for _ in range(M+1)] for i in range(N+1)]
# DP[i][j] = i,j까지 왔을 때, 가장 큰 정사각형의 한 변의 길이
DP = [[0 for _ in range(M+1)] for i in range(N+1)]

for i in range(N):
    for idx, j in enumerate(list(map(int, list(input())))):
        A[i+1][idx+1] = j
mx =0
for i in range(1, N+1):
    for j in range(1, M+1):
        if A[i][j]:
            DP[i][j] = min(DP[i-1][j], DP[i-1][j-1], DP[i][j-1])+1

print(max([max(i) for i in DP]) ** 2)

단계별풀기 - 정렬

# 2108 통계학 (실버4)

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

• input()으로 하면 시간초과 남 import sys sys.stdin.readline() 사용
• 데이터 개수 세기 collections 모듈의 Counter 클래스 사용 ( 참고 )

from collections import Counter
import sys
N = int(sys.stdin.readline())
N_list = [int(sys.stdin.readline()) for _ in range(N)]
N_sort = sorted(N_list)

print(round(sum(N_list)/N)) # 반올림함수 round
print(N_sort[int(N/2)])
N_count = Counter(N_sort).most_common(2) #데이터 개수가 많은 순으로 정렬된 배열 리턴
if N > 1: # 데이터가 하나일 경우에는 out of range 뜨니까
    if N_count[0][1] == N_count[1][1]:
        print(N_count[1][0])
    else:
        print(N_count[0][0])
else:
    print(N_list[0])
print(N_sort[-1]-N_sort[0])

# 1427 소트인사이드 (실버5)

• 첫째 줄에 자리수를 내림차순으로 정렬한 수를 출력한다.

n = input()
n_list = []
for i in n:
    n_list.append(i)

n_sort = sorted(n_list, reverse=True)
for i in n_sort:
    print(i,end="")

# 2167 2차원 배열의 합 (브론즈1)

• 2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.
• 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i ≤ x, j ≤ y).
• point. 누적합 사용

N,M = map(int,input().split())
A = [list(map(int, input().split())) for _ in range(N)]
# DP[i][j] = (1,1) 부터 (i,j) 까지의 부분합
DP = [[0 for i in range(M+1)] for _ in range(N+1)]

for i in range(1, N+1):
    for j in range(1, M+1): #대각선 중복되므로 빼줘야됨
        DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + A[i-1][j-1]

for _ in range(int(input())):
    i, j, x, y = map(int, input().split())
    print(DP[x][y] - DP[i-1][y] - DP[x][j-1] + DP[i-1][j-1])

*  1차원 배열 누적합

A = [i for i in range(10)]
print(A)
for i in range(1, 10):
    A[i] = A[i-1] + A[i]
print(A)

// 결과값
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 3, 6, 10, 15, 21, 28, 36, 45]

• 3까지 합은 -> 6
• 5부터 9까지의 합 -> 9누적합 - (5-1)누적합 = 45 - 10 = 35
• => i부터 j까지의 합은 DP[j] - DP[i-1]

단계별풀기 - 정렬

# 2750 수 정렬하기 (브론즈1)

• 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
• 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 

n = int(input())
num = [int(input()) for _ in range(n)]
sort_n = sorted(num)

for i in range(n):
    print(sort_n[i])

# 2751 수 정렬하기2 (실버5)

• 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다
• 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 
• point. 수 정렬하기 코드 제출하면 시간 초과남 -> input()으로 입력받아 메모리 초과가 날 경우, import sys sys.stdin.readline() 사용

import sys
n = int(sys.stdin.readline())
num = [int(sys.stdin.readline()) for _ in range(n)]
sort_n = sorted(num)

for i in range(n):
    print(sort_n[i])

# 10989 수 정렬하기3 (실버5)

• 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
• 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다.  
• 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다.
• point. 수 정렬하기2로 코드로 제출하면 메모리 초과 뜸 -> array를 사용한다

import sys
n = int(sys.stdin.readline())
b = [0]*10001 #수가 10,000보다 작거나 같은 자연수이기 때문
for i in range(n):
    b[int(sys.stdin.readline())] += 1  #같은 수 갯수 세기
for i in range(10001):
    if b[i] != 0:
        for j in range(b[i]): #같은 수 갯수만큼 출력하기
            print(i)

# 11055 가장 큰 증가 부분 수열 (실버2)

• 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오.
• 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수열은 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 이고, 합은 113이다.
• 첫째 줄에 수열 A의 합이 가장 큰 증가 부분 수열의 합을 출력한다.

import copy
N, A = int(input()), list(map(int, input().split()))

# DP[i] : i까지 왔을 때, 합의 최대
# 자기 자신이 제일 클 수도 있음 ex) 1000 100 10 1 -> 1000이 젤커
DP = copy.deepcopy(A) 

for i in range(1, N):
    for j in range(i):
        if A[i] > A[j]:
            DP[i] = max(A[i]+DP[j], DP[i])

#마지막이 최대라는 보장없음
#예시ㅣ -> print(DP) [1, 101, 3, 53, 113, 6, 11, 17, 24, 32]
print(max(DP))

+ (심화) 합이 가장 큰 증가 부분 수열의 합과 리스트 출력하기 

import copy
N, A = int(input()), list(map(int, input().split()))

# DP[i] : i까지 왔을 때, 합의 최대
# 자기 자신이 제일 클 수도 있음 ex) 1000 100 10 1 -> 1000이 젤커
DP = copy.deepcopy(A)
rev = [i for i in range(N)]
idx = 0

for i in range(1, N):
    for j in range(i):
        if A[i] > A[j] and DP[i] < A[i]+DP[j]:
            DP[i] = A[i]+DP[j]
            rev[i] = j
    if DP[idx] < DP[i]:
        idx = i

print(DP[idx])
while rev[idx] != idx:
    print(A[idx], sep=" ")
    idx = rev[idx]
print(A[idx])

// 결과값
10
1 100 2 50 60 3 5 6 7 8
113
60
50
2
1

+ 최장 증가 부분 수열(LIS : Longest Increasing Subsequence)

단계별풀기 - 브루트 포스

# 1436 영화감독 숌 (실버 5)

• Point. 1666 2666 3666 4666 5666 6666 이 아니고 6660 6661 6662 6663... 이다.
• 단순 반복문으로 666이 들어있는지 판별한다

n = int(input())
cnt = 0
six_n = 666
while True:
    if '666' in str(six_n):
        cnt += 1
    if cnt == n:
        print(six_n)
        break
    six_n += 1