문제 문제링크 접근 나보다 강한 사람, 약한 사람의 수가 n-1일 때 그 사람의 순위를 알 수 있다. 그래서 단방향 그래프를 이용해 강한 사람, 약한 사람을 dfs를 이용해 찾았다. 풀고 난 후 다른 분들은 플로이드-워셜 알고리즘을 이용한 사람들이 많았는데, 비슷한 시간복잡도와 실행시간을 가지더랑 풀이

문제 문제링크 접근 처음에는 방문 여부를 체크하면서 정답을 늘려야 하나 고민했지만, set을 이용하면 중복처리를 쉽게 할 수 있을 것 같아서 그 방향으로 생각하였다. 중요한 부분은 모든 선분에 대해 고유한 수로 나타내는 getIndex를 잘 작성하면 크게 어려운 부분 없다. (약간 hashCode를 얻기 위한 해싱 함수라 생각하면 편하다) 풀이

문제 문제 링크 접근 여러 개의 간선을 지나고, 모든 정점을 방문해야 한다는 점에서 MST(최소 신장 트리)를 떠올렸다. MST 풀이 알고리즘으로는 대표적으로 크루스칼, 프림이 있다. 그 중 나는 우선순위큐, union-find를 이용하는 프림을 채택하였다. 프로그래머스 level3 치고는 전형적이고 쉬운 문제 같다. 소스 코드

문제 문제링크 접근 제곱 관련 문제가 나오면 제일 많이 사용하는 개념은, 제곱한 두 수의 합이 가장 작은 경우는 두 수의 차가 가장 작을 때라는 것이다. 수학적 증명을 간단하게 설명하자면 a, (a+x) 이렇게 두 수가 있다면, 제곱에서는 x^2은 양수가 되기 때문에 그 값이 최소가 되어야 합이 최소가 된다. 그래서 두 수의 차이가 작아야 제곱의 합도 최소가 된다. 위 개념을 이번 문제에 적용하려면, 값들끼리의 차를 최소로 해야한다. 그래서 n번만큼 최대값을 줄여나가는 방식을 채택하였다. 우선순위큐를 활용하여 매번 최댓값을 가져왔다. 소스 코드 정답 소스는

문제 문제링크 접근 백트래킹 그림만 그려지면 금방 풀리는 문제이다. 방문 여부를 포함하고 있는 간선 클래스를 통해 형태로 map을 구성하여 dfs, 백트래킹을 이어갔다. map을 사용할 때 항상 get이 null을 반환하는지를 조심하자! 풀이

문제 문제 링크 접근 알파벳 인덱스 변환이 양쪽으로 자주 일어나기 때문에 이 과정에서 시간복잡도를 줄이는 것이 안건이라고 생각했다. 암호 생성할 때 2차원 배열에서의 탐색이 필요하기 때문에 2차원 배열에 알파벳을 저장하고, 저장할 때 Map에 정보를 저장하여 조회가 둘 다 상수 수준에서 이루어질 수 있도록 하였다. 암호 생성은 간단한 배열 인덱스 처리로 해결할 수 있다. 이 과정이 논리는 간단하지만 코드가 조금 길게 나온다. 줄이는 방법 찾고 싶당 풀이

문제 문제 링크 접근 N 범위는 그렇게 크지 않아서 모든 순열을 조회하며 분기하는 풀이를 떠올렸다. 그런데 시간 복잡도가 O(N^3) 수준이라 배제하였다. 백준의 [ 가장 수열 ] 시리즈의 접근법이 떠올라 dp를 떠올렸고, 전혀 다른 풀이였지만 해결하였다. 최종적으로 시간복잡도는 O(NlogN)가 되었고, 넉넉하게 통과하였다. 풀이

문제 접근 먼저 나의 풀이는 다른 사람들의 풀이와 접근 자체가 다르다. 다른 사람들은 이분탐색으로 풀었는데, 다 풀고 다른 사람 풀이를 보니까 이분탐색으로 푸는 것이 더 좋을 것 같다. 이분탐색을 이용할 경우 탐색 자체는 O(logn) 수준이지만, 모든 수를 탐색 당 한 번씩 돌아야하기 때문에 O(mlogn)의 시간복잡도를 가진다. 나의 풀이는 순차탐색을 기반으로 하고 있기 때문에 O(n)의 시간복잡도를 가진다. 시간복잡도는 나의 풀이가 더 작지만, 이 문제에서는 m보다 n이 더 크기 때문에 실행 결과를 비교해보니 실행시간이 비슷하였다. 하지만 나의 풀이는 수학적 연산이 들어가있기 때문에 알고리즘 풀이를 할 때는 범용성이 더 작아보인다 ㅜ 나의 풀이를 설명하자면 아

문제 문제링크 접근 처음에는 문제가 생각보다 쉽다 생각하고 아래와 같이 정렬과 indexOf 메서드를 활용하였지만 반 이상이 시간초과가 났다... ㅠ O(n) 수준 이하로 복잡도를 낮추기 위해서 고민하다가, 수 범위가 1000이하로 좁다는 것을 확인하였다. 1000 모든 값에 대해서 누적합 dp를 이용하면 시간복잡도를 낮출 수 있을 것이라 생각하고 풀었다. cnts에는 해당 인덱스에 같은 사람 수를 저장한다. 0으로 초기화되므로 그냥나온 수만 저장하면 된다. dp는 내림차순이므로 제일 끝에서부터 내려오는데, dp에는 지금까지 누적 사람 수를 저장하는 것이다. 최종 출력에는 해

