분류 전체보기

문제에서 요구하는 대로 코드를 짜면 되는 구현문제이다. 이 문제는 요구사항도 일곱단계로 정리해서 주었고, 효율성을 크게 요구하는 문제도 아니기 때문에 문제가 원하는대로 구현하면 쉽게 풀수 있는 문제이다. 약간 까다로운 조건이라하면, 연속으로 마침표를 사용할 경우에는 마침표가 제거된다는 점이 있었는데 백준 문자열폭발 문제에 비하면 까다로운 조건도 아니였다. 문자열 폭발처럼 스택으로 해결하지 않고 플래그로 해결했어도 됐지만, 나는 스택을 이용하여 풀었다. 문제조건은 아래와같다. stack 자료구조를 이용하여 쉽게 풀 수 있었다.

이분탐색 문제이다. 이번문제는 이분탐색인걸 모르는채로 풀었는데 문제를 읽자마자 이거 이분탐색이잖아? 라는 생각이 들었다. 내가 그래도 연습을 하긴했구나 싶어서 뿌듯했다. 항상 느끼는 거지만 이분탐색문제는 어떤 값을 찾을 것인가? 그 값이 내가 원하는 값인지 어떻게 검증할 것인가가 가장 중요하고 어려운것 같다. 이 문제에서는 몇 센티미터로 잘랐을 때 원하는 갯수만큼 가장 길게 줄 수 있냐고 묻는 문제이다. 즉, 몇 센티미터인가를 우리가 찾는 값으로 이 값을 기준으로 자르면 몇개를 만들 수 있냐를 통해 검색을 해나갈 수 있다. 이를 코드로 나타내면, 이렇게 된다. 이전에 풀었던 이분탐색문제들보다는 쉬웠던 문제인것 같다.

이 문제는 https://congsoony.tistory.com/158 이 블로그를 참고하여 풀었습니다, 위 블로그에서 설명하는 것처럼 문자열 폭발이라는 문제를 먼저 풀고 이문제를 풀면 그나마 쉽게 접근할 수 있다. 이 문제는 앞에서부터 가면서 원하는 단어가 있으면 삭제하고, 뒤에서 부터 탐색하는 과정을 반복한다. 앞에서부터 탐색하는 과정은 문자열 폭발이라는 문제와 동일하다. 스택을 이용하여 끝 문자가 같으면 검사하고 삭제하는 과정을 반복하는 것이다. 뒤에서부터 탐색하는 과정 역시 스택과 비슷하게 큐를 이용하면 같은 로직으로 해결할 수 있다. 그리고 이를 투포인터를 활용하여 앞에서 진행, 뒤에서 진행 반복하며 모든 문자열을 검사할 때까지 반복했다. 정리하면 아래와 같이 된다. 1. 문자열의 시작을 lef..

이 문제는 자료구조 (스택)에 관한 문제였다. 문제를 간략히 설명하자면, 입력으로 문자열과 문자열 폭탄이 주어진다. 문자열이 문자열 폭탄을 포함하고 있으면 폭탄 부분은 제거되고 앞뒤로 이어지는 새로운 문자열이 된다. 백준에 자료구조 문제들이 그렇듯 쉬운 방법(re라이브러리) 같은 것들로 풀면 당연히 시간 초과가 나는 문제이다. 결국 가장 효율적으로 폭탄들을 제거하면서 새로운 문자열을 만들어가야 한다. 반복을 자주 할수록 시간 소요가 많이 되기 때문에 최소한의 반복문으로 문자열을 만들 방법을 생각해야 한다. 나의 아이디어는 이렇다. 1. 문자열들을 순서대로 스택에 담는다. 2. 내가 담는 문자열이 문자열 폭탄의 끝 글자와 같으면 스택을 검사한다. 3. 이때, 문자열 폭탄이라면 스택에서 제거한다. 문자열의 ..

