모항이코딩한다

풀이방법 및 문제점 2022.04.06 주어진 예제에 대하여 올바른 답을 출력하는 코드(코드 (1))는 쉽게 짤 수 있었다. 그러나 제출을 하면 틀렸다는 결과가 나왔다. 예외의 경우를 고려하지 못한 것이다. 아직도 수면패턴이 들쑥날쑥해서(빨리 고쳐야 한다...) 머리가 멍했기 때문에 내 손으로 반례를 찾기가 너무 귀찮았다. 그래서 그냥 즉시 질문 게시판으로 달려갔다. 나와 비슷한 수많은 사람들의 흔적이 있었고, 반례 하나를 금방 찾을 수 있었다. 첫 반례를 찾은 게시글 링크 일단 위 게시글에 있던 1 1 20 20 이 테스트케이스를 넣어보았더니 '120'호가 당연히 정답인데 '021'이라는 터무니없는 결과가 나왔다. 그래서 나는 내가 층이 하나 뿐인 경우를 고려하지 못하여 틀렸다고 생각했다. 층이 하나 ..

풀이방법 및 문제점 2022.03.27 번호를 입력받았다면 포켓몬 이름을 출력하고, 포켓몬 이름을 출력받았다면 번호를 출력해야 한다. 두 가지 기준으로 빠르게 자료를 찾아와야 하는 문제이다. 결론부터 말하자면 HashMap 하나와 String[] 하나를 사용하면 된다. 이를 알아내기까지 두 번의 시행착오를 거쳤다. 먼저, 한 개의 HashMap만 사용해보았다. 시간초과가 발생한다. Key를 이용해 Value를 찾는 것은 빠르게 해낼 수 있지만 Value를 이용해 Key를 찾고자 할 경우엔 반복문을 사용해야 하기 때문이다. 시간복잡도가 제곱으로 불어난다. 그래서 다음으로는, 두 개의 HashMap을 사용해보았다. HashMap HashMap 동일한 데이터셋을 Key와 Value의 순서만 바꾸어 저장한 두 ..

풀이방법 및 문제점 2022.03.21 주어진 수열을 오름차순 정렬한 뒤, 정렬된 주어진 수열에 포함된 가장 긴 연속하는 수열을 찾아서, 그 수열의 길이가 5 이상이라면 0을 출력하고, 5 미만이라면 5에서 해당 수열의 길이를 뺀 값을 출력하였다. 그러나, 이렇게 하면 1 2 3 위와 같은 연속되는 수열이 있을 때에는 2를 잘 출력하지만 1 3 5 위와 같은 경우를 캐치하지 못한다. 2, 4를 넣으면 연속되는 길이 5의 수열이 될 수 있다는 것을 알아내고 2를 출력해야 하는데, 그냥 무의미한 수들로 판단해버리기 때문이다. 저렇게 띄엄띄엄 연속되는 경우를 어떻게 해야 잡아낼 수 있을까? 알고리즘 분류에 투 포인터가 있던데 그걸 힌트 삼아서 잘 생각해봐야겠다. 2022.03.23 해결되었다. 정답 게시물 바..

풀이방법 및 문제점 2022.02.22 왠지 스택을 이용해 풀 수 있을 것 같아서 스택으로 구현해보았는데 틀렸다. 50%에서 실패가 뜬다. 얌전히 동적 프로그래밍 또는 그래프로 풀어야겠다. 내가 시도한 풀이법은 다음과 같다. 문자를 저장하는 스택 A, B, C를 선언한다. 첫 번째 단어를 스택 A에, 두 번째는 B에, 세 번째는 C에 앞 글자부터 push한다. C의 top에 있는 글자가 A의 top에 있는 글자와 동일하다면 A와 C에서 한 글자를 pop한다. C의 top에 있는 글자가 B의 top에 있는 글자와 동일하다면 B와 C에서 한 글자를 pop한다. C의 top에 있는 글자가 A와 B 중 어느 것의 top과도 같지 않다면 no를 출력하고 다음 데이터로 넘어간다. no로 판별하는 일 없이 C가 텅 ..

