CodeDrive

문제:

상근이는 세계적인 소프트웨어 회사 기글에서 일한다. 이 회사의 가장 큰 특징은 자유로운 출퇴근 시간이다. 따라서, 직원들은 반드시 9시부터 6시까지 회사에 있지 않아도 된다.

각 직원은 자기가 원할 때 출근할 수 있고, 아무때나 퇴근할 수 있다.

상근이는 모든 사람의 출입카드 시스템의 로그를 가지고 있다. 이 로그는 어떤 사람이 회사에 들어왔는지, 나갔는지가 기록되어져 있다. 로그가 주어졌을 때, 현재 회사에 있는 모든 사람을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다.(2<=n<=10^6) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고, "enter"나 "leave"가 주어진다. "enter"인 경우는 출근, "leave"인 경우는 퇴근이다.

회사에 동명이인이 없으며, 대소문자가 다른 경우에는 다른 이름이다. 사람들의 이름은 알파벳 대소문자로 구성된 5글자 이하의 문자열이다.

출력:

현재 회사에 있는 사람의 이름을 사전 순의 역순으로 한 줄에 한 명씩 출력한다.

풀이방법:

 동명이인이 없고, 대소문자가 다른 경우에는 다른 이름이기 때문에 한 사람이 출근하고 퇴근하는 것은 독립적이다. 따라서 python의 dict을 이용해서 해쉬를 구성하도록 했다. 

 "enter"와 "leave"와 상관 없이 처음 이름이 등장한다면 출근이고, 두 번째로 이름이 등장한다면 퇴근하는 것이라 생각하고, 처음 등장하면 True로 값을 새로 저장하고, 다시 등장하면 False로 바꿔주도록 했다.

 모두 확인했다면 dict의 items()를 사용해서 key, value 쌍으로 묶어주고, 역순 정렬을 한 뒤 , value 값이 True인 것만 출력하도록 했다.

문제링크:

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

문제:

Vigenere cipher이라는 암호화 방법은 암호화하려는 문장(평문)의 단어와 암호화 키를 숫자로 바꾼 다음, 평문의 단어에 해당하는 숫자에 암호 키에 해당하는 숫자를 더하는 방식이다. 이 방법을 변형하여 평문의 단어에 암호화 키에 해당하는 숫자를 빼서 암호화하는 방식을 생각해 보자.

예를 들어 암호화 키가 love이고, 암호화할 문장이 "nice day"라면 다음과 같이 암호화가 이루어진다.

제시된 평문의 첫 번째 문자인 'n'은 해당 암호화 키 'l'의 알파벳 순서가 12이므로 알파벳상의 순서에서 'n'보다 12앞의 문자인 'b'로 변형된다.

변형된 문자가 'a'이전의 문자가 되면 알파벳 상에서 맨 뒤로 순서를 돌린다. 예를 들면 평문의 세 번째 문자인 'c'는 알파벳 상에서 3번째이고 대응하는 암호화키 'V'는 알파벳 순서 22로 'c'에서 22 앞으로 당기면 'a'보다 훨씬 앞의 문자이어야 하는데, 'a' 앞의 문자가 없으므로 'z'로 돌아가 반복되어 'g'가 된다. 즉 평문의 문자를 암호화키의 문자가 알파벳 상에서 차지하는 순서만큼 앞으로 뺀 것으로 암호화한다.

평문의 문자가 공백 문자인 경우는 그 공백 문자를 그대로 출력한다.

이과 같은 암호화를 행하는 프로그램을 작성하시오.

입력:

첫째 줄에 평문이, 둘째 줄에 암호화 키가 주어진다.

평문은 알파벳 소문자와 공백문자(space)로만 구성되며, 암호화 키는 알파벳 소문자만으로 구성된다. 평문의 길이는 공백까지 포함해서 30000자 이하이다.

출력:

첫 번째 줄에 암호문을 출력한다.

풀이방법:

암호화 키와 평문의 차이를 알아야 하므로 ascii코드 값으로 바꿔 주는 ord 함수를 사용한다. 이를 이용해서 암호화 키와 평문의 차이를 구하고 이 값이 0보다 큰지 작은지를 결정한다.

0보다 크다면 해당 차이 값이 96을 더해주도록 한다.(소문자 'a'의 ascii는 97이다.)

