CodeDrive

문제:

당신은 유명 프로그래밍 대회인 KCPC(Korean Collegiate Programming Contest)에 참가하고 있다. 이 대회에서 총 k개의 문제를 풀게 되는데, 어떤 문제에 대한 풀이를 서버에 제출하면 그 문제에 대해 0점에서 100점 사이의 점수를 얻는다. 풀이를 제출한 팀의 ID, 문제 번호, 점수가 서버의 로그에 제출되는 시간 순서대로 저장된다. 한 문제에 대한 풀이를 여러 번 제출할 수 있는데, 그 중 최고 점수가 그 문제에 대한 최종 점수가 된다. (만약 어떤 문제에 대해 풀이를 한번도 제출하지 않았으면 그 문제에 대한 최종 점수는 0점이다.)

당신 팀의 최종 점수는 각 문제에 대해 받은 점수의 총합이고, 당신의 순위는 (당신 팀보다 높은 점수를 받은 팀의 수)+1 이다. 

점수가 동일한 팀이 여럿 있을 수 있는데, 그 경우에는 다음 규칙에 의해서 순위가 정해진다. 

1. 최종 점수가 같은 경우, 풀이를 제출한 횟수가 적은 팀의 순위가 높다. 
2. 최종 점수도 같고 제출 횟수도 같은 경우, 마지막 제출 시간이 더 빠른 팀의 순위가 높다. 

동시에 제출되는 풀이는 없고, 모든 팀이 적어도 한 번은 풀이를 제출한다고 가정하라. 

서버의 로그가 주어졌을 때, 당신 팀의 순위를 계산하는 프로그램을 작성하시오.

입력:

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫 번째 줄에는 팀의 개수 n, 문제의 개수 k, 당신 팀의 ID t, 로그 엔트리의 개수 m을 나타내는 4 개의 정수가 주어진다. 여기서, 3 ≤ n, k ≤ 100, 1 ≤ t ≤ n, 3 ≤ m ≤ 10,000이다. 그 다음 m개의 줄에는 각 풀이에 대한 정보가 제출되는 순서대로 주어진다. 각 줄에는 팀 ID i, 문제 번호 j, 획득한 점수 s를 나타내는 세 개의 정수가 주어진다. 여기서 1 ≤ i ≤ n, 1 ≤ j ≤ k, 0 ≤ s ≤ 100이다. 

출력:

출력은 표준출력을 사용한다. 주어진 각 테스트 데이터에 대해 당신 팀의 순위를 한 줄에 출력하여야 한다

풀이방법:

 주어지는 로그 엔트리들을 팀 ID, 문제 번호대로 정리를 잘 하고, 주어진 조건에 따라서 정렬을 하면 되는 문제다. 따라서 입력을 받을 당시에 defaultdict을 사용하여 raw 데이터를 저장하고, 이 와 동시에 가장 큰 점수와 마지막 인덱스도 저장하도록 한다.

 raw 데이터들은 Counter를 통해 빈도를 계산하며 이를 통합하여 정렬하도록 한다.

문제링크:

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

문제:

게임 개발자인 밀리는 전투력 시스템을 만들어, 캐릭터가 가진 전투력을 기준으로 칭호를 붙여주려고 한다.

예를 들어, 전투력 10,000 이하의 캐릭터는 WEAK, 10,000 초과 그리고 100,000 이하의 캐릭터는 NORMAL, 100,000 초과 그리고 1,000,000 이하의 캐릭터는 STRONG 칭호를 붙여준다고 하자. 이를 IF문으로 작성한다면 아래와 같이 구현할 수 있다.

if power <= 10000
 print WEAK
else if power <= 100000
 print NORMAL
else if power <= 1000000
 print STRONG

혼자서 게임을 개발하느라 매우 바쁜 밀리를 대신해서, 캐릭터의 전투력에 맞는 칭호를 출력하는 프로그램을 작성하자.

입력:

첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105)

두 번째 줄부터 N개의 줄에 각 칭호의 이름을 나타내는 길이 1 이상, 11 이하의 영어 대문자로만 구성된 문자열과 해당 칭호의 전투력 상한값을 나타내는 109 이하의 음이 아닌 정수가 주어진다. 칭호는 전투력 상한값의 비내림차순으로 주어진다. 

N + 2번째 줄부터 M개의 각 줄에는 캐릭터의 전투력을 나타내는 음이 아닌 정수가 주어진다. 해당하는 칭호가 없는 전투력은 입력으로 주어지지 않는다.

출력:

M개의 줄에 걸쳐 캐릭터의 전투력에 맞는 칭호를 입력 순서대로 출력한다. 어떤 캐릭터의 전투력으로 출력할 수 있는 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나만 출력한다.

