풀이 선택 정렬로 푼 코드이다. 소스 코드 import java.util.*; public class 소트인사이드 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String num = sc.next(); int[] arr = new i...

풀이 문제의 C++코드를 보면, 버블 정렬에서의 2중 for문 중, 안쪽 for문이 돌아갔는데도 정렬을 하지 않았을 경우, break한다. 즉,정렬이 다 되어있을 경우에, for문을 끝까지 돌지 않고 중간에 탈출한다는 것이다. 그리고 이를 몇번쨰 인덱스에서 탈출했는지를 출력한다. 문제에서 주어진 n이 500,000이기 때문에, 똑같이 버블정렬을 ...

풀이 1부터 n까지의 카드가 위에서부터 있고, 그 카드를 다음과 같은 두가지 동작을 순서로 카드가 1장 남을 때까지 반복한다. 맨 위 카드를 버린다. 맨 위 카드를 빼서 맨 아래로 넣는다. 는 큐.poll() 큐.add(큐.poll()) 과 같다. 즉, 큐를 통해 간단하게 풀 수 있는 문제이다. 소스 코드 import...

풀이 투 포인터 개념을 도입해 사용하는 문제이다. 투 포인터 개념은 배열을 탐색할 때 인덱스 포인터를 두개를 사용하여 탐색하는 개념이다. 이 문제의 경우, n의 최대가 15,000이므로 정렬을 사용해서 투 포인터 개념을 사용하고자 한다. 입력받은 배열을 정렬한 후, 한 포인터는 배열의 첫번째(start), 다른 한 포인터는 배열의 마지막 원소(en...

풀이 일단 문제를 이해하는데 오래걸렸다…문제를 잘 읽어봐야 한다. 1부터 n까지의 수를 스택에 일단 넣는다는 문장이 있다. 즉, 입력받은 수열대로 1부터 n까지의 스택에서 꺼내오려면 어떤 연산이 필요하냐는 것이다!! 예제 입력에서 처음 값인 4가 1부터 n까지의 오름차순 스택에서 나오려면, 일단 빈 스택에 1,2,3,4를 넣고 4를 빼야하기 때...

풀이 투 포인터 개념을 활용해야 하는 문제이다. 투 포인터의 개념은 배열을 탐색할 때 인덱스 포인터를 두개를 사용해서 배열을 탐색하는 개념이다. 근데 이 문제에서는 포인터가 3개..라고 볼 수도 있을 것 같다. 탐색 방법 입력 받은 배열을 오름차순으로 정렬하여, 두개의 포인터 이동의 기준을 잡는다. 정렬하는 이유는, 찾고자 하는 값...

풀이 문제에 힙이라고 적혀있듯이, 우선순위 큐를 사용하는 문제이다. 그런데, 우선순위 큐의 정렬 조건이 절댓값이고, 절댓값이 같을 경우 작은 숫자를 우선으로 한다. 이를 구현하는게 이번 문제의 핵심이다…조건 걸어주는게 힘들었다. 조건을 걸어주고 나면, 문제에 쓰여있는 대로, x가 0일 때 출력하고 삭제(poll())해주고, 다른 값일 땐 큐에 입...

풀이 주어진 범위 안에서 최솟값을 찾는 문제이다. 주어진 범위가 움직이므로, 윈도우 슬라이딩 문제이다. 윈도우 슬라이딩이란, 범위가 창문 움직이듯이 옆으로 옮겨가는 것이다. 이 문제의 경우, n은 5,000,000이고, l은 10^9이다…즉, O(n)인 알고리즘으로만 풀어야 한다. 그렇다면, 정렬의 시간 복잡도 하한선이 O(nlogn)이므로, 어떠...

풀이 n이 최악의 경우 10,000,000까지 커지므로, O(N)인 알고리즘을 사용해서 풀어야한다. 이런 경우 투 포인트 개념을 도입하여 풀 수 있다. 즉, 시작 인덱스 포인터와 끝 인덱스 포인터, 이 2개의 포인터를 가지고 배열을 탐색하는 것이다. 그러면 배열을 한 바퀴 돌 때(O(N)의 시간 복잡도) 이 문제에서 원하는 모든 계산을 할 수 있...

풀이 2차원 배열의 구간 합 구하기 문제이다. 1차원 배열의 구간 합 구하기(구간 합 구하기 4-백준 11659번)에서와 같이, N과 M이 100,000이므로 구간 합으로 접근해야 한다. 2차원 합 배열 생성 공식 : termSum[i][j] = termSum[i][j-1] + termSum[i-1][j] - termSum[i-1][j-1] ...