CodeDrive

문제:

상근이는 수학시간에 딴 짓을 하다가 선생님께 걸렸다. 선생님은 상근이에게 이번 주말동안 반성하라며 엄청난 숙제를 내주었다.

선생님이 상근이에게 준 종이에는 숫자와 알파벳 소문자로 되어있는 글자가 N줄있다. 상근이는 여기서 숫자를 모두 찾은 뒤, 이 숫자를 비내림차순으로 정리해야한다. 숫자의 앞에 0이 있는 경우에는 정리하면서 생략할 수 있다.

글자를 살펴보다가 숫자가 나오는 경우에는, 가능한 가장 큰 숫자를 찾아야 한다. 즉, 모든 숫자의 앞과 뒤에 문자가 있거나, 줄의 시작 또는 끝이어야 한다.

예를 들어, 01a2b3456cde478에서 숫자를 찾으면 1, 2, 3456, 478이다.

선생님이 준 종이의 내용이 주어졌을 때, 상근이의 숙제를 대신하는 프로그램을 작성하시오.

입력:

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

다음 N개의 줄에는 각 줄의 내용이 주어진다. 각 줄은 최대 100글자이고, 항상 알파벳 소문자와 숫자로만 이루어져 있다.

출력:

종이에서 찾은 숫자의 개수를 M이라고 하면, 출력은 M줄로 이루어져야 한다. 각 줄에는 종이에서 찾은 숫자를 하나씩 출력해야 한다. 이때, 비내림차순으로 출력해야 한다. 비내림차순은 내림차순의 반대인 경우인데, 다음 수가 앞의 수보다 크거나 같은 경우를 말한다.

풀이방법:

 python의 isdigit 기능을 사용해서 숫자를 찾도록 한다. 숫자가 연속해서 나오는 경우에는 이어붙이고, 숫자가 아닌 경우에만 배열에 담도록한다. 그리고 맨 끝의 숫자(lo3za4)에서 4도 탐색하기 위해서 for 문이 끝나고 나서 숫자가 남아있다면 추가로 넣어주도록한다.

 이렇게 모든 문자열 탐색이 끝난 뒤에, 배열에 있는 모든 숫자를 int형으로 바꾼 뒤에 정렬을 하도록 한다. (01과 같은 것을 제거하기 위함)

문제링크:

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

문제:

2차원 좌표 평면 위에 있는 점 3개 P1, P2, P3가 주어진다. P1, P2, P3를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 P1의 (x1, y1), 둘째 줄에 P2의 (x2, y2), 셋째 줄에 P3의 (x3, y3)가 주어진다. (-10,000 ≤ x1, y1, x2, y2, x3, y3 ≤ 10,000) 모든 좌표는 정수이다. P1, P2, P3의 좌표는 서로 다르다.

출력:

P1, P2, P3를 순서대로 이은 선분이 반시계 방향을 나타내면 1, 시계 방향이면 -1, 일직선이면 0을 출력한다.

풀이방법:

 2차원 평면에서 점 3개의 방향을 판단하는 알고리즘을 CCW(Counter Clockwise)라고 한다. 외적을 사용하는 알고리즘인데, 아래 링크에서 자세하게 잘 설명해준 것 같아서 참조하도록 한다.

참고링크: https://degurii.tistory.com/47

문제링크:

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

문제:

좋은 패스워드를 만드는것은 어려운 일이다. 대부분의 사용자들은 buddy처럼 발음하기 좋고 기억하기 쉬운 패스워드를 원하나, 이런 패스워드들은 보안의 문제가 발생한다. 어떤 사이트들은 xvtpzyo 같은 비밀번호를 무작위로 부여해 주기도 하지만, 사용자들은 이를 외우는데 어려움을 느끼고 심지어는 포스트잇에 적어 컴퓨터에 붙여놓는다. 가장 이상적인 해결법은 '발음이 가능한' 패스워드를 만드는 것으로 적당히 외우기 쉬우면서도 안전하게 계정을 지킬 수 있다.

회사 FnordCom은 그런 패스워드 생성기를 만들려고 계획중이다. 당신은 그 회사 품질 관리 부서의 직원으로 생성기를 테스트해보고 생성되는 패스워드의 품질을 평가하여야 한다. 높은 품질을 가진 비밀번호의 조건은 다음과 같다.

1. 모음(a,e,i,o,u) 하나를 반드시 포함하여야 한다.
2. 모음이 3개 혹은 자음이 3개 연속으로 오면 안 된다.
3. 같은 글자가 연속적으로 두번 오면 안되나, ee 와 oo는 허용한다.

이 규칙은 완벽하지 않다;우리에게 친숙하거나 발음이 쉬운 단어 중에서도 품질이 낮게 평가되는 경우가 많이 있다.

입력:

입력은 여러개의 테스트 케이스로 이루어져 있다.

각 테스트 케이스는 한 줄로 이루어져 있으며, 각 줄에 테스트할 패스워드가 주어진다.

