문제풀이

[문제] https://www.acmicpc.net/problem/2170 2170번: 선 긋기 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 다음 N개의 줄에는 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어진다. www.acmicpc.net [풀이] 이 문제의 핵심은 아래 두 가지로 요약할 수 있다. 1. 선을 좌표 기준으로 정렬해야된다. (우선순위 큐 혹은 배열 정렬) 2. 선이 포함되는 경우 조건문으로 처리 👎 배열에 선을 그은 곳은 1로 채워 총 1의 수를 구할 경우, 배열 크기를 2조로 지정해야되기 때문에 다른 방법을 생각해야한다. 문제에서 주어진 입력된 선을 형광펜으로 표시하면 이렇다..

[문제] https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net [풀이] "아홉 난쟁이의 키는 모두 다르지만 그중 일곱 난쟁이의 크기의 합은 100이 된다" 는 것은 sum(난쟁이 리스트) - (난쟁이1 + 난쟁이2) == 100과 같다. 두 난쟁이를 구하기 위해 전체 탐색을 해야 한다. [코드] import sys men = [int(sys.stdin.readline()) for _ in range(9)] flag = False for i in range(9..

[문제] https://school.programmers.co.kr/learn/courses/30/lessons/70129 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [코드] def solution(s): cnt, zero_cnt = 0, 0 while s != '1': zero_cnt += s.count('0') s = bin(len(s.replace('0', '')))[2:] cnt += 1 return [cnt, zero_cnt]

[문제] https://school.programmers.co.kr/learn/courses/30/lessons/12951# 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 문자열을 split(' ') 함수로 쪼개 리스트에 담았다. 괄호안에 ' ' 가 있기 때문에 공백문자 1개를 기준으로 쪼갠다. 문자열에 "Hello Hi" 이런식으로 공백문자가 2개 들어있었던 경우 ["Hello", "", "Hi"] 이렇게 리스트가 만들어진다. 따라서 리스트 원소의 길이가 0이 아닐 경우 upper과 lower 함수를 이용해 대문자 소문자 조건을 충족한다. 리스..

[문제] https://school.programmers.co.kr/learn/courses/30/lessons/12939?language=python3 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [코드] def solution(s): numbers = list(map(int, s.split())) return '%d %d' %(min(numbers), max(numbers))

[문제] https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net [풀이] 문제의 핵심은 현재 수업의 종료 시간이 다음 수업의 종료 시간보다 늦을 경우 회의실 하나를 더 배정해야 한다. 먼저 수업의 시작과 끝 시간을 queue에 넣고 이를 정렬하면 시작 시간이 가장 빠른 수업이 가장 앞에 오게 되기 때문에 첫 수업의 종료시간을 새로운 큐인 room에 넣는다. 두 번째 수업부터 첫 번째 회의와 비교를 하는데 두 번째 수업의 시작시간 < 첫 수업의 종료시간 일 경우 강의실을 새로 배정해야 하고 그렇지 않..

[문제] https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net [풀이] 처음에는 간단하게 sort 함수를 이용해 풀었는데 이는 O(nlogn)으로 우선순위 큐를 이용하면 O(logn)으로 시간복잡도를 줄일 수 있다. 우선순위 큐 사용시, 값을 바꿀 카드 2개를 우선순위 큐에 삽입만 하면 되기 때문에 매번 정렬해야하는 sort 보다 훨씬 효율적인 것이다. 따라서 cards 리스트를 만든 후 heapq 내장 모듈 사..

[문제] https://www.acmicpc.net/problem/9009 9009번: 피보나치 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n www.acmicpc.net [풀이] 우선 피보나치 리스트를 만들어 올바른 값을 미리 넣어준다. 문제에 n의 최댓값이 1,000,000,000이라고 했기 때문에 44번 째 피보나치 수열까지만 구하면 된다. 만들 수 있는 숫자 중 최소 개수로 n을 만들기 위해서는 n 이하의 수 중 가장 n과 가까운 수를 써야 한다. 문제에 나온 예시처럼 100을 만들기 위해서는 (3 + 8 + 89) 도 가능하지만 (3 + 8 + 34 ..

[문제] https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net [풀이] 우선.. for문을 두 번 쓰면 런타임 에러가 난다. 당연함. 100,000명을 2차 반복문으로 돌리면.. 따라서 반복문 한번에 비교를 끝내야한다. 그러기 위해 우선 첫 번째 점수를 기준으로 정렬을 한 후에 rank_asc 변수에 담는다. rank_asc 변수의 첫 번째 원소는 서류 심사가 가장 높은 사람이 오기 때문에 이 사람의 면접 결과가 몇 점이든 무조..