코딩 테스트 연습/백준

1. 문제 https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 각 지원자의 서류심사 성적, 면접 성적의 순위가 주어진다. 서류심사 성적, 면접 성적 둘 모두가 다른 지원자보다 낮은 지원자가 있다면, 그 지원자는 선발 될 수 없다. 이 조건을 만족시키면서 선발할 수 있는 최대 인원수를 출력하는 문제이다. 2. 풀이 STEP1. 각 지원자의 서류심사 성적, 면접 성적의 순위를 벡터에 받아 저장한다. 그리고 sort()를 활용하여 ..

1. 문제 https://www.acmicpc.net/problem/1141 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, www.acmicpc.net N개의 단어가 주어졌을때, 접두사X 집합의 최대 크기를 구하는 문제이다. 즉, 어떤 단어가 다른 단어의 접두사가 되지 않는 단어의 갯수를 찾으면 된다. 2. 풀이 접두사를 찾는 문제라는 것을 인지하니 정렬이 떠올랐다. sort()를 활용하여 정렬을 하면, 사전처럼 접두사가 될 수 있는 단어가 다른 단어들의 앞에 정렬되기 때문이다..

1. 문제 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net N개의 회의에 대해서 회의의 시작 시간과 종료 시간이 주어졌을 때, 각 회의가 겹치지 않게 회의실을 이용할 수 있는 최대 회의의 개수를 구하는 문제이다. 회의실의 수는 1개이고, 회의가 종료되는 것과 동시에 다음 회의가 시작될 수 있다. 2. 풀이 먼저 시작하더라도 늦게 끝난다면 그 회의는 선택될 수 없다. 즉, '종료 시간'이 이 문제의 주인공임을 알 수 있다. 남은 회의 중 종료 시간이 가장 빠른 회의의 시작 시간이 직전 회의의 종료 시간 이후라면 그 회의를 선택해 주면 된다. 우선, 각 회의의 시..

1. 문제 https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 숫자와 부호들이 번갈아 가면서 등장하는데, 적절하게 괄호를 쳐서 만들 수 있는 최솟값을 구하면 된다. 가장 처음과 마지막은 숫자이고, 연속해서 두 개 이상의 연산자가 나타나지는 않는다. 예외처리는 고려하지 않아도 될 것 같다. 2. 풀이 마이너스가 한 번이라도 등장하면 그 뒤는 괄호 쳐서 다 마이너스 처리하면 되는 거 아닌가? 라고 생각했다. 여기까지는 쉽게 생각했는데 문제는 문자..