본문 바로가기
728x90

문자열

 (12)
[백준] 9251번 LCS [Python] - 다이나믹, 문자열 LCS$($Longest Common Subsequence, 최장 공통 부분 수열$)$문제 최장 공통 부분 수열 더보기 문제 LCS$($Longest Common Subsequence, 최장 공통 부분 수열$)$문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. 입력 첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 출력 첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다. https://www.acmicpc.net/problem/9251 한 단어의 철자를 순서대로 다른 단어의 철자와 비교하면서 같은 철자가..
[프로그래머스] Lv.1 가장 가까운 같은 글자 [Python] - 문자열 주어진 문자열의 각 글자가 처음 나오면 -1, 이미 나온 글자는 바로 앞의 글자와의 거리를 리스트에 담아서 반환하는 문제 더보기 문제 설명 문자열 s가 주어졌을 때, s의 각 위치마다 자신보다 앞에 나왔으면서, 자신과 가장 가까운 곳에 있는 같은 글자가 어디 있는지 알고 싶습니다. 예를 들어, s="banana"라고 할 때, 각 글자들을 왼쪽부터 오른쪽으로 읽어 나가면서 다음과 같이 진행할 수 있습니다. b는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다. a는 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다. n은 처음 나왔기 때문에 자신의 앞에 같은 글자가 없습니다. 이는 -1로 표현합니다. a는 자신보다 두 칸 앞에 a가 있습니다. 이는..
[프로그래머스] Lv.1 문자열 내 마음대로 정렬하기 [Python] - 문자열 문자열로 구성된 리스트와 정수 n이 주어질 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬, n 번째 글자가 같은 경우 사전순 정렬하는 문제 더보기 문제 설명 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱스 1의 문자 "u", "e", "a"로 strings를 정렬합니다. 제한 조건 strings는 길이 1 이상, 50이하인 배열입니다. strings의 원소는 소문자 알파벳으로 이루어져 있습니다. strings의 원소는 길이 1 이상, 100이하인 문자열입니다. 모든 strings의 원소의 길이는 n보다 ..
[백준] 6064번 IOIOI [Python] - 문자열 N+1 개의 I 사이에 N개의 O가 들어있는 문자열 $P_N$ : IOIOIOIO...IOI에 대해서 N이 주어질 때 I와 O로만 이루어진 길이가 M인 문자열에서 $P_N$이 몇 번 포함되는지 세는 문제 IOIOIOI에는 IOI가 3번 포함됨. 더보기 문제 N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 $P_N$이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI $($O가 N개$)$ I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다. 출력 S에 $P_N$이 몇 군..
[백준] 1541번 잃어버린 괄호 [Python] - 그리디 양수, +, -, 괄호가 주어진 수식에서 괄호만 지운 문자열이 주어질 때, 괄호를 적절히 쳐서 최소값을 구하는 문제 양수는 0부터 시작하는 문자열로 주어지기도 합니다. 더보기 문제 세준이는 양수와 +, -, 그리고 괄호를 가지고 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다. 그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다. 괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어..
[프로그래머스] Lv.1 문자열 나누기 [Python] - 문자열 규칙에 따라 문자열을 나누고, 분해된 문자열의 개수를 구하는 문제 규칙 - 첫 글자부터 같은 글자와 다른 글자 수를 세어나가서, 두 수가 같아지만 분해 남은 문자열부터 똑같은 방식으로 진행 더이상 남은 문자열이 없고, 현재 진행중인 게 있다면 그 문자열 덩어리로 분해 더보기 문제 설명 문자열 s가 입력되었을 때 다음 규칙을 따라서 이 문자열을 여러 문자열로 분해하려고 합니다. 먼저 첫 글자를 읽습니다. 이 글자를 x라고 합시다. 이제 이 문자열을 왼쪽에서 오른쪽으로 읽어나가면서, x와 x가 아닌 다른 글자들이 나온 횟수를 각각 셉니다. 처음으로 두 횟수가 같아지는 순간 멈추고, 지금까지 읽은 문자열을 분리합니다. s에서 분리한 문자열을 빼고 남은 부분에 대해서 이 과정을 반복합니다. 남은 부분이 없다면 ..
[백준] 17176번 암호해독기 [Python] - 아스키코드 0은 띄어쓰기, 1 - 26 범위 안의 수는 A ~ Z, 27 - 52 범위 안의 수는 a ~ z로 해석 평문을 암호화해서 주어진 암호문을 만들 수 있는지 확인하는 문제 더보기 문제 방금 도착한 암호문을 해독했는데, 해독에 오류가 없는지 확인해보려 한다. 해독한 문장이 암호문을 해석한 결과로 나올 수 없다면, 그 해독은 잘못된 것이다. 암호문은 0 이상 52 이하의 정수로 이루어져 있다. 0은 띄어쓰기, 1 - 26 범위 안의 수는 A ~ Z, 27 - 52 범위 안의 수는 a ~ z로 해석된다. 암호문은 띄어쓰기를 포함한 모든 철자를 이와 같이 정수로 치환한 후 순서를 무작위로 뒤섞어서 만들어졌다. 입력 첫 번째 줄에는 주어질 수열의 길이 N이 주어진다. $(1 ≤ N ≤ 100,000)$ 두 번째 줄..
[백준] 13413번 오셀로 재배치 [Python] 오셀로 말$($2개$)$의 위치를 바꾸거나, 말 1개를 뒤집기 위 두 가지 작업만으로 초기 상태 -> 목표 상태 까지의 최소 작업 횟수 구하는 문제 각 상태는 W와 B가 이어진 문자열 형태로 주어짐 더보기 문제 로봇을 좋아하는 세희는 로봇동아리에서 카메라와 센서, 라즈베리 파이, 집게발을 이용해 로봇을 완성하였다. 이 로봇을 통해서 오셀로 재배치라는 작업을 하려고 한다. 오셀로 말은 앞면이 검정, 뒷면이 흰색으로 된 말이다. 세희의 목표는 로봇을 이용하여 처음 배치된 오셀로 말을 주어진 형태로 바꾸는 일을 하는 것이다. 아래의 예시를 참고하자. 초기 상태 목표 상태 ○●●○○ ○●○●○ 세희는 로봇을 이용해 2가지 작업 중 하나를 골라 진행할 수 있다. 배치된 말 중 임의의 2개의 말을 골라 서로의 위치..
[백준] 1213번 팰린드롬 만들기 [Python] 팰린드롬$($palindrome$)$: 거꾸로 읽어도 제대로 읽는 것과 같은 문장이나 낱말, 숫자, 문자열 등 주어진 문자열로 팰린드롬 만들기 더보기 문제 임한수와 임문빈은 서로 사랑하는 사이이다. 임한수는 세상에서 팰린드롬인 문자열을 너무 좋아하기 때문에, 둘의 백일을 기념해서 임문빈은 팰린드롬을 선물해주려고 한다. 임문빈은 임한수의 영어 이름으로 팰린드롬을 만들려고 하는데, 임한수의 영어 이름의 알파벳 순서를 적절히 바꿔서 팰린드롬을 만들려고 한다. 임문빈을 도와 임한수의 영어 이름을 팰린드롬으로 바꾸는 프로그램을 작성하시오. 입력 첫째 줄에 임한수의 영어 이름이 있다. 알파벳 대문자로만 된 최대 50글자이다. 출력 첫째 줄에 문제의 정답을 출력한다. 만약 불가능할 때는 "I'm Sorry Hanso..
[백준] 1343번 폴리오미노 [Python] XXXX >>> AAAA XX > BB 위 방법으로 덮어쓴 문자열 출력하는 문제 더보기 문제 민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB 이제 '.'와 'X'로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 'X'를 모두 폴리오미노로 덮으려고 한다. 이때, '.'는 폴리오미노로 덮으면 안 된다. 폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 50이다. 출력 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. 1343번: 폴리오미노 (acmicpc.net) a=".".join(["AAAA"*(len(x)//4)+"B"*(len(x)%4) if len(x)%..
[백준] 15904번 UCPC는 무엇의 약자일까? [Python] 주어진 문자열을 줄임말로 변형했을 때, 원하는 문자열이 될 수 있는지 확인하는 문제 더보기 문제 UCPC는 '전국 대학생 프로그래밍 대회 동아리 연합 여름 대회'의 줄임말로 알려져있다. 하지만 이 줄임말이 정확히 어떻게 구성되었는지는 아무도 모른다. UCPC 2018을 준비하던 ntopia는 여러 사람들에게 UCPC가 정확히 무엇의 줄임말인지 물어보았지만, 아무도 정확한 답을 제시해주지 못했다. ntopia가 들은 몇 가지 답을 아래에 적어보았다. Union of Computer Programming Contest club contest Union of Computer Programming contest Club contest Union of Computer Programming contest club ..
[백준] 1543번 문서 검색 [Python] 주어진 문자열에 그 다음 주어진 문자열이 중복 없이 몇 번 들어 있는지 구하는 문제 더보기 문제 세준이는 영어로만 이루어진 어떤 문서를 검색하는 함수를 만들려고 한다. 이 함수는 어떤 단어가 총 몇 번 등장하는지 세려고 한다. 그러나, 세준이의 함수는 중복되어 세는 것은 빼고 세야 한다. 예를 들어, 문서가 abababa이고, 그리고 찾으려는 단어가 ababa라면, 세준이의 이 함수는 이 단어를 0번부터 찾을 수 있고, 2번부터도 찾을 수 있다. 그러나 동시에 셀 수는 없다. 세준이는 문서와 검색하려는 단어가 주어졌을 때, 그 단어가 최대 몇 번 중복되지 않게 등장하는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 문서가 주어진다. 문서의 길이는 최대 2500이다. 둘째 줄에 검색하고 싶은 단어가 주어..

티스토리툴바