원

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

다양한 문자열 문제를 해결하기 위해서는 접미사 배열(suffix array) 자료구조를 이해해야한다. 접미사 배열은 어떤 문자열 S의 모든 접미사를 사전순으로 정렬해 둔 것이다. 이 말 그래도 모든 접미사들을 문자열 배열에 저장하면 문자열 길이의 제곱에 비례하는 메모리가 필요하기 때문에, 대개 접미사 배열은 각 접미사의 시작 위치를 담는 정수 배열로 구현된다. 예를 들면 아래 표는 문자열 "alohomora"의 접미사 배열 A[]와 각 위치에서 시작하는 접미사들을 보여준다. i A[i] S[A[i] ..] 0 8 a 1 0 a l o h o m o r a 2 3 h o m o r a 3 1 l o h o m o r a 4 5 m o r a 5 2 o h o m o r a 6 4 o m o r a 7 6 ..

https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net 문제 Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 끝에 새로운 에디터를 만들게 되었고, 그 에디터의 이름은 Cubeditor이다. 텍스트 에디터는 찾기 기능을 지원한다. 대부분의 에..

https://www.acmicpc.net/problem/1283 1283번: 단축키 지정 첫째 줄에 옵션의 개수 N(1 ≤ N ≤ 30)이 주어진다. 둘째 줄부터 N+1번째 줄까지 각 줄에 옵션을 나타내는 문자열이 입력되는데 하나의 옵션은 5개 이하의 단어로 표현되며, 각 단어 역시 10개 이하 www.acmicpc.net 문제 한글 프로그램의 메뉴에는 총 N개의 옵션이 있다. 각 옵션들은 한 개 또는 여러 개의 단어로 옵션의 기능을 설명하여 놓았다. 그리고 우리는 위에서부터 차례대로 각 옵션에 단축키를 의미하는 대표 알파벳을 지정하기로 하였다. 단축키를 지정하는 법은 아래의 순서를 따른다. 먼저 하나의 옵션에 대해 왼쪽에서부터 오른쪽 순서로 단어의 첫 글자가 이미 단축키로 지정되었는지 살펴본다. 만약..

https://www.acmicpc.net/problem/11365 11365번: !밀비 급일 당신은 길을 가다가 이상한 쪽지를 발견했다. 그 쪽지에는 암호가 적혀 있었는데, 똑똑한 당신은 암호가 뒤집으면 해독된다는 것을 발견했다. 이 암호를 해독하는 프로그램을 작성하시오. www.acmicpc.net END 입력 전까지 무한 반복문 내에서 입력한 문자열을 반대로 뒤집어서 출력해주면 되는 문제이다. 파이썬에서 제공하는 문자열 슬라이싱을 이용하여 쉽게 해결할 수 있는 문제이다. import sys while True: sentence = input() if sentence == "END": break answer = sentence[::-1] print(answer)

https://www.acmicpc.net/problem/3029 3029번: 경고 첫째 줄에 현재 시간이 hh:mm:ss 형식으로 주어진다. (시, 분, 초) hh는 0보다 크거나 같고, 23보다 작거나 같으며, 분과 초는 0보다 크거나 같고, 59보다 작거나 같다. 둘째 줄에는 나트륨을 던질 시간 www.acmicpc.net 문자열 문제이다. 시간을 계산해서 시간 차를 구하는 문제이다. 나는 초단위로 모든 시간을 구해주었다. 1시간은 3600초, 1분은 60초, 1초 이렇게 계산해주었다. 그리고 하나 주의해야할 점이 2개의 시간이 같은 경우 0시간 0분 0초 차이가 아닌 하루 차이가 난다는 것을 인지하지 못해서 한 번 틀렸었다. import sys first = input().split(':') se..

https://www.acmicpc.net/problem/2902 2902번: KMP는 왜 KMP일까? 입력은 한 줄로 이루어져 있고, 최대 100글자의 영어 알파벳 대문자, 소문자, 그리고 하이픈 ('-', 아스키코드 45)로만 이루어져 있다. 첫 번째 글자는 항상 대문자이다. 그리고, 하이픈 뒤에는 반드 www.acmicpc.net 이 문제는 파이썬에서 제공하는 split()함수를 이용하면 쉽게 해결이 가능하다. split('-')문을 통해 -을 기준으로 나눠준 후 리스트로 변환하는 것이다. 그럼 각 리스트 안 원소의 첫번째 문자들만 합쳐주어 문자열로 만들어주면 정답이 된다. import sys from collections import * arr = sys.stdin.readline().split(..

https://www.acmicpc.net/problem/1302 1302번: 베스트셀러 첫째 줄에 오늘 하루 동안 팔린 책의 개수 N이 주어진다. 이 값은 1,000보다 작거나 같은 자연수이다. 둘째부터 N개의 줄에 책의 제목이 입력으로 들어온다. 책의 제목의 길이는 50보다 작거나 같고 www.acmicpc.net 파이썬에서 조건에 따른 정렬을 할 때 lambda를 사용하는데 그것과 관련된 문제이다. 가장 높은 우선순위를 팔린 책의 수로 두고, 팔린 책의 수가 같다면 사전순으로 정렬하는 문제이다. 나는 딕셔너리를 이용해 "책 제목 : 팔린 책의 수"로 설정하고, 모든 입력이 끝나면 딕셔너리를 리스트로 형변환 시켜주었다. 그리고 리스트를 lambda를 이용해 우선순위에 따른 정렬을 해주었다. impor..

https://www.acmicpc.net/problem/4358 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 이번 문제는 문자열 문자라 파이썬으로 풀어보았다. 요즘 학교 수업 시간에 파이썬을 배우고 있는데 확실히 문자열 관련 문제는 C++보다는 파이썬이 훨씬 풀기에 쉬운 것 같다. 딕셔너리를 이용해서 해결하였고, 딕셔너리도 collections에서 defaultdict()으로 추가까지 할 수 있게 해주었다. 그리고 입력이 끝나면 key값을 기준으로 정렬해주고 출력만 해주면 된다.! import..

https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 문제 김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. 이름은 띄어쓰기 없이 영어 소문자로만 이루어지며, 그..