풀이방법:

 N, M의 범위가 많이 크기 때문에 일반적인 탐색을 사용한다면 시간초과가 발생하게 된다. 따라서 더 빠른 탐색을 사용하여 이분탐색을 사용하도록 한다.

 따라서 python에는 이분탐색을 도와주는 bisect가 있기 때문에 이를 사용할 수 있다. 이 문제는 이분 탐색을 수행하고, 주어진 M을 왼쪽에 삽입하는 것과 같기 때문에 bisect_left 함수를 사용하도록 한다. 주어진 M이 이분 탐색에 의해 삽입될 인덱스를 구하게 된다면, 그 인덱스에 해당하는 칭호의 이름을 출력하도록 한다.

 그리고 출력 조건에서 칭호가 여러 개인 경우 가장 먼저 입력된 칭호 하나를 출력해야 하는데, 입력이 애초에 오름차순으로 주어지기 때문에 따로 고려할 점은 없다.

문제링크:

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

문제:

영문 알파벳 대문자로 이루어진 두 단어가 다음의 두 가지 조건을 만족하면 같은 구성을 갖는다고 말한다.

1. 두 개의 단어가 같은 종류의 문자로 이루어져 있다.
2. 같은 문자는 같은 개수 만큼 있다.

예를 들어 "DOG"와 "GOD"은 둘 다 'D', 'G', 'O' 세 종류의 문자로 이루어져 있으며 양쪽 모두 'D', 'G', 'O' 가 하나씩 있으므로 이 둘은 같은 구성을 갖는다. 하지만 "GOD"과 "GOOD"의 경우 "GOD"에는 'O'가 하나, "GOOD"에는 'O'가 두 개 있으므로 이 둘은 다른 구성을 갖는다.

두 단어가 같은 구성을 갖는 경우, 또는 한 단어에서 한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어 나머지 한 단어와 같은 구성을 갖게 되는 경우에 이들 두 단어를 서로 비슷한 단어라고 한다.

예를 들어 "DOG"와 "GOD"은 같은 구성을 가지므로 이 둘은 비슷한 단어이다. 또한 "GOD"에서 'O'를 하나 추가하면 "GOOD" 과 같은 구성을 갖게 되므로 이 둘 또한 비슷한 단어이다. 하지만 "DOG"에서 하나의 문자를 더하거나, 빼거나, 바꾸어도 "DOLL"과 같은 구성이 되지는 않으므로 "DOG"과 "DOLL"은 비슷한 단어가 아니다.

입력으로 여러 개의 서로 다른 단어가 주어질 때, 첫 번째 단어와 비슷한 단어가 모두 몇 개인지 찾아 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이하이다.

출력:

입력으로 주어진 첫 번째 단어와 비슷한 단어가 몇 개인지 첫째 줄에 출력한다.

풀이방법:

주어진 경우의 수가 많지 않기 때문에 모든 경우의 수에 대해 고려하도록 한다. main으로 선택한 단어는 비교할 단어가 들어올 때마다 복사해서 사용한다.

main 단어와 비교할 단어를 비교하면서 문자가 겹치는 것이 있는지 확인한다. 겹치는 문자가 있다면 remove를 하고 없다면 count를 증가시킨다. 모든 비교를 완료한 뒤에 count가 1 이하, 남은 단어가 1 이하인지 확인하도록 한다. 만약 각 값들이 2보다 크다면 '한 문자를 더하거나, 빼거나, 하나의 문자를 다른 문자로 바꾸어' 조건에 해당하지 않게 된다.

문제링크:

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

문제:

풀이방법:

 시간은 한정되어 있기 때문에 모든 케이스를 다 고려하는 방법으로 문제를 해결했다. 최대로 필요한 객실의 수는 입력으로 들어오는 book_time의 길이와 같다. 따라서 book_time의 높이와 시간의 길이를 가지는 배열(hotel)을 만들도록 한다.

 그리고 각 예약 손님이 사용하는 길이를 hotel 배열에 기록한다. 이 때, 10분간 청소를 하는 시간 또한 같이 고려하도록 한다. 모든 예약 손님에 대해 기록을 완료했다면 세로로 hotel 배열을 탐색하며 가장 많이 겹치는 구간을 답으로 선정한다.

문제링크:

https://school.programmers.co.kr/learn/courses/30/lessons/155651

문제:

세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다.

세준이는 저녁을 먹으러 갔다 와서, 자기가 쓴 수의 일부가 지워져있는 모습을 보고 충격받았다.

세준이는 수를 방금 전과 똑같이 쓰려고 한다. 하지만, N이 기억이 나지 않는다.

