빠에야는 개발중

배열을 오름차순으로 정렬하고 k만큼의 간격으로 최대, 최소값 쌍을 만들어 순회한다. 가장 작은 값을 골라낸다. 기존 배열을 변경하지 않고 그냥 순회를 해서 회전까지 생각을 한다면 부분 배열 골라내기 + 부분 배열에서 최소값 찾기를 해야하기 때문에 오랜 시간이 걸릴 것이다. 게다가 중복 연산도 있을 수 있다. 하지만 정렬을 하면 O(nlogn) 시간에 끝날 수 있기 때문에 빠르다.

생각했던 것 내림차순으로 각 요소를 정렬해서 사람 수만큼 하나씩 쭉 빼주다가 마지막 사람에게 전부 몰아주는 방법을 생각했다. 하지만 예제를 보면서 틀렸다는 걸 알았다. 맨 마지막에 남은 값들을 다 몰아주면 결과값이 선형적으로 증가할 것이기 때문이다. 그래서 수정한 방법은 꽃의 개수를 균일하게 가져갈 수 있도록 분배하는 것이었다. 꽃의 가격에 영향을 주는 것은 이전, 이후의 꽃의 가격이 아닌 "해당 꽃을 사는 사람의 이전 구매 개수"이다. 따라서 개수를 잘 조절하면 최소값을 얻을 수 있다. 진행 해시맵에 사람 수만큼의 원소를 넣고 내림차순 정렬한 꽃 배열을 순회하면서 순차적으로 해시맵의 구매 개수를 늘려준다. 개수를 매번 더해주면서 꽃의 가격도 함께 계산해준다. 여담 역시나 정렬을 기본으로 생각하니 생각하..

생각했던 것 important contest와 not important contest를 구분해서 저장해주면 연산하기가 훨씬 쉽다. 한꺼번에 넣어주면 다중 조건 정렬을 해줘야하기 때문이다. 진행 luck을 key라고 하고, 중요성을 value라고 두었을 때 value가 1인 것들을 따로 담아서 내림차순 한 다음, 받은 개수만큼은 앞에서부터 순차적으로 남겨두고 나머지 뒷부분은 전부 같은 절대값의 음수로 바꿔준다. 그리고 모든 리스트들의 값들을 더해주면 결과값이 나온다. 여담 그리디 알고리즘은 대부분 정렬로부터 시작되는 것 같다. 정렬을 내가 직접 구현하지 않아도 돼서 편하게 문제를 풀 수 있어 다행이다.

생각했던 것 절대값들 중 최소값을 찾는 문제로, 모든 경우의 수를 비교하여 최소값을 찾아내면 된다. 진행 ... 라고 하였으나 그러면 0(n^2) 시간에 끝날 것이기 때문에 비효율적이다. 경우의 수를 줄이기 위해서 생각한 것은 "정렬"이다. 예를 들어 오름차순으로 정렬했을때 [A, B, C] 배열이 도출되었다면 (A, B)의 차이는 (A, C)의 차이보다 작을 수 밖에 없다. 그러므로 모든 경우의 수를 따지지 않고, 바로 옆의 수와 비교하기만 하면 된다. 그러면 정렬하는 시간 O(nlogn) + 탐색시간 O(n)으로 O(nlogn) 시간 안에 끝낼 수 있다. 여담 각 수가 양수, 음수 여부에 따라 절대값 계산이 다를거라고 잠깐 착각했었다.. 그냥 뒷수에서 앞 수를 빼면 된다.

생각했던 것 척봐도 LCS(Longest Common Sequence, Substring이 아니다.) 문제임을 알 수 있었다. 부분 수열이 무엇인지는 필요없고 개수만 파악하면 돼서 오히려 더 쉬운 문제였다. 진행 일반적인 LCS 풀이와 같이 했다. 0부터 시작하는 테이블을 만들어 두 문자열을 비교해가면서 두 문자가 같은 경우는 직전 문자열(테이블의 대각선 1칸 전의 값)까지의 개수 + 1을 해주고, 다른 경우에는 각 문자열의 직전 문자열(테이블의 아래, 위로 1칸 전의 값 중 최대값)까지의 개수를 가져오면 된다. 예컨대, 두 문자가 같은 경우 ABCD와 ACCB에서 세번째 C가 같기 때문에 AB, AC의 최장 수열 개수인 1(A만 공통)에서 1을 더해줘 2가 된다. 두문자가 다른 경우 ABCD와 ACCB..

