문자열
-
BOJ) 문자열알고리즘/백준 2020. 7. 21. 15:29
문자열 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 � www.acmicpc.net 풀이 문자열 두개가 주어질 때, 오른쪽 문자열의 길이는 항상 왼쪽보다 크다. 왼쪽 문자열의 맨 앞이나 맨 뒤에 a~z 문자 하나를 적절하게 배치했을 때, 왼쪽과 오른쪽의 문자열의 인덱스가 다른 수의 최소값을 찾는 문제다. 문제의 조건에 최대 길이가 50이라고 주어졌지만, 이를 먼저 확인하지 않고 brute force라 dfs로 그냥 모든 경우의 수를 조합했다. 하지만, 메모리 초과가 떠서 위의 조건을 추가적으로 ..
-
BOJ) 잃어버린 괄호알고리즘/백준 2020. 7. 21. 15:07
잃어버린 괄호 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 풀이 양수와 +-로만 이루어졌고 최대 길이가 50인 수식이 있다. 이 수식에 적절하게 괄호를 씌워서 최소값을 구하는 문제다. 그렇다면, 가장 중요한 것은 -가 최대가 되게 해야한다. -로 먼저 split을 해주고, - 뒤에 있는 모든 +를 더해서 -를 씌워주면 최소값이 나올 것이다. 이 때, -를 기준으로 split을 해줬기 때문에, 배열의 첫번째 index는 -가 없다는 점을 유의해야한다. 그래서 idx ==0인 경우에는 -를 씌워주지 않고..