남은 수를 이어 붙인 수가 주어질 때, N의 최솟값을 구하는 프로그램을 작성하시오. 아무것도 지우지 않을 수도 있다.)

입력:

첫째 줄에 지우고 남은 수를 한 줄로 이어 붙인 수가 주어진다. 이 수는 최대 3,000자리다.

출력:

가능한 N 중에 최솟값을 출력한다.

풀이방법:

원래 세준이가 쓴 숫자는 다음과 같을 것이다.

12345678910111213141516....

그래서 앞에서 부터 일치하는 숫자들을 찾고서 더 이상 일치할 숫자를 찾을 수 없을 때까지 반복한다.

즉, 234092와 같은 경우에는 1234567891011121314151617181920 중 굵은 숫자의 일부분이 남은 것과 같다. 1부터 하나씩 증가하면서 234092와 비교한다. 2,3,4 에서는 바로 일치되긴 하지만 10부터는 바로 일치되지 않을 것이다. 따라서 자릿수가 늘어난 경우에는 모든 자리에서 일치하는지 여부를 확인하도록 한다.

문제링크:

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

문제:

기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래와 같이 단위 간격으로 놓여 있다. 사람들은 자신의 위치에서 거리가 K 이하인 햄버거를 먹을 수 있다.

위의 상태에서 K = 1인 경우를 생각해보자. 이 경우 모든 사람은 자신과 인접한 햄버거만 먹을 수 있다. 10번의 위치에 있는 사람은 11번 위치에 있는 햄버거를 먹을 수 있다. 이 경우 다음과 같이 최대 5명의 사람이 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 11번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 먹을 수 있는 햄버거가 없음

 K = 2인 경우에는 6명 모두가 햄버거를 먹을 수 있다.

• 2번 위치에 있는 사람: 1번 위치에 있는 햄버거
• 4번 위치에 있는 사람: 3번 위치에 있는 햄버거
• 6번 위치에 있는 사람: 5번 위치에 있는 햄버거
• 9번 위치에 있는 사람: 7번 위치에 있는 햄버거
• 10번 위치에 있는 사람: 8번 위치에 있는 햄버거
• 12번 위치에 있는 사람: 11번 위치에 있는 햄버거

식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K, 사람과 햄버거의 위치가 주어졌을 때, 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

입력:

첫 줄에 두 정수 N과 K가 있다. 그리고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)와 H(햄버거)로 이루어지는 길이 N인 문자열로 주어진다.

출력:

첫 줄에 햄버거를 먹을 수 있는 최대 사람 수를 나타낸다

풀이방법:

 사람을 기준으로 -K인 인덱스부터 햄버거를 우선 배정하는 그리디 알고리즘을 사용한다. 인덱스를 사용하기 때문에 IndexError가 발생하지 않도록 주의한다.

문제링크:

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

문제:

화은이는 이번 영어 시험에서 틀린 문제를 바탕으로 영어 단어 암기를 하려고 한다. 그 과정에서 효율적으로 영어 단어를 외우기 위해 영어 단어장을 만들려 하고 있다. 화은이가 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다.

1. 자주 나오는 단어일수록 앞에 배치한다.
2. 해당 단어의 길이가 길수록 앞에 배치한다.
3. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다

 M보다 짧은 길이의 단어의 경우 읽는 것만으로도 외울 수 있기 때문에 길이가 M이상인 단어들만 외운다고 한다. 화은이가 괴로운 영단어 암기를 효율적으로 할 수 있도록 단어장을 만들어 주자.

입력:

첫째 줄에는 영어 지문에 나오는 단어의 개수 N과 외울 단어의 길이 기준이 되는 M이 공백으로 구분되어 주어진다. (1≤ N ≤100,000, 1≤ M ≤10)

둘째 줄부터 N+1번째 줄까지 외울 단어를 입력받는다. 이때의 입력은 알파벳 소문자로만 주어지며 단어의 길이는 10을 넘지 않는다.

단어장에 단어가 반드시 1개 이상 존재하는 입력만 주어진다.

출력:

화은이의 단어장에 들어 있는 단어를 단어장의 앞에 위치한 단어부터 한 줄에 한 단어씩 순서대로 출력한다.

풀이방법:

defaultdict을 사용해서 나오는 횟수를 카운팅하며 (key, value) 값을 조건에 맞게 정렬하고 출력하도록 한다.

시간 제한이 걸려 있는 문제이므로 일반 input 대신 sys.stdin.readline을 사용해야 하며, rstrip()으로 개행문자를 제거해 주도록 한다.

문제링크:

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

문제:

찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.

요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.

찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.

찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자.

입력:

첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.

둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다.

출력:

첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.

만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다.

풀이방법:

