백준 2주차

7일차(1/13)

 

https://www.acmicpc.net/problem/1181

람다를 쓸 수 있느냐

lists = []
n = int(input())
for _ in range(n):
    lists.append(input().strip())
set_lists = set(lists)

# 길이 우선 -> 사전 순
sorted_lists = sorted(set_lists, key=lambda x: (len(x), x))

for word in sorted_lists:
    print(word)

 

 

https://www.acmicpc.net/problem/10825

이때, 람다에서 -를 붙여서 내림차순을 표현하는데,

람다의 기본 정렬은 오름차순이다. 내림차순을 위해선 -를 붙이거나, 매개변수로 reverse=True를 써야하는데

- 를 붙일때는, 해당 인자가 숫자형 데이터여야 한다. 이를 위해 변환을 하고 정렬해야한다.

n=int(input())
lists=[]
for _ in range(n):
    name,korean,english,math=input().split()
    lists.append([name,int(korean),int(english),int(math)])
sorted_lists = sorted(lists, key=lambda x:(-x[1],x[2],-x[3],x[0]))
for nm in sorted_lists:
    print(nm[0])

 

만약 여러 기준으로 정렬할 때, 문자열인데 내림차순을 원한다면, 슬라이싱을 활용한다.

x[0][::-1]

 

 

https://www.acmicpc.net/problem/2729

t = int(input())

for _ in range(t):
    a, b = input().split()
    print(bin(int(a, 2) + int(b, 2))[2:])

 

8일차(1/14)

 

https://www.acmicpc.net/problem/5533

n = int(input())
arr = []
score = [0] * n

for _ in range(n):
    arr.append(list(map(int, input().split())))

for i in range(3):
    dic = {}

    for j in range(n):
        if arr[j][i] in dic:
            dic[arr[j][i]] += 1
        else:
            dic[arr[j][i]] = 1

    for j in range(n):
        if dic[arr[j][i]] == 1:
            score[j] += arr[j][i]

for s in score:
    print(s)

 

https://www.acmicpc.net/problem/7696

def find(n): #25 -> 27
    num=[0]*10002
    cur_num = 1  # 현재 탐색 중인 숫자
    cnt = 0  # 조건을 만족하는 숫자의 개수
    while True:
        str_cur_num = str(cur_num)
        if len(str_cur_num) == len(set(str_cur_num)):
            cnt += 1
        num[cnt] = cur_num
        if cnt == n:
            print(num)
            return cur_num
        cur_num+=1

#14번째 수 13
#13번째 수 14


while True:
    num = int(input())
    if num==0:
        break
    print(find(num))

원래 이거 -> 시간초과

def find(limit):
    non_repeating_numbers = []
    cur_num = 1

    # 중복 체크를 위한 배열 (0~9까지 각 숫자가 나온 적이 있는지 체크)
    while len(non_repeating_numbers) < limit:
        check = [False] * 10  # 각 자리수의 숫자가 나온 적이 있는지 체크
        num = cur_num
        is_duplicate = False
        
        # 각 자릿수 확인
        while num > 0:
            digit = num % 10
            if check[digit]:  # 이미 나온 숫자라면 중복
                is_duplicate = True
                break
            check[digit] = True
            num //= 10

        # 중복되지 않는 수면 리스트에 추가
        if not is_duplicate:
            non_repeating_numbers.append(cur_num)

        cur_num += 1

    return non_repeating_numbers


max_limit = 1000000
non_repeating_numbers = find(max_limit)

while True:
    num = int(input())
    if num == 0:
        break
    print(non_repeating_numbers[num - 1])

 

9일차(1/15)

 

https://www.acmicpc.net/problem/1932 

전형적인 DP문제

나는 아래에서 올라오는걸 좋아해서, 이걸로 풀었다. 이때, range범위를 잘 고려해야한다.

n=int(input())
arr=[[0]*n for i in range(n)]
dp=[[0]*n for i in range(n)]
for i in range(n):
    lists=list(map(int,input().split()))
    for j in range(len(lists)):
        arr[i][j]=lists[j]
for i in range(n):
    dp[-1][i]=arr[-1][i]
for i in range(n-2,-1,-1):
    for j in range(i+1):
        dp[i][j] = arr[i][j] + max(dp[i+1][j],dp[i+1][j+1])