문제 문제 링크 접근 n이 크기 때문에 시간복잡도 O(n)이하으로 맞추어야 한다. 처음에는 아래 코드로 0.0x수준으로 정확성 테스트를 통과하였지만, 효율성 테스트를 하나도 통과하지 못했다... 다시 읽어보니 stations가 오름차순으로 정렬되어 있는 것을 확인하였고, 인덱스 연산에 이를 반영하였다. 풀이

문제 문제링크 접근 기본적으로 스택을 이용한 괄호 유효성 검사 알고리즘이 필요하다. 괄호 회전 처리는 인덱스의 증감으로 처리하여 순회하며 개수를 센다. 풀이

문제 문제 링크 접근 투 포인트를 이용한 문자열 분리와 해싱을 통해 해결하였다. 한글자 단위로는 다 해싱이 되어 있으므로, 두 글자 이상부터 해당 문자열이 사전에 포함되어 있는지 확인한다. 이때 점점 늘려가다가, 없는 순간의 바로 앞칸을 이용하여 최장 길이를 찾는다. 반복문 종료 조건을 end 인덱스로 잡는다면, 마지막까지 한 칸의 단어가 사전에 포함되어 있다는 것이기 때문에 해당 문자열 관련해서도 처리한다. 풀이

문제 문제링크 접근 자바 정규식을 활용하면 쉽게 풀이할 수 있다. 특정한 로직으로 정렬을 할때는 Comparable을 상속 받고, compareTo 메서드를 오버라이드하여 활용한다. 풀이

문제 문제링크 접근 처음에는 이전처럼 getNextIdx() 메서드를 만들어서, 끝값을 분기했었는데 너무 잦은 메서드 호출이 걱정되었다. 어차피 중복 값은 취급하면 안되기 때문에 배열에서 임시로 같은 배열을 뒤에 붙이면 모든 경우의 수를 다룰 수 있다. 풀이

문제 문제링크 접근 가장 앞자리가 바뀔 때마다 아래 자리 수의 경우의 수 만큼 건너 뛰어야 한다. 예를 들어 A -> E로 갈때는 A를 가장 앞글자로 두는 모든 단어들을 건너뛰어야 한다. 그래서 4자리의 모든 경우의 수를 계산하고, 몇 칸 넘어가는지를 곱하면 된다. 모든 경우의 수는 제곱 연산의 합으로 구하였다. 각 자리 수마다 같은 연산을 반복하였다. 풀이

문제 문제링크 접근 1로 시작하는 누적합 배열과, -1로 시작하는 누적합 배열을 구분하여 풀이를 시작하였다. 해당 인덱스 전까지 경우의 수들을 비교하며 최댓값을 탐색하였는데, 줄어드는 이중반복문이라 O(nlogn)의 시간복잡도를 가진다. -> 시간초과 O(n) 수준의 시간복잡도를 고민하다가 누적합을 더하는 과정에서 현재 인덱스까지의 최소합을 저장하여 차를 구하도록 하였다. 각 인덱스의 차를 최대값과 비교하여 최대값을 찾는다. 소스 코드

문제 문제 링크 접근 가장 먼저 가장자리에 따라 BFS 탐색을 해야 한다는 생각에서 출발하였다. 테두리 정보를 쉽게 입력에 따라 배열에 표시하여 쉽게 얻을 수 있을 것 같다 생각하였다. 그런데 특정 점 좌표와 채워진 면적 정보를 2차원 배열로 고민하는 과정에 두 용도를 구분하여 2개의 2차원 배열로 정보를 나타내었다. 한 좌표에 대해 제 1,2,3,4사분면의 면적이 채워진 여부에 따라 테두리인지 판단하였다. 소스코드

문제 문제링크 접근 스택을 활용한 연산을 할 때 우선순위를 사용하여 더 꺼낼지 말지 판단한다. 그래서 이 문제도 그 우선순위에 대하여 완전탐색하면 최대값을 구할 수 있다. 정규식으로 연산자와 피연산자를 각각 처리하여 쉽게 파싱하였다. 내부 값이 딱히 필요 없기 때문에 속도 향상을 위하여 Dequq를 사용한다. 소스코드

문제 문제링크 접근 끝나는 구간을 오름차순으로 정렬하고, 한 범위에 대해서 최대한 뒤쪽에 요격 하면 이후의 범위에 최대한 들 수 있다. 구간들을 순회하면서, 현재까지의 가장 마지막 요격 지점이 현재 구간에 포함되면 현재 구간을 무시해도 되기 때문에 다음 순회로 넘어간다. 양쪽이 개구간이라는 것이 유의할 점이다. 소스코드

최근 자바 버전 관련 이슈에 정말 많이 부딪혀서 정리하게 되었다. 보통 개발 전에 Java SE 8, Java SE 11, Java SE 17 중에 선택하는 것 같다. JDK, Java SE 등 이름도 다양해서 시간 순으로 정리하였다. 실제로 개발할 때 사용한 컨텐츠 위주로 정리하였다. 💣 JDK JDK 1.0 1996년 1월 23일 첫 출시 JDK 1.0.2가 첫 안정화 버전이고, Java 1이라 불림 JDK 1.1 1997년 2월 19일 awt 이벤트 모델 정비, 내부 클래스, Java Beans, 직렬화 JIT (Just In Time) 컴파일러 🔮 J2SE (Java 2 Platform, Standard Edition) J2SE 1.2