만약 작다면 26을 추가로 더해서 뒤에서 부터 이동하도록 한다. 

문제링크:

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

문제:

김형택은 탑문고의 직원이다. 김형택은 계산대에서 계산을 하는 직원이다. 김형택은 그날 근무가 끝난 후에, 오늘 판매한 책의 제목을 보면서 가장 많이 팔린 책의 제목을 칠판에 써놓는 일도 같이 하고 있다.

오늘 하루 동안 팔린 책의 제목이 입력으로 들어왔을 때, 가장 많이 팔린 책의 제목을 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고, 알파벳 소문자로만 이루어져 있다.

출력:

첫째 줄에 가장 많이 팔린 책의 제목을 출력한다. 만약 가장 많이 팔린 책이 여러 개일 경우에는 사전 순으로 가장 앞서는 제목을 출력한다.

풀이방법:

 hash를 사용해서 책의 제목을 효과적으로 세도록한다. python에서는 dict 자료형을 사용해서 구현하면 된다.

책의 이름을 key로 하고 책의 개수를 value로 설정한다. 따라서 get을 사용해서 dict에(전체 책 리스트) 해당 key(책의 이름)가 있는지 확인하고 있다면 key에 해당하는 value(책의 개수)를 하나 올려주고, 없다면 해당 key를 dict에 value가 1인 상태로 넣어준다.

 이렇게 책을 hash 상태로 정리했다면 items()를 통해서 key,value 쌍으로 가져오고, sort 조건에 맞게 정렬해서 값을 구하도록 한다.

문제링크:

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

문제:

N*M 크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 열에 평행해야 한다.

입력:

첫째 줄에 N과 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 수가 주어진다.

출력:

첫째 줄에 정답 정사각형의 크기를 출력한다.

풀이방법:

N과 M의 크기가 50보다 작기 때문에 브루트 포스로 전부 탐색을 해도 된다. 1x1의 정사각형은 반드시 존재하기 때문에 넘어가고 가로, 세로 길이가 2인 정사각형부터 탐색을 시작한다. 한 변의 길이가 n이지만 좌표상의 차이는 n-1이 나게 된다. 따라서 이 점을 이용해서 꼭짓점의 값들이 같은지 탐색하고 같다면 answer를 변경하도록 한다.

만약 모두 탐색을 했는데 초기 answer이 변하지 않는다면 가장 큰 정사각형은 1x1이므로 1을 출력하도록 한다.

문제링크:

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

문제:

우리 나라는 가족 혹은 친척들 사이의 관계를 촌수라는 단위로 표현하는 독특한 문화를 가지고 있다. 이러한 촌수는 다음과 같은 방식으로 계산된다. 기본적으로 부모와 자식 사이를 1촌으로 정의하고 이로부터 사람들 간의 촌수를 계산한다. 예를 들면 나와 아버지, 아버지와 할아버지는 각각 1촌으로 나와 할아버지는 2촌이 되고, 아버지 형제들과 할아버지는 1촌, 나와 아버지 형제들과는 3촌이 된다.

여러 사람들에 대한 부모 자식들 간의 관계가 주어졌을 때, 주어진 두 사람의 촌수를 계산하는 프로그램을 작성하시오.

입력:

사람들은 1, 2, 3, ..., n (1<=n<=100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘때 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.

각 사람의 부모는 최대 한 명만 주어진다.

출력:

입력에서 요구한 두 사람의 촌수를 나타내는 정수를 출력한다. 어떤 경우에는 두 사람의 친척 관계가 전혀 없어 촌수를 계산할 수 없을 때가 있다. 이 때에는 -1을 출력해야 한다.

풀이방법:

두 사람이 얼마나 긴 간격으로 연결되어 있는지 확인하는 문제이기 때문에 dfs나 bfs로 풀어야 할 것 같다고 생각했다. dfs로도 풀 수 있는지 정확히 모르지만, 두 사람 사이의 몇 level(단계)가 있는지 확인하면 되는 문제 이므로 bfs를 사용하기로 했다.

형제들 같은 경우에는 2촌으로 계산되는데 그 이유가 (나에서 부모님으로 1촌) + (부모님에서 형제로 1촌) 이기 때문이다. 따라서 이러한 관계를 알기 위해서는 양방향으로 이동할 수 있도록 relation을 만들었고, 중복방문을 하지 않기 위해서 visited를 만들었다.

처음 시작해야 하는 사람의 번호로 시작한다. 그리고 그 사람과 관계가 있는 사람들 중 방문하지 않았던 사람만 temp라는 배열에 담고 방문한 것으로 visited를 변경한다. 그리고 이 temp에 나와의 관계가 알고 싶은 사람의 번호가 있는지 확인하고, 있다면 break 없다면 temp의 길이를 재서 탐색할 사람이 있는지 확인한다. temp에 더 탐색할 사람이 있다면 위의 행동을 다시 반복하고, 더 이상 탐색할 사람이 없다면 친척 관계가 전혀 없다는 것으로 출력하면 된다.

그리고 최종 출력에서 +1을 했는데, 이 이유는 temp에 내가 원하는 사람의 번호가 있기 때문에 그 관계로 이동한다는 행동이 빠져있었기 때문에 +1을 해서 출력하도록 했다.

문제링크:

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

문제:

반도체를 설계할 때 n개의 포트를 다른 n개의 포트와 연결해야 할 때가 있다.

예를 들어 왼쪽 그림이 n개의 포트와 다른 n개의 포트를 어떻게 연결해야 하는지를 나타낸다. 하지만 이와 같이 연결을 할 경우에는 연결선이 서로 꼬이기 때문에 이와 같이 연결할 수 없다. n개의 포트가 다른 n개의 포트와 어떻게 연결되어야 하는지가 주어졌을 때, 연결선이 서로 꼬이지(겹치지, 교차하지) 않도록 하면서 최대 몇 개까지 연결할 수 있는지를 알아내는 프로그램을 작성하시오.

입력:

첫째 줄에 정수 n(1<=n<=40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, ... , n번 포트와 연결되어야 하는 포트 번호가 주어진다. 이 수들은 1 이상 n 이하이며 서로 같은 수는 없다고 가정하자.

출력:

첫째 줄에 최대 연결 개수를 출력한다.

풀이방법:

복잡해 보이지만 LIS 문제라고 생각하면 쉽게 풀 수 있다. LIS를 푸는 방법에는 여러 가지가 있지만 가장 대표적인 방법인 DP를 사용해서 문제를 풀어보았다.

DP로 푸는 방법은 O(N^2)의 시간 복잡도이기 때문에 시간이 오래 걸리게 된다. 따라서 O(NlogN)으로 푸는 방법이 있다해서 다음을 참고 하였다.

https://dyngina.tistory.com/16

여기서 O(NlogN)이 두 개 있었는데 lower_bound는 python의 bisect를 쓰면 될 것 같다. 이번에는 인덱스 트리를 사용해서 문제를 풀어 보았다. 인덱스 트리를 만들기 위한 과정에서 시간이 많이 소요 되는 것 같아서 이 역시도 pypy3로 통과했다. 아마도 bisect를 사용하면 python으로도 통과할 수 있을 것 같다.

문제링크:

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

문제:

1부터 N까지의 수를 이어서 쓰면 다음과 같이 새로운 하나의 수를 얻을 수 있다.

1234567891011121314151617181920212223...

이렇게 만들어진 새로운 수는 몇 자리 수일까? 이 수의 자릿수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N(1<=N<=100,000,000)이 주어진다.

출력:

첫째 줄에 새로운 수의 자릿수를 출력한다.

풀이방법:

처음에는 브루트 포스로 알고리즘 분류가 되어 있어서 그냥 N까지의 수를 다 붙인 다음에 길이를 구하는 방식으로 했는데 시간초과가 발생했다.

그래서 처음 받은 N을 기준으로 자릿수를 줄여나가면서 더하는 방식으로 바꾸어서 해결을 했다.

ex) 3자리수의 갯수*3 + 2자리수의 갯수*2 ....

문제링크:

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

문제:

동호는 새악대로 T 통신사의 새 핸드폰 옴머나를 샀다. 새악대로 T 통신사는 동호에게 다음 두 가지 요금제 중 하나를 선택하라고 했다.

1. 영식 요금제

2. 민식 요금제

영식 요금제는 30초마다 10원씩 청구된다. 이 말은 만약 29초 또는 그 보다 적은 시간 통화를 했으면 10원이 청구된다. 만약 30초부터 59초 사이로 통화를 했으면 20원이 청구된다.

민식 요금제는 60초마다 15원씩 청구된다. 이 말은 만약 59초 또는 그 보다 적은 시간 통화를 했으면 15원이 청구된다. 만약 60초부터 119초 사이로 통화를 했으면 30원이 청구된다.

동호가 저번 달에 새악대로 T 통신사를 이용할 때 통화 시간 목록이 주어지면 어느 요금제를 사용 하는 것이 저렴한지 출력하는 프로그램을 작성하시오.

입력:

동호가 저번 달에 이용한 통화의 개수 N이 주어진다. N은 20보다 작거나 같은 자연수이다. 둘째 줄에 통화 시간 N개가 주어진다. 통화 시간은 10,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 싼 요금제의 이름을 출력한다. 그 후에 공백을 사이에 두고 요금이 몇 원 나오는지 출력한다. 만약 두 요금제의 요금이 모두 같으면 영식을 먼저 쓰고 민식을 그 다음에 쓴다.

영식은 Y로, 민식은 M으로 출력한다.

풀이방법:

처음에 정답 비율이 30%대이길래 난이도가 있는 문제인 줄 알았는데 생각보다 간단했던 문제였다.

통화한 시간들을 배열에 담고 각 30초, 60초로 나눈 몫에 1을 더하고 10원, 15원을 곱한 것들을 계속 누적해서 더하고 나 중에 이를 비교해 형식에 맞게 출력하면 되는 문제였다.

아마도 정답률이 낮았던 이유가 형식을 맞지 못하게 출력해서 그런 것 같으므로 python의 format을 사용해서 형식을 맞춰 주었다.

문제링크:

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

문제:

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10+20+25+20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.

2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.

3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력:

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력:

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

풀이방법:

조건3인 마지막 계단을 무조건 밟아야 하기 때문에 경우의 수는 다음 2개만 존재하게 된다.

1. 마지막칸의 전칸을 밟고 마지막 칸으로 이동하는 경우

2. 마지막의 전전칸을 밟고 마지막칸을 밟는 경우

그런데 1번의 경우에는 조건2가 있기 때문에 이를 고려해 줘야 한다. 

이 것을 코드로 구현하게 되면 다음과 같다. 

1번 -> dp[n-3] + stair[n-1] + stair[n]

2번 -> dp[n-2] + stair[n]

따라서 이 둘중 max 값을 골라서 진행하면 된다.

이를 위해서 dp[0], dp[1], dp[2]를 초기화 해줬는데, 만약 계단의 개수가 이보다 적게 되면 런타임에러가 발생하게 된다.

따라서 stair를 공백의 빈 배열을 만들어도 되긴 하는데, 단순히 조건문을 추가해서 답을 구하도록 만들었다.

문제링크:

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

문제:

총 N개의 시험장이 있고, 각각의 시험장마다 응시자들이 있다. i번 시험장에 있는 응시자의 수는 Ai명이다.

감독관은 총감독관과 부감독관으로 두 종류가 있다. 총감독관은 한 방에서 감시할 수 있는 응시자의 수가 B명이고, 부감독관은 한 방에서 감시할 수 있는 응시자의 수가 C명이다.

각각의 시험장에 총감독관은 오직 1명만 있어야 하고, 부감독관은 여러 명 있어도 된다.

각 시험장마다 응시생들을 모두 감시해야 한다. 이때, 필요한 감독관 수의 최솟값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 시험장의 개수 N(1<=N<=1,000,000)이 주어진다.

둘째 줄에는 각 시험장에 있는 응시자의 수 Ai(1<=Ai<=1,000,000)가 주어진다.

셋째 줄에는 B와 C가 주어진다.(1<=B,C<=1,000,000)

출력:

각 시험장마다 응시생을 모두 감독하기 위해 필요한 감독관의 최소 수를 출력한다.

풀이방법:

총감독관은 시험장마다 1명씩만 존재해야 하므로 answer를 시험장의 수로 초기화한다. 

그리고 각 시험장마다 총감독관이 감시할 수 있는 인원을 빼고 아직 감시해야 할 인원들이 남았다면 이를 부감독관에게 할당하도록 한다. 

문제링크:

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