[BOJ_2164 카드2 -Python3](https://www.acmicpc.net/problem/2164

문제분석

1. 관찰
- queue 에서 두개를 빼서 첫번째 장은 버리고, 두번째 장은 뒤로 보낸다.
- 마지막 한장인 경우 출력한다.

2. 복잡도
- O(n) = 500000 >> 50만 가능

3. 자료구조
- 카드 순서 : int queue

해결코드

import sys
from collections import deque
si = sys.stdin.readline

N = int(si())
Q = deque([i for i in range(1,N+1)])

while Q:
    first = Q.popleft()
    if not Q:
        print(first)
        break
    second = Q.append(Q.popleft())

BOJ_2864 5와 6의 차이 -Python3

문제분석

1. 관찰
- 5를 5나 6으로 보고, 6을 5나 6으로 본다.
- 최소값: 6을 5로 바꾼경우
- 최대값: 6을 5로 바꾼경우

2. 복잡도
- O(len(A)+len(B)) = 7+7 >> 매우가능

3. 자료구조
- 5,6 의 자리수 check: int[]

해결코드

import sys
si = sys.stdin.readline

A,B = map(list,si().strip().split())
check_a = [0 for _ in range(len(A))]
check_b = [0 for _ in range(len(B))]

for i,v in enumerate(A):
    if v=='5' or v=='6':
        A[i]=0
        check_a[i]=1

for i,v in enumerate(B):
    if v=='5' or v=='6':
        B[i]=0
        check_b[i]=1

min_a = int("".join(map(str,A)))+5*int("".join(map(str,check_a)))
max_a = int("".join(map(str,A)))+6*int("".join(map(str,check_a)))

min_b = int("".join(map(str,B)))+5*int("".join(map(str,check_b)))
max_b = int("".join(map(str,B)))+6*int("".join(map(str,check_b)))

print(min_a+min_b, max_a+max_b)

BOJ_5585 거스름돈 -Python3

문제분석

1. 관찰
- 500, 100, 10, 5, 1 로 거스름돈을 받는다.
- 1000엔을 냈을 때 받는 잔돈의 개수를 구해야한다.
- 거스름돈 개수가 가장 적은 경우에 개수를 출력한다.

- 거스름돈이 가장 적은 경우는
- 큰돈부터 차례대로 값을 채워나가는 경우이다

2. 복잡도
- 사칙연산 

3. 자료구조
- 거스름 최소경우 : int[]

해결코드

import sys
si = sys.stdin.readline

pay = int(si())
m = 1000-pay

payback = [m//500,m%500//100,m%500%100//50,m%500%100%50//10,m%500%100%50%10//5,m%500%100%50%10%5]
print(sum(payback))

BOJ_10162 전자레인지 -Python3

문제분석

1. 관찰
- 3개의 버튼
- 300초, 60초, 10초
- A,B,B를 눌러 T초가 되도록하는 최소버튼 조작의 경우를 출력한다.

2. 복잡도
- O((T*T*T)//(300*60*10)) = (10000*10000*10000)//(300*60*10) >> 약 천만 가능

3. 자료구조
- 조합: int[]

해결코드

import sys
si = sys.stdin.readline

T = int(si())
flag = float('inf')
ans = [0,0,0]

for i in range(T//300+1):
    for j in range(T//60+1):
        for k in range(T//10+1):
            if 300*i + 60*j +10*k == T:
                flag = min(flag, i+j+k)
                if flag == i+j+k: # 가장 작은 경우 정답리스트 업데이트
                    ans[:]=[i,j,k]

if flag==float('inf'):
    print(-1)
else:
    print(*ans)

배운점

브론즈 4 문제인데 왜 이렇게 어렵게 풀었나 싶어서, 다른 코드를 살펴보았다.
다른 코드를 보고나니 내가 for문의 상한선으로 지정한 부분이 최소값이 된다는 사실을 알게됐다.
loop을 돌릴 필요가 없었다 ㅎㅎ

추가로, 보고서 감탄한 코드를 남긴다.
리스트 뒤에 조건문을 붙인 형식으로 출력을 했는데, 처음 보는 문법이라 신기했다.
해당 문법은 찾아봐야겠다.

참고코드

n=int(input());a=n//300;n%=300;b=n//60;n%=60;print(*[[-1],[a,b,n//10]][n//10==n/10])

BOJ_1120 문자열 -Python3

문제분석

1. 관찰
- 길이가 다른 두 문자열의 길이를 같게 만들면서 차이를 최소로한다.
- A,B 가 길이가 같도록 만든다

- case1) A, B 길이가 같다.
- case2) A가 들어갈 수 있는 모든 경우를 탐색하여 차이가 가장 적은 경우 출려한다.


2. 복잡도
- O((len(B)-len(A))*len(A)) = 50*50 >> 가능

3. 자료구조
- ans : float -> int
- 두 문자: str[]

해결코드

import sys 
si = sys.stdin.readline

a_list, b_list = map(list, si().strip().split()) 
a_len, b_len = len(a_list), len(b_list)
ans=float('inf')

if a_len == b_len:
    tmp = 0
    for i in range(a_len):
        if a_list[i]!=b_list[i]:
            tmp+=1
    ans = tmp
else:
    tmp = 0
    for i in range(b_len-a_len+1):
        for j in range(a_len):
            b_tmp = b_list[i:i+a_len]
            if a_list[j] != b_tmp[j]:
                tmp += 1
        ans = min(tmp, ans)
        tmp=0
print(ans)

BOJ_10819 차이를 최대로 -Python3

문제분석

1. 관찰
- abs(A[0]-A[1]) + abs(A[1] - A[2]) +... + abs(A[N-2]-A[N-1])
- N개의 숫자를 뽑을 수 있는 경우의 수를 모두 고려한다 => N!
- 주어진 수식 for 문으로 구현 => N

- 백트래킹으로 모든 조합 탐색하여 max값 갱신하여 출력

2. 복잡도
- O(N!*N) = 8!*8 >> 가능

3. 자료구조
- 구한 배열: int[]
- 체크처리: int[]

해결코드

import sys
si = sys.stdin.readline

N = int(si())
A = list(map(int, si().split()))

check = [0 for _ in range(N)]
nums = []
ans = 0

def bt():
    global ans
    if len(nums)==N:
        tmp = 0
        for i in range(N-1):
            tmp += abs(nums[i]-nums[i+1])
        ans = max(ans, tmp)
        return
    for i,v in enumerate(A):
        if not check[i]:
            check[i]=1
            nums.append(v)
            bt()
            check[i]=0
            nums.pop()
bt()
print(ans)