이분 탐색 문제이다. 이 문제는 총 M대의 놀이기구가 있을 때, N명이 순서대로 놀이기구를 탈 때, 마지막 사람이 타게 되는 놀이기구의 인덱스를 맞추는 문제이다. 문제를 봤을 때, 프로그래머스의 입국심사와 비슷한 느낌이 있었지만, 차이점이 있다고 느꼈고 나는 입국심사를 푼 테크닉을 바탕으로 약간의 아이디어를 추가하여 이문제를 풀었다. 이문제는 N명의 사람은 빈 놀이기구에 순서대로 들어가고, 각 놀이기구 마다 소요되는 시간이 다르다. 여기서 조심해야 할 점은 입국심사와는 다르게 사람들이 최소 시간을 위해 놀이기구 선택을 하는 것이 아닌, 여러 개가 비어있다면 단순히 인덱스가 작은 놀이기구부터 탄다는 점이다. 내가 문제를 푼 아이디어는 아래와 같다. 1. N-M명을 태울 때는 최소 시간을 위해 놀이기구를 선..

이 문제는 작업이 들어오는 시간과, 그 작업이 걸리는 시간을 알려주는 이차원 배열이 주어질 때 각 작업이 요청부터 종료까지 걸린 평균시간이 가장 적은 답을 구하는 문제이다. 살짝 보면 Greedy문제 같지만, 문제에서 제공된 예시들을 봤을 때, CPU 스케줄링의 SPN방식과, SRN 방식이 떠올랐다. 물론 문제에서 선점, 비선점에 대한 설명을 해주지 않아 어떤 방식으로 해야 할지 고민했지만, 우선 구현이 쉬워 보이는 SPN방식으로 문제를 풀어보았고 다행히 정답이 나왔다. SPN방식이란 기본적으로는 작업이 들어온 시간을 기준으로 작업을 처리하지만, 작업을 처리하는 중에 들어온 작업들에 대해서는, CPU요구량이 적은 것 부터 처리하는 비선점 방식의 스케줄링이다. 즉, 이문제의 요구사항과 같이, 기본적으로는 ..

이분 탐색 문제이다. 이 문제는 문제 설명 자체도 간단하지만 더 간략히 정리하자면, N*N크기의 이차원 배열에서 각 값은 row*col의 값을 가질 때(최소 인덱스를 1로 둠) T번째 수의 값을 구하는 것이다. 결국 T번째 수의 값을 이진탐색으로 찾아낼 수 있는 가를 구하는 문제이다. 역시 중간값 검증을 하여, 지금 탐색하고 있는 수가 몇 번째 수인지 찾아내는 것이 문제를 푸는 포인트인 것 같다. 1 2 3 2 4 6 3 6 9 N이 3인 이차원 배열은 이렇게 되고, 마치 구구단과 비슷한 모양이 된다. 이 배열에서 6은 몇번째로 큰 수인지 확인하기 위해서는 어떻게 해야 할까? 1행에서 6보다 작은 수는 3개, 2행에서 6보다 작은 수 역시 3개, 3행에서 6보다 작은 수는 2개로 총 8번째로 큰 수이다...

이분 탐색 문제이다. 이전 문제들과 마찬가지로 중간값 검증을 어떻게 할 것인지, 범위를 어떻게 할지 가장 중요했다. 이분 탐색으로 내가 찾고 싶은 값은 만들어진 구간의 최소 값이다. 즉 중앙값을 기준으로 구간을 만들 때 문제에서 원하는 구간 개수가 가능한지 검증한 후, 더 적게 나온다면 문제에서 원하는 구간 개수를 만들 수 있다는 뜻이므로, 최솟값을 찾기 위해 중간값을 줄이고, 더 많이 나온다면 중간값을 올리는 과정으로 문제를 해결하였다. 다시 정리하자면, 내가 원하는 값(중앙값)으로 구간을 나눌 때 M개 이하로 만들 수 있다면, 내가 정한 값으로 M개의 배열을 만들 수 있다는 것을 확실히 인지하여야 한다. 이를 이용하여 중앙값을 검증할 때, 내가 지정한 중앙값으로 배열의 최소 최대의 최대 차를 만들 수..