print(dp[0][0])

 

10일차(1/16)

 

https://www.acmicpc.net/problem/1966

 

from collections import deque

n=int(input())
for _ in range(n):
    cnt,order = map(int,input().split()) #order만 집중  order번째 숫자 찾기
    arr= deque(map(int,input().split()))
    find = arr[order]
    order_pop=0
    while arr:
        max_num = max(arr)
        cur = arr.popleft()
        if cur != max_num:
            arr.append(cur)
        else:
            order_pop+=1
        if find not in arr:
            print(order_pop)
            break

이렇게 되면, 중요도가 같은 부분을 처리 못한다. -> 이 틀에서, 인덱스만 함께 처리하는 방안 생각

from collections import deque

n = int(input())
for _ in range(n):
    cnt, order = map(int, input().split())  #order만 집중  order번째 숫자 찾기
    arr = deque((priority, idx) for idx, priority in enumerate(map(int, input().split())))

    order_pop = 0

    while arr:
        max_priority = max(arr, key=lambda x: x[0])[0]
        cur_priority, cur_idx = arr.popleft()

        if cur_priority == max_priority:
            order_pop += 1
            if cur_idx == order:
                print(order_pop)
                break
        else:
            arr.append((cur_priority, cur_idx))

 

11일차(1/17)

 

https://www.acmicpc.net/problem/14888

n=int(input())
num_list = list(map(int, input().split()))
add,minus,multiple,divide=map(int,input().split())
op_dic = {'+': add, '-': minus, '*': multiple, '/': divide}

arr=[]
for op,cnt in op_dic.items():
    for _ in range(cnt):
        arr.append(op)
from itertools import permutations
operation = set(permutations(arr,n-1))
max_result = -float('inf')
min_result = float('inf')

for op_seq in operation:
    result = num_list[0]
    for i in range(1, n):
        if op_seq[i - 1] == '+':
            result += num_list[i]
        elif op_seq[i - 1] == '-':
            result -= num_list[i]
        elif op_seq[i - 1] == '*':
            result *= num_list[i]
        elif op_seq[i - 1] == '/':
            if result < 0:
                result = -(-result // num_list[i])
            else:
                result //= num_list[i]
    max_result = max(max_result, result)
    min_result = min(min_result, result)
print(max_result)
print(min_result)

 

12일차(1/18)

 

https://www.acmicpc.net/problem/17609

처음 코드

def is_palindrome(words):
    length = len(words)
    palindrome_cnt = 0

    for i in range(length // 2):
        if words[i] != words[length - (i + 1)]:
            palindrome_cnt += 1

    if palindrome_cnt == 0:
        return 0

    for i in range(length):
        temp = words[:i] + words[i + 1:]  
        palindrome_cnt = 0

        for j in range(len(temp) // 2):
            if temp[j] != temp[len(temp) - (j + 1)]:
                palindrome_cnt += 1

        if palindrome_cnt == 0:
            return 1

    return 2
t= int(input())
for _ in range(t):
    words= input()
    print(is_palindrome(words))

 

시간초과

슬라이싱에서 시간복잡도가 O(n)만큼 추가로 들어 최종적으로 O(n^2)가 된다.

포인터를 사용하여 해결하자

def is_palindrome(words):
    def is_valid_palindrome(s, left, right):
        while left < right:
            if s[left] != s[right]:
                return False
            left += 1
            right -= 1
        return True

    length = len(words)
    left, right = 0, length - 1

    while left < right:
        if words[left] != words[right]:
            if is_valid_palindrome(words, left + 1, right) or is_valid_palindrome(words, left, right - 1):
                return 1   
            return 2   
        left += 1
        right -= 1

    return 0  

t= int(input())
for _ in range(t):
    words= input()
    print(is_palindrome(words))

 

https://www.acmicpc.net/problem/15666

def generate_sequence(arr, sequence, m, start):
    if len(sequence) == m:
        print(" ".join(map(str, sequence)))
        return
    
    for i in range(start, len(arr)):
        generate_sequence(arr, sequence + [arr[i]], m, i)

n, m = map(int, input().split())
arr = list(map(int, input().split()))

arr = sorted(set(arr))

generate_sequence(arr, [], m, 0)