풀이방법 및 문제점 2022.02.14 (1) 그리디 알고리즘 문제이다. 주어진 회의들을 끝나는 시간을 기준으로 오름차순 정렬한다. 정렬된 순서대로 차근차근 방문하며, 이전 회의와 겹치지 않는다면 즉시 스케줄표에 해당 회의를 추가한다. 그럼 빨리 끝나는 순서대로 차근차근 겹치지 않게 스케줄표에 추가할 수 있다. 그런데 87%에서 틀렸습니다가 뜬다. 백준에 올라온 다음의 테스트케이스에 대하여 올바른 답을 출력하지 못하는 것을 보고 원인을 알 수 있었다. 5 6 7 6 6 5 6 5 5 7 7 답:5 이 테스트케이스를 찾은 게시글 링크 끝나는 시간이 서로 같은 회의가 포함되어있을 경우를 고려하지 않은 것이 문제였다. 끝나는 시간이 동일한 회의끼리는 시작 시간을 기준으로 오름차순 정렬을 해주어야 한다. 그런데..

풀이방법 및 문제점 2022.02.12 55%에서 시간초과가 난다. 예제의 답은 옳게 출력된다. 일단은 출력 방식을 바꾸어봐야겠다. 18870번 문제를 풀 때처럼 System.out.println을 Q번 수행한 것이 문제일 수 있다. 혹은 재귀함수를 많이 써서 시간이 많이 걸린 것일까? 트리를 생성하는 makeTree 함수도 재귀함수이고, 서브트리의 노드의 개수를 구하는 count 함수도 재귀함수이다. 하지만 재귀를 쓰지 않는 방식이 떠오르지 않는다. 자고 일어나서 생각해봐야겠다. 혹은 트리의 구현 방식이 문제일 수도 있다. 다른 방식으로 구현해봐야겠다. 자바에서 트리 형식의 라이브러리를 제공하는지도 알아봐야겠다. 사용한 풀이 방법은 다음과 같다. 먼저, n-1개의 간선 정보를 인접 리스트(ArrayLi..

풀이방법 및 문제점 2022.02.05 (1) 예제 입력에 대한 출력값은 올바르게 나오지만 채점 결과는 틀렸다고 나오는 상황이 또 발생했다. 큰일이다... 문제점이 무엇인지 모르겠다. 채점 시 6%에서 틀렸습니다 가 나온다. 잠이 부족한 상태에서 풀다 보니 놓친 반례가 생긴 것일까? 단계별로 다시 차근차근 검토해보아야겠다. 사용한 풀이방법은 다음과 같다. 가장 위 한 줄을 잘라내면, 이번 차례에 비교대상이 되는 단어들은 모두 앞전에 비교대상이었던 단어들의 가장 앞 한 글자만 떼어낸 접미사이다. Polynomial Hashing 기법을 사용하면 접미사를 빠르게 해싱할 수 있으므로, Polynomial Hashing으로 모든 접미사들의 해싱을 미리 끝내둔 뒤, 그 해시값을 비교하며 count 값을 구하였다...

풀이방법 및 문제점 2022.01.28 (1) 입력 수열의 값을 복사한 temp 배열을 크기순으로 정렬하면 각 좌표의 압축 결과를 쉽게 구할 수 있다. 그 다음 temp값과 기존 입력 수열의 값을 비교하여 본래 순서에 맞게 결과값을 화면에 출력하였다. 문제점: 시간초과. 데이터의 개수 N이 최대 100만 개이고 제한시간은 2초이다. 그런데 압축 결과값을 구하는 부분, 값을 출력할 순서를 알아내기 위해 기존 입력 수열을 조회하는 부분 모두 $N^2$의 시간복잡도를 가져서 시간을 많이 초과하였다. 2022.01.28 (2) HashMap을 사용하여 코드를 짜보았다. HashMap의 key에는 정수 값을, value에는 순위를 저장한 뒤 조회하는 방식이다. 그런데 또 시간이 초과된다. 얼마나 더 빨라져야 하는..