문제를 잘 파악하자! 생각한 것 왜 저렇게 크게 써놨냐면 문제를 제대로 파악을 못해서 잘못된 코드를 짰기 때문이다. 결국 처음에는 그냥 일반적인 팰린드롬을 구현했다(효율적인지는 둘째치고...). 그러다 테스트 케이스가 실패하는걸 보고 문제를 다시 보니 "한 문자 빼고 전부 다 같은 경우"가 있었고 일반적인 팰린드롬은 다른 것들도 카운팅 해주기 때문에 실패한다는 걸 알았다. 또 삽질 그런데 나는 정말 생각없이 "단 하나"임을 놓치고 가운데에 오는 문자가 하나인 것과(홀수 길이) 두개인 것(짝수 길이)을 따로 체크를 해주도록 코드를 작성했다... 그러니 틀릴 수 밖에. 게다가 쓸데없는 연산이 생겼기 때문에 타임아웃에 걸리는건 덤... 진짜 해결책 우선 먼저번에 구현한 "잘못된 팰린드롬"과 같은 방식으로 구현..

생각한 것 YES의 조건이 "단 하나의 알파벳의 개수가 다른 알파벳보다 1개 많고, 다른 알파벳들의 개수를 모두 같을 것"이라고 생각했고, a-z를 나타내는 배열을 만들어 순차적으로 유일성을 체크해주는 로직을 생각했다. 그런데 예를 들어 aabbbcdd 라는 문자열이 있다면 배열로 나타냈을때 [2, 1, 3, 2...]로 표현할 수 있는데, 불가능을 구별하기 위해 2를 기준으로 잡고 순차적으로 체크했을때 1은 넘어가고 3은 안되고... 그런 많은 조건들이 필요해졌기 때문에 이 방법은 아니라고 생각했다. 다른 생각 앞에서 O(n) 시간 안에 할 수 있을거라는 생각에 미련을 버리지 못했었는데.. 정렬을 하면 정말 간단하게 체크할 수 있다. 빈도수 별로 정렬을 하고 각 요소들의 개수와 크기를 비교하면 된다. ..

생각한 것 단순하게 생각해서 입력받은 문자열들을 글자 단위 쪼개 리스트로 만들어 비교해서 공통되는 문자를 카운팅 해서 기존 문자열에서 빼는 로직을 생각했었다. 문자열 a를 순회하면서 문자열 b에 포함된 문자열이 있으면 빼주는 식인데 문제가 있었다. 첫번째는 "어떻게 한 글자씩 뺄 것인가?"이고 두번째는 "String에서 한글자씩 제거할 때 드는 오버헤드의 크기"였다. 보통 String.replace()로 모든 글자를 치환하는 방식을 사용하는데 이번 문제에서는 한 글자씩 제거해나가야 했다. 그리고 한 글자씩 제거하기 위해 루프를 돈다면 O(m*n)의 시간복잡도를 가지게 되므로 비효율적이다. 개선 아나그램은 결국 공통된 문자를 같은 개수만큼 가지고 있으면 된다. 그러므로 문자와 그 개수를 기억하고 선형 시간..

생각한 것 특정 키와 그 키의 빈도수를 표현하기 위해서는 역시 map 구조가 잘 어울린다고 생각했고 형태의 hashmap을 만들어서 입력값을 받아 넣어주었다. 그런데 값이 잘 들어가지 않거나 타임 아웃이 나서 실패했다. 개선 결국 필요한 출력값은 어떤 키가 됐던 간에 빈도수만 맞으면 결정된다. 즉 빈도수만 생각하는 자료구조를 하나 더 만들어주면 된다고 생각했다. 그래서 를 가지는 hashmap을 하나 더 만들어서 값을 넣고 뺄때 함께 계산해줬다. 결말 타임아웃은 여전히 난다. 아직도 완전히 풀고 있지 못한 문제다... 입력 개수가 10만개가 넘어가니 타임아웃이 난다. 아무래도 map.containsKey() 메소드가 순차적으로 값을 찾다보니 그런 것 같다. 그렇다면 특정 key나 value를 한번에 찾으..

생각했던 것 문제가 생각보다 쉽게 느껴졌기 때문에 직관적으로 구현해보았다. 주어지는 각 입력에 맞춰 a부터 b까지 k만큼 더해주었고, 마지막에 정렬을 해서 가장 큰 값을 가져오면 된다. 중간중간 미스가 있었지만 답 자체가 틀리지는 않았다. 문제점 문제는 타임아웃이었다. 주어진 범위에 해당하는 모든 원소에 접근해야하기 때문에 입력값이 100000개가 넘어가면 아무래도 오래걸렸다. 자바가 아니라 C, C++이라면 통과할 수도 있겠다고 생각했지만 꼼수 부리지 말고 알고리즘을 개선해보자. 해결 결과적으로는 스스로 답을 찾아내지는 못했다. 오름차순으로 절반의 값만 계산한다던지 하는 생각이 들긴 했지만 정답은 아닌것 같았다. 좀 더 효율적인 자료구조 활용이 필요해보였다. bfs, dfs 등의 기법이 필요해보이진 않..