알고리즘 문제/Programmerse42 [programmers][찾아라 프로그래밍 마에스터] 사칙연산 문제 : programmers.co.kr/learn/courses/30/lessons/1843 숫자와 연산 기호(+, -)로 이루어진 수식이 주어질 때 괄호를 추가해 그 수식의 계산 결과는 여러가지가 나올 수 있다. 이 때 나올 수 있는 계산 결과 중 최대값을 구하여라. DP로 해결했다. 수식이 문자열 arr로 주어지고 부분문자열 arr[s~e]의 최대값, 최소값을 저장하는 배열을 만든다. 최대값 배열 dMax[s][e] = arr[s~e] 수식의 계산 결과 중 최대값. 최소값 배열 dMin[s][e] = arr[s~e] 수식의 계산 결과 중 최소값. 우리가 알고자 하는 값은 dMax[0][n-1] 인데 최대값을 구하기 위해서는 최소값도 알아야 하기 때문에 dMin 배열도 필요하다. 만약 i 인덱스가 연.. 2020. 9. 13. [programmers][2020카카오공채] 가사 검색 문제 : https://programmers.co.kr/learn/courses/30/lessons/60060 검색 키워드는 와일드카드 문자인 '?'가 하나 이상 포함돼 있으며, '?'는 각 검색 키워드의 접두사 아니면 접미사 중 하나로만 주어집니다. 단어들이 주어지고 접미사, 접두사를 제공하며 단어들의 개수를 묻는다. -> 트라이! 접두사에 대한 질문은 문자열의 앞에서부터 탐색하니까 일반적으로 풀 수 있는데 접미사는 뒤에서부터 탐색해야 하므로 문자들을 역순으로 만든 후 트라이를 하나 더 만든다. (접미사, 접두사를 위해 각자 1개씩 2개의 트라이 생성) 검색 키워드가 문자로 시작하는 경우(?로 끝나는 경우) 접두사를 위해 만든 트라이를 이용하여 탐색하고, 검색 키워드가 ? 으로 시작하는 경우 해당 키워.. 2020. 5. 12. [programmers][2020카카오공채] 자물쇠와 열쇠 문제 : https://programmers.co.kr/learn/courses/30/lessons/60059# N, M 범위가 20으로 널널하기 때문에 구현, 시뮬레이션으로 풀었다. 일단 키를 회전한 모습을 배열에 저장한다. for (int i = 0; i 2020. 5. 10. [programmers][2020카카오공채] 괄호 변환 문제 : https://programmers.co.kr/learn/courses/30/lessons/60058 문자열 p를 입력으로 받은 경우 먼저 p에서 문자열 u, v 분리한다. 분리하는 방법은 cnt 변수를 하나두고 p를 앞에서부터 탐색하면서 여는괄호가 나오면 cnt+1, 닫는괄호가 나오면 cnt-1해준다. 탐색하면서 탐색의 시작지점(p[0])을 제외하고 cnt가 0이 되는 지점이 나오면 이를 기준으로 p를 u, v로 분리한다. 문자열 p는 '(', ')' 개수가 같은 균형잡힌 괄호 문자열이라는 조건이 있기 때문에 cnt가 0이 되는 지점은 반드시 존재한다.ex) p = "(())()" 인 경우 인덱스가 3일때 cnt를 계산하면 cnt가 0이되고 이를 기준으로 "(())" "()"문자열로 분리한다... 2019. 11. 27. [programmers][2020카카오공채] 문자열 압축 문제 : https://programmers.co.kr/learn/courses/30/lessons/60057 aabbccc 가 있을 때, 탐색하는 압축 길이는 길이의 반 이하인 1, 2, 3만 살펴보면 된다. 길이의 반(7/2 =3)보다 큰 수인 4는 반드시 중복되는 수가 하나도 없을 것이기 때문이다. (aabb가 중복될 가능성은 0. 왜냐하면 남은 문자의 길이가 4보다 작기 때문이다.) 압축하는 길이를 compression 이라고 했을 때, #1 문자열 s를 앞에서부터 compression 개수만큼 잘라가며 이전 문자열과 비교한다. 동시에 압축 문자열의 길이(len)를 갱신해나간다. #2 만약 이전 문자열과 같다면 반복되는 문자열 개수(cnt)를 +1 해준다. 이 때, cnt의 초기 값은 0이 아닌 .. 2019. 11. 26. [programmers] 베스트앨범 문제 : https://programmers.co.kr/learn/courses/30/lessons/42579# 수록 기준 1. 속한 노래가 많이 재생된 장르를 먼저 수록. 2. 장르 내에서 많이 재생된 노래를 먼저 수록. 3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록 map를 이용했다. 사용한 map은 총 3가지. 1. key: 장르 / value : 재생수, 고유번호를 원소로 가지는 배열 => songMap 2. key: 장르 / value : 해당장르의 총 재생수 => cntMap 3. key: 해당장르의 총 재생수 / value: 장르 [cntMap의 key, value를 바꾼 map] => rcntMap 1번 songMap은 수록 기준 2, 3을 만족하기 .. 2019. 5. 7. 이전 1 ··· 4 5 6 7 다음