X만큼의 구간을 슬라이딩 하면서 최댓값을 갱신하고, 최댓값이랑 같은 경우에는 기간을 증가시켜준다.

문제링크:

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

문제:

IQ Test의 문제 중에는 공통된 패턴을 찾는 문제가 있다. 수열이 주어졌을 때, 다음 수를 찾는 문제이다.

예를 들어, 1, 2, 3, 4, 5가 주어졌다. 다음 수는 무엇인가? 당연히 답은 6이다. 약간 더 어려운 문제를 보면, 3, 6, 12, 24, 48이 주어졌을 때, 다음 수는 무엇인가? 역시 답은 96이다.

이제 제일 어려운 문제를 보자.

1, 4, 13, 40이 주어졌을 때, 다음 수는 무엇일까? 답은 121이다. 그 이유는 항상 다음 수는 앞 수*3+1이기 때문이다.

은진이는 위의 3문제를 모두 풀지 못했으므로, 자동으로 풀어주는 프로그램을 작성하기로 했다. 항상 모든 답은 구하는 규칙은 앞 수*a + b이다. 그리고, a와 b는 정수이다.

수 N개가 주어졌을 때, 규칙에 맞는 다음 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 N개의 수가 주어진다. 이 수는 모두 절댓값이 100보다 작거나 같은 정수이다.

출력:

다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다.

풀이방법:

문제에서 찾아야 하는 a와 b를 찾는 것은 연립방정식을 사용한다면 쉽게 찾을 수 있다. 하지만 A, B와 같이 특이 케이스들이 다수 존재하기 때문에 이를 위한 노력이 필요하다. 다음과 같은 케이스들이 존재할 수 있다.

1. N이 1인 경우

N이 1인 경우에는 a와 b를 알 수 없기 때문에 다음에 여러 수가 존재할 수 있다. -> A

2. N이 2인 경우

N이 2인 경우에도 a와 b를 알 수 없기 때문에 여러 수가 존재할 수 있다.(A) 하지만 첫 두 수가 같다면 a=1, b=0인 특수한 케이스에 해당하기에 마지막 수를 출력한다.

3. N이 3 이상인 경우

 N이 3 이상이면 연립방정식을 통해 a와 b를 구할 수 있게 된다. 따라서 첫 세 수를 사용하여 a와 b를 구하도록 한다. 이 때, a와 b를 정수라는 조건이 있기 때문에 소수가 구해지게 된다면 B를 출력하도록 한다.

 a와 b를 정상적으로 구해도 첫 세 수를 통해 구한 값이기 때문에 이 규칙이 주어진 배열 끝까지 동작하는지 확인하는 작업이 필요하다. 규칙이 정상적으로 작동한다면 규칙을 사용하여 다음 수를 출력하고, 그렇지 않다면 B를 출력한다.

문제링크:

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

문제:

대한민국을 비롯한 대부분의 나라에서는 터널 내에서의 차선 변경을 법률로 금하고 있다. 조금만 관찰력이 있는 학생이라면 터널 내부에서는 차선이 파선이 아닌 실선으로 되어 있다는 것을 알고 있을 것이다. 이는 차선을 변경할 수 없음을 말하는 것이고, 따라서 터널 내부에서의 추월은 불가능하다.

소문난 명콤비 경찰 대근이와 영식이가 추월하는 차량을 잡기 위해 한 터널에 투입되었다. 대근이는 터널의 입구에, 영식이는 터널의 출구에 각각 잠복하고, 대근이는 차가 터널에 들어가는 순서대로, 영식이는 차가 터널에서 나오는 순서대로 각각 차량 번호를 적어 두었다.

N개의 차량이 지나간 후, 대근이와 영식이는 자신들이 적어 둔 차량 번호의 목록을 보고, 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차들이 몇 대 있다는 것을 알게 되었다. 대근이와 영식이를 도와 이를 구하는 프로그램을 작성해 보자.

입력:

입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이가 적은 차량 번호 목록이 주어진다. 각 차량 번호는 6글자 이상 8글자 이하의 문자열로, 영어 대문자('A'-'Z')와 숫자('0'-'9')로만 이루어져 있다.

같은 차량 번호가 두 번 이상 주어지는 경우는 없다.

출력:

첫째 줄에 터널 내부에서 반드시 추월을 했을 것으로 여겨지는 차가 몇 대인지 출력한다.

풀이방법:

먼저 들어간 차량부터 1이라고 라벨링을 할 때, 추월한 차량의 뒤 차량들 중에는 본인 차의 숫자보다 작은 숫자가 반드시 존재하게 된다. 따라서 이러한 경우를 추월한 차량이라고 생각하고 갯수를 세도록 한다.

문제링크:

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