마지막 테스트 케이스는 end이며, 패스워드는 한글자 이상 20글자 이하의 문자열이다. 또한 패스워드는 대문자를 포함하지 않는다.

출력:

각 테스트 케이스를 '예제 출력'의 형태에 기반하여 품질을 평가하여라.

풀이방법:

이 문제에는 조건이 3개 있고, 각각 다음과 같이 처리하도록 한다.

1. 모음 하나를 반드시 포함하여야 한다.

vowel이라는 리스트를 선언하고, string의 chr 하나씩 보면서 모음인 경우에 vowel_check를 True로 변환해준다. 모든 string 탐색을 마친 뒤에 vowel_check를 확인하도록 한다.

2. 모음이 3개 혹은 자음이 3개 연속으로 오면 안 된다.

한 단어를 확인할 때마다. v, nv의 갯수를 업데이트 한다. 각각 vowel, non_vowel을 의미하고, 모음이 나온 경우에는 v++을 하고, nv는 0으로 만들어준다. 자음의 경우에는 반대로 수행한다. 그리고, 둘 중 하나가 3인 경우에는 answer를 False로 바꾼다.

3. 같은 글자가 연속적으로 두번 오면 안되나, ee와 oo는 허용한다.

각 chr를 stack에 담으면서 끝 값과 비교하도록 한다. 이 때 만약 같다는 조건문을 통과한 경우에는 answer를 False로 바꾸는데, ee와 oo만 따로 예외상황으로 빼도록 한다.

문제링크:

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

문제:

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

창영이는 말할 수 없는 방법을 이용해서 현우가 강산이에게 보내는 메시지를 획득했다. 이 메시지는 숫자 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

문제:

상근이는 오락실에서 바구니를 옮기는 오래된 게임을 한다. 스크린은 N칸으로 나누어져 있다. 스크린의 아래쪽에는 M칸을 차지하는 바구니가 있다. (M<N) 플레이어는 게임을 하는 중에 바구니를 왼쪽이나 오른쪽으로 이동할 수 있다. 하지만, 바구니는 스크린의 경계를 넘어가면 안 된다. 가장 처음에 바구니는 왼쪽 M칸을 차지하고 있다.

스크린의 위에서 사과 여러 개가 떨어진다. 각 사과는 N칸중 한 칸의 상단에서 떨어지기 시작하며, 스크린의 바닥에 닿을때까지 직선으로 떨어진다. 한 사과가 바닥에 닿는 즉시, 다른 사과가 떨어지기 시작한다.

바구니가 사과가 떨어지는 칸을 차지하고 있다면, 바구니는 그 사과가 바닥에 닿을 때, 사과를 담을 수 있다. 상근이는 사과를 모두 담으려고 한다. 이때, 바구니의 이동 거리의 최솟값을 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 M이 주어진다. (1 ≤ M < N ≤ 10) 둘째 줄에 떨어지는 사과의 개수 J가 주어진다. (1 ≤ J ≤ 20) 다음 J개 줄에는 사과가 떨어지는 위치가 순서대로 주어진다.

출력:

모든 사과를 담기 위해서 바구니가 이동해야 하는 거리의 최솟값을 출력한다.

풀이방법:

바구니의 너비가 있기 때문에 사과를 양 끝에 걸치게 받는 것이 가장 조금 이동하면서 사과를 받는 방법이다. 따라서 바구니의 양 끝의 index를 기억하면서 사과가 떨어지는 지점과의 차이를 더해나가도록 한다.

사과가 바구니의 오른쪽이면 바구니의 오른쪽과의 차이를 , 왼쪽이라면 바구니의 왼쪽과의 차이를 계산하면서 바구니도 같이 이동시키도록 한다.

문제링크:

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

문제:

이번 계절학기에 심리학 개론을 수강 중인 평석이는 오늘 자정까지 보고서를 제출해야 한다. 보고서 작성이 너무 지루했던 평석이는 노트북에 엎드려서 꾸벅꾸벅 졸다가 제출 마감 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

문제:

주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다.

갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고유한 번호들이 공백을 사이에 두고 주어진다. 고유한 번호는 100,000보다 작거나 같은 자연수이다.

출력:

첫째 줄에 갑옷을 만들 수 있는 개수를 출력한다.

풀이방법:

 우선 N개의 재료들을 오름차순으로 정렬하고, 첫 값(start)과 마지막 값(end)에 포인터를 할당한다. 그리고 해당 위치에 있는 값들을 더하면서 M이 되는지 확인하고, 만약 M보다 크다면 end의 값을 줄이고, M보다 작거나 같다면 start를 하나 늘리도록 한다. 이 과정을 start와 end가 같아질 때까지 반복하도록 한다.(같은 순간에 종료)

문제링크:

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

문제:

임한수와 임문빈은 서로 사랑하는 사이이다.

임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다.

임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다.

임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오.

입력:

첫째 줄에 임한수의 영어 이름이 있다. 알파벳 대문자로만 된 최대 50글자이다.

출력:

첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hansoo"를 출력한다. 정답이 여러 개일 경우에는 사전순으로 앞서는 것을 출력한다.

풀이방법:

 우선 각 알파벳의 갯수를 count를 한다. 이 때, 홀수 개인 알파벳이 한 개만 있거나 없을 경우에만 팰린드롬을 만들 수 있다. 홀수 개인 알파벳이 하나만 있을때만, 가운데에 배치하여 팰린드롬을 만들 수 있기 때문이다. 따라서 이 조건을 사용해서 우선적으로 필터링해주도록 한다.

 만들 수 있는 경우에는 알파벳을 사전순으로 정렬한 뒤 만들어나가기 시작한다. 각 알파벳의 갯수 M/2개를 문자열에 이어붙이고, 모든 문자열을 순회한 경우에는 다시 역순으로 M/2개를 문자열에 이어 붙이도록 한다. 이 때, 홀수 개인 알파벳이 있었다면, 역순으로 진행하기 전에 먼저 붙이도록 한다.

문제링크:

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

문제:

선영이는 이번 학기에 오스트레일리아로 교환 학생을 가게 되었다.

호주에 도착하고 처음 며칠은 한국 생각을 잊으면서 즐겁게 지냈다. 몇 주가 지나니 한국이 그리워지기 시작했다. 

선영이는 한국에 두고온 서버에 접속해서 디렉토리 안에 들어있는 파일 이름을 보면서 그리움을 잊기로 했다. 매일 밤, 파일 이름을 보면서 파일 하나하나에 얽힌 사연을 기억하면서 한국을 생각하고 있었다.

어느 날이었다. 한국에 있는 서버가 망가졌고, 그 결과 특정 패턴과 일치하는 파일 이름을 적절히 출력하지 못하는 버그가 생겼다.

패턴은 알파벳 소문자 여러 개와 별표(*) 하나로 이루어진 문자열이다.

파일 이름이 패턴에 일치하려면, 패턴에 있는 별표를 알파벳 소문자로 이루어진 임의의 문자열로 변환해 파일 이름과 같게 만들 수 있어야 한다. 별표는 빈 문자열로 바꿀 수도 있다. 예를 들어, "abcd", "ad", "anestonestod"는 모두 패턴 "a*d"와 일치한다. 하지만, "bcd"는 일치하지 않는다.

패턴과 파일 이름이 모두 주어졌을 때, 각각의 파일 이름이 패턴과 일치하는지 아닌지를 구하는 프로그램을 작성하시오.

입력:

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

둘째 줄에는 패턴이 주어진다. 패턴은 알파벳 소문자와 별표(아스키값 42) 한 개로 이루어져 있다. 문자열의 길이는 100을 넘지 않으며, 별표는 문자열의 시작과 끝에 있지 않다.

다음 N개 줄에는 파일 이름이 주어진다. 파일 이름은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다.

출력:

총 N개의 줄에 걸쳐서, 입력으로 주어진 i번째 파일 이름이 패턴과 일치하면 "DA", 일치하지 않으면 "NE"를 출력한다.

참고로, "DA"는 크로아티어어로 "YES"를, "NE"는 "NO"를 의미한다.

풀이방법:

 패턴과 일치하는 문자열을 찾기 위해 사용할 수 있는 라이브러리로 정규표현식이 있다. 따라서. 주어진 패턴을 정규표현식 형태로 변경하여 출력을 하도록 한다.

 문제에서 주어진 *와 같은 역할을 하는 것은 정규표현식에서 . 에 해당한다. 따라서 replace를 사용하여 이를 변경해주도록 한다. 그리고 패턴이 변수에 할당된 상태로 사용해야 하기 때문에 formatting을 사용하여 string 형태로 사용할 수 있도록 한다. 이 패턴과 추가적으로 ^(맨 앞임을 의미), $(맨 끝임을 의미)를 사용하여 패턴을 마무리하도록 한다. 들어 오는 입력대로 패턴과 일치하는지 확인하여 알맞은 출력을 하도록 한다.

문제링크:

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

문제:

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 

입력:

첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다.

출력:

첫째 줄에 주어진 추들로 측정할 수 없는 양의 정수 무게 중 최솟값을 출력한다.

풀이방법:

 이 문제를 해결하기 위해서 다음과 같은 하나의 가정을 하도록 한다. Sn을 n까지의 저울추를 더한 값이라고 하고, An을 저울추라고 하자. 그럼 Sn+2 <= A(n+1)가 될 때, Sn+1은 측정할 수 없는 최솟값이 된다. 이러한 가정이 가능한 이유는 Sn이 Sn까지 무게를 측정할 수 있다는 의미를 가지기 때문이다.

 따라서 오름차순으로 정렬한 뒤에 저울추를 하나씩 올리면서 가정에 도달할 때까지 반복하도록 한다.

문제링크:

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