CodeDrive

문제:

위대한 해커 창영이는 모든 암호를 깨는 방법을 발견했다. 그 방법은 빈도를 조사하는 것이다.

창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 메시지는 숫자 N개로 이루어진 수열이고, 숫자는 모두 C보다 작거나 같다. 창영이는 이 숫자를 자주 등장하는 빈도순대로 정렬하려고 한다.

만약, 수열의 두 수 X와 Y가 있을 때, X가 Y보다 수열에서 많이 등장하는 경우에는 X가 Y보다 앞에 있어야 한다. 만약, 등장하는 횟수가 같다면, 먼저 나온 것이 앞에 있어야 한다.

이렇게 정렬하는 방법을 빈도 정렬이라고 한다.

수열이 주어졌을 때, 빈도 정렬을 하는 프로그램을 작성하시오.

입력:

첫째 줄에 메시지의 길이 N과 C가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ C ≤ 1,000,000,000)

둘째 줄에 메시지 수열이 주어진다.

출력:

첫째 줄에 입력으로 주어진 수열을 빈도 정렬한 다음 출력한다.

풀이방법:

 python의 Counter는 편리하고 빠르게 개수를 세도록 지원한다. Counter가 가진 함수 중에서 most_common이 자주 등장하는 순서로 정렬을 하는데, 개수가 같은 요소는 처음 발견된 순서를 유지한다. 이 문제에서 요구하는 조건과 같기 때문에 이를 사용하여 개수를 집계하고, 정렬된 순서에 따라 출력을 하도록 한다.

문제링크:

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

문제:

이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 1시간 전에 깨고 말았다. 안타깝게도 자는 동안 키보드가 잘못 눌려서 보고서의 모든 글자가 A와 B로 바뀌어 버렸다! 그래서 평석이는 보고서 작성을 때려치우고 보고서에서 '좋은 단어'나 세보기로 마음 먹었다.

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.

입력:

첫째 줄에 단어의 수 N이 주어진다. (1 ≤ N ≤ 100)

다음 N개 줄에는 A와 B로만 이루어진 단어가 한 줄에 하나씩 주어진다. 단어의 길이는 2와 100,000사이이며, 모든 단어 길이의 합은 1,000,000을 넘지 않는다.

출력:

첫째 줄에 좋은 단어의 수를 출력한다.

풀이방법:

단어들을 stack에 다음과 같은 규칙을 따르면서 A나 B를 하나씩 넣도록 한다.

 1. stack이 비어있다면 추가한다.

 2. stack의 마지막 값과 같다면 pop을 하고, 다르다면 append한다.

이 과정을 마치고 난 뒤에 stack에 값이 남아 있다면 이는 '좋은 단어'가 아니라는 것을 의미한다. 따라서 stack이 비어있을 때에만 count를 올려주도록 한다.

문제링크:

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

문제:

무한 수열 A는 다음과 같다.

• A0 = 1
• Ai = A⌊i/P⌋ + A⌊i/Q⌋ (i ≥ 1)

N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 3개의 정수 N, P, Q가 주어진다.

출력:

첫째 줄에 AN을 출력한다.

풀이방법:

 문제에서 명확하게 점화식이 주어졌기 때문에 다이나믹 프로그래밍을 사용하도록 한다. 하지만 주어진 조건의 N, P, Q이 매우 크기 때문에 list를 사용해서 구현을 한다면 메모리가 터지는 문제점이 있다. 따라서 최대한 쓰지 않는(비어있는) 값들을 줄이기 위해서 dict 자료형에다가 값들을 mapping 하도록 한다. 빠른 구현을 위해서 defaultdict을 사용해 초기화하는 과정을 간단하게 구현할 수 있도록 했다.

문제링크:

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

문제:

수빈이는 동생에게 "가운데를 말해요" 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야 한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다.

예를 들어 수빈이가 동생에게 1, 5, 2, 10, -99, 7, 5를 순서대로 외쳤다고 하면, 동생은 1, 1, 2, 2, 2, 2, 5를 차례대로 말해야 한다. 수빈이가 외치는 수가 주어졌을 때, 동생이 말해야 하는 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

출력:

한 줄에 하나씩 N줄에 걸쳐 수빈이의 동생이 말해야하는 수를 순서대로 출력한다.

풀이방법:

