백준34 [BOJ/PYTHON] 18870. 좌표 압축 (정렬) 백준 문제 링크: https://www.acmicpc.net/problem/18870 문제 요약 주어지는 좌표 X1, X2, ..., Xn에 좌표 압축을 적용한 결과 출력 핵심 아이디어 주어지는 숫자들을 중복 제거한 채로 정렬하고 제일 앞에 있는 것부터 인덱스값으로 0부터 시작하면 된다. 풀이 # silver2-18870. 좌표 압축 import sys input = sys.stdin.readline # X1, X2, ..., Xn 좌표 압축을 적용한 결과 n = int(input()) nums = list(map(int, input().split())) # 중복 제거한 리스트(오름차순) 만들기 # 그 리스트 돌면서 몇 번째인지 인덱스 프린트 sorted_nums = sorted(set(nums)) # .. 2023. 5. 18. [BOJ/PYTHON] 1448. 삼각형 만들기 (정렬) 백준 문제 링크: https://www.acmicpc.net/problem/1448 문제 요약 빨대 N개 중 3개를 선택했을 때, 세 변의 길이 합의 최댓값 핵심 아이디어 길이 합의 최대값을 구해야 하기 때문에 빨대 길이 리스트를 큰 것부터 정렬하면 된다. 삼각형은 제일 큰 변의 길이가 나머지 두 변의 길이 합보다 작을 때 성립하는데, 그 정의를 이용하면 된다. 큰 것부터 정렬된 상황이기 때문에, list[i] > list[i + 1] + list[i + 2]가 성립하면 된다. 순차 3개(a b c)가 성립 안 하면 a b d, a b e... 등의 케이스도 성립 불가해 저렇게만 보면 된다. 마지막 세 개까지 봤는데도 성립 안 하면 -1을 출력하면 된다. 풀이 # silver3-1448. 삼각형 만들기 .. 2023. 5. 18. [BOJ/PYTHON] 11656. 접미사 배열 (정렬) 백준 문제 링크: https://www.acmicpc.net/problem/11656 문제 요약 문자열의 모든 접미사 사전순 정리 후 출력 핵심 아이디어 접미사 리스트를 저장해두고 그거를 정렬한 걸 출력하면 된다. 예시의 baekjoon 접미사 리스트는 baekjoon을 첫 번째부터 두 번째, 세 번째…로 자르면 된다. 풀이 # silver4-11656. 접미사 배열 # 문자열의 모든 접미사 사전순 정리 후 출력 s = input() #문자열 S list = [] # 접미사 리스트 for i in range(len(s)): list.append(s[i:]) print(*sorted(list), sep='\n') 실행 시간 메모리 31256KB, 시간 44ms (python3) 2023. 5. 18. [BOJ/PYTHON] 11582. 치킨 TOP N (정렬) 백준 문제 링크: https://www.acmicpc.net/problem/11582 문제 요약 치킨 집 정렬하고자 함 N/2명이 차례대로 2개의 치킨집을 선택해 정렬 → N/4명이 차례대로 바로 전 단계의 사람이 정렬한 두 개의 그룹을 차례대로 선택하여 치킨집 정렬 → 계속해서 N/8명, N/16명이 정렬을 진행 → 마지막 사람이 두 개의 정렬된 그룹을 합병하여 작업을 완료. 현재 단계에서 k명의 회원이 정렬을 진행할 때 정렬을 마친 뒤 결과를 출력 핵심 아이디어 n, k 둘다 2의 거듭제곱이라 n을 k로 나눈 몫만큼 숫자를 자를 수 있다. k명이 정렬하면 전체 치킨집 개수인 n을 k만큼 나눈 n // k 개씩 나눠서 정렬하게 된다. 그만큼 끊어서 각각 정렬하고 이어붙여 출력하면 된다. 풀이 # sil.. 2023. 5. 18. [BOJ/PYTHON] 1431. 시리얼 번호 (정렬) 백준 문제 링크: https://www.acmicpc.net/problem/1431 문제 요약 시리얼번호 정렬한 결과 출력 길이 짧은 것부터 길이 같으면 자리수 합 작은 것부터 (숫자만 더함) 사전순. 숫자가 알파벳보다 사전순으로 작음. 핵심 아이디어 정렬 기준이 여러 개이기 때문에 정렬 기준에 해당하는 애를 순서대로 커버해주면 된다. 정렬 우선순위에 따라 새 리스트에 길이, 자리수 합, 시리얼 번호를 넣어주고, 그것을 정렬하면 된다. 풀이 # silver3-1431. 시리얼 번호 import sys input = sys.stdin.readline # 1. 길이 짧은 것부터 # 2. 길이 같으면 자리수 합 작은 것부터 (숫자만 더함) # 3. 사전순. 숫자가 알파벳보다 사전순으로 작음. n = int(i.. 2023. 5. 18. [BOJ/PYTHON] 2423. 전구를 켜라 (최단 경로 - 다익스트라) 백준 문제 링크: https://www.acmicpc.net/problem/2423 문제 요약 N × M 직사각형 크기의 전자 회로에서 전원은 왼쪽 위 모서리에 연결되어 있고, 전구는 오른쪽 아래 모서리에 연결 전구는 전원에서 전구로 가는 경로가 있을 때만 불이 켜짐 전구에 불을 켜기 위해 돌려야 하는 칸의 개수의 최솟값 구하기 핵심 아이디어 불가능할 경우 "NO SOLUTION”을 출력해야 하는데, N + M이 홀수인 경우 물리적으로 불을 켜는 것이 불가능하다. 다익스트라로 푼다고 가정했을 때 비용값을 구하는 것이 필요한데, ‘돌려야 하는 칸의 개수의 최솟값’을 구해야 하기 때문에 돌릴 필요가 없으면 0, 돌려야 하면 1로 비용을 산정하면 된다. “/”일 때는 (i, j+1)에서 (i+1, j) 방향으.. 2023. 5. 18. 이전 1 2 3 4 5 6 다음