시간 제한이 매우 엄격하게 정해져 있기 때문에 max_heap과 min_heap를 두 개를 사용해서 중간값을 구하도록 한다. 기본적인 아이디어는 양쪽에 채워나가면서 heap으로 정리했을 때, 가운데 값을 기준으로 정렬되는 것을 이용한다. max_heap에는 중간값보다 낮은 값들을 채워나가고, min_heap은 중간값보다 큰 값이 채워지도록 하게 한다. 개수가 짝수개인 경우 두 수 중에 작은 수를 말해야 하기 때문에 max_heap에 있는 값을 출력하도록 한다.  

문제링크:

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

문제:

총 N개의 문자열로 이루어진 집합 S가 주어진다.

입력으로 주어지는 M개의 문자열 중에서 집합 S에 포함되어 있는 것이 총 몇 개인지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 문자열의 개수 N과 M (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10,000)이 주어진다.

다음 N개의 줄에는 집합 S에 포함되어 있는 문자열들이 주어진다.

다음 M개의 줄에는 검사해야 하는 문자열들이 주어진다.

입력으로 주어지는 문자열은 알파벳 소문자로만 이루어져 있으며, 길이는 500을 넘지 않는다. 집합 S에 같은 문자열이 여러 번 주어지는 경우는 없다.

출력:

첫째 줄에 M개의 문자열 중에 총 몇 개가 집합 S에 포함되어 있는지 출력한다.

풀이방법:

이 문제는 다른 방법을 사용하면 쉽게 풀 수 있겠지만, 트라이 자료구조를 활용해서 풀어보았다. 생각보다 시간제한이 어려웠던 문제라서 최대한 시간을 줄이고자, Node를 정의해서 풀었던 다른 문제들과는 달리 하나의 class만으로 해결해보도록 구성해보았다.

class Trie(object):
    @classmethod
    def __init__(self):
        self.root = {}
        self.terminate = 'eof'
        
    @classmethod
    def insert(self, string):
        currNode = self.root
        for chr_ in string:
            if chr_ not in currNode:
                currNode[chr_] = {}
            currNode = currNode[chr_]
        currNode[self.terminate] = string
        
    @classmethod
    def search(self,string):
        currNode = self.root
        for chr_ in string:
            if chr_ in currNode:
                currNode = currNode[chr_]
            else:
                return False
        if 'eof' in currNode.keys():
            return True
        else:
            return False

n, m = map(int,input().split())
T = Trie()
for _ in range(n):
    T.insert(input())
answer = 0
for _ in range(m):
    if T.search(input()):
        answer+=1
        
print(answer)

문제링크:

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

문제:

오늘은 신승원의 생일이다.

박승원은 생일을 맞아 신승원에게 인천국제공항을 선물로 줬다.

공항에는 G개의 게이트가 있으며 각각은 1에서 G까지의 번호를 가지고 있다.

공항에는 P개의 비행기가 순서대로 도착할 예정이며, 당신은 i번째 비행기를 1번부터 gi (1 ≤ gi ≤ G) 번째 게이트중 하나에 영구적으로 도킹하려 한다. 비행기가 어느 게이트에도 도킹할 수 없다면 공항이 폐쇄되고, 이후 어떤 비행기도 도착할 수 없다.

신승원은 가장 많은 비행기를 공항에 도킹시켜서 박승원을 행복하게 하고 싶어한다. 승원이는 비행기를 최대 몇 대 도킹시킬 수 있는가?

입력:

첫 번째 줄에는 게이트의 수 G (1 ≤ G ≤ 105)가 주어진다.

두 번째 줄에는 비행기의 수 P (1 ≤ P ≤ 105)가 주어진다.

이후 P개의 줄에 gi (1 ≤ gi ≤ G) 가 주어진다.

출력:

승원이가 도킹시킬 수 있는 최대의 비행기 수를 출력한다.

풀이방법:

유니온-파인드 알고리즘을 사용해서 문제를 풀려고 한다. 우선 초기 게이트들은 각자 번호로 초기화를 한다. 그리고 앞으로 들어오는 비행기를 게이트에 할당하기 시작한다. 이 때 할당하는 방법은 find()함수로 진행을 하며, 비행기의 번호에 따라 가장 큰 게이트에 도킹을 한다. 즉 gi번 비행기는 gi게이트에 할당하도록 하고, 만약 gi게이트에 이미 도킹 된 비행기가 있다면 그 전 게이트(gi-1)에 할당한다. 이렇게 계속해서 할당을 하다가 0번째 게이트를 만나게 되면 더 이상 도킹을 진행할 수 없기 때문에 공항을 폐쇄한다.

문제링크:

www.acmicpc.net/problem/10775