소통 하고싶은 개발자

문제 개요 풀이 연속된 문자열 S가 주어지고, 문자열에 "0"과 "1"만이 존재한다고 가정할 때 연속된 일부분을 선택해서 뒤집는 방식으로 모두 같은 문자로 이루어진 문자열을 만든다고 한다. 문제를 풀려면 1로 이루어진 문자열 덩어리의 개수와 0으로 이루어진 문자열 덩어리의 개수 중 적은 개수를 출력해주면 된다. 단, 여기서 주의할 점은 처음부터 문자열이 모두 같은 한 문자로 이루어진 경우에는 0으로 출력해주는 처리를 해줘야 한다. 나는 다음 순서로 알고리즘 해결을 위한 순서를 생각했다. 연속된 문자열을 split()을 사용해 배열로 만든다. 그 배열을 향상된 for문으로 차례대로 돌면서 "1"로 이루어진 덩어리와 "0"으로 이루어진 덩어리의 개수를 특정한다. 만약 1덩어리와 0덩어리의 합이 1인 경우 원..

문제 개요 풀이 문제에서 원하는 바를 한 줄로 요약하자면, 입사 지원자들을 평가하기 위한 두 종목의 점수가 주어질 때 지원자의 점수를 모두와 비교해서 전체적으로 적어도 한 개 이상의 점수가 높은 사람의 수를 구해야 한다. 사실 브루트 포스 방식으로 문제를 풀면 로직을 작성하는 것은 간단한 일인 것일지 모른다. 만약 브루트 포스로 접근한다면, 각 과목을 의미하는 배열 2개를 만들고(혹은 2차원 배열) 입력받은 값들을 저장한다. 2 중첩 for문을 사용해서 각 지원자의 등수와 다른 모든 지원자의 등수를 비교한다. (1:n) 한 지원자를 기준으로 다른 모두와 비교해야 하고, 이를 전체 지원자를 대상으로 실시해야 하기 때문에 시간 복잡도가 n²가 된다. 루프를 돌면서 만약 비교하려는 상대가 자신보다 두 과목의 ..

문제 개요 풀이 입력 값이 아래와 같이 주어졌을 때 기름 값으로 드는 비용의 최소 비용을 구해야 한다. 각 도시에서의 기름 값 도시와 도시 사이의 거리 경유해야 할 도시의 순서 문제에도 나와있지만 기름을 구입하는 시기에 따라 최종 목적지까지 도착했을 때 소비한 총액수가 달라지므로 그리디 알고리즘으로 풀어야 한다. 문제를 풀기위한 내 생각은 다음과 같다. 각 도시에서의 기름 값 정보, 도시와 도시 사이의 거리를 차례대로 입력받는다. 차례대로 입력받은 정보가 경유 순서가 된다. 첫 도시부터 시작해서 현재 도시의 기름 값과 다음 도시의 기름 값을 비교한다. 반복하는 과정에서 만약 현재 도시의 기름 값이 다음 도시보다 저렴한 경우에는 현재 도시에서 기름을 더 사고 가는 것이 유리하므로 기름을 더 구매한다. 현재..

문제 개요 풀이 전자레인지에 버튼 A, B, C가 있고 누르면 각각 5분, 1분, 10초씩 추가될 때 우리가 원하는 시간을 만들기 위해 버튼을 최소로 누르려면 각 버튼을 몇 회씩 눌러야 하는지 구해야 한다. 이 문제는 그리디 알고리즘으로 풀어야 하는 전형적인 문제였다고 생각한다. 문제를 풀기위한 과정은 목표 시간에서 시간이 가장 많이 추가되는 버튼의 시간을 나눈다. 나눈 몫을 따로 저장하고, 나머지를 다시 목표 시간으로 설정한다. 두 번째로 시간이 많이 추가되는 버튼의 시간을 새롭게 설정된 목표 시간에서 나눈다. 2번의 과정을 반복한다. 전체 버튼의 시간을 나눌 때까지 위 과정을 반복한다. 이를 코드로 작성해봤다. 코드 import java.io.*; public class Main { public st..

문제 개요 풀이 전체 로프의 정보가 주어질 때 해당 로프들로 들 수 있는 최대 중량을 구해야 한다. 문제에서 원하는 값을 구하기 위해 생각했던 최초의 방법은 각 로프들 중 최소의 중량을 가지는 로프를 구한 뒤, 해당 로프의 중량에 전체 로프의 수를 곱하여 이 값을 출력하는 것인데, 결론적으로 잘못된 접근 방식이다. 위 생각이 이유를 찾는 과정에서 개인적으로 테스트 케이스가 더 많았다면 빨리 오류를 찾을 수 있었을 텐데 라는 생각을 했지만, 예시 입출력이 존재하는 것만으로 감사해야 하기에, 더욱 정진해야겠다는 마음을 먹었다..ㅠ 만약 [30, 34, 20, 16, 5] 라는 입력이 존재할 경우에 최초의 생각대로 풀면, 최소 값이 5이므로 최대 중량은 5 * 5 = 25라는 것이 된다. 여기서 문제 하단을 ..

문제 개요 풀이 이번 문제의 핵심은 덧셈과 뺄셈만 존재하는 정상적인 수식이 존재할 때, 괄호를 넣는 위치에 따라 결과 값이 달라진다는 것이다. 가령 아래의 두 예시를 보자. (55 - 50) + 40 = 45 55 - (50 + 40) = -35 두 예시의 결과 값이 다른 이유는 수식을 계산하는 순서에서 괄호 안의 수식을 우선으로 계산해야 하기 때문이다. 이 문제는 백준 알고리즘에서 그리디 알고리즘으로 분류되어 있다. 즉, 최적의 가설을 세우고 이를 코드로 작성해야 한다는 것이다. 때문에 나는 최소의 결과 값을 얻기 위해 이런 가설을 세웠다. 문자열을 검사하면서 '+' 기호가 나오면 이전 수와 다음 수를 누적해서 더해주고, '-' 기호가 나오면 지금까지 누적되었던 수를 빼도록 괄호를 만들면 최소 값이다...

문제 개요 풀이 100보다 작은 정수가 담긴 두 개의 배열의 항목들의 곱을 더한 값이 가장 작아졌을 때, 해당 값을 출력하면 되는 문제이다. 나는 문제를 처음 보고 '배열 A만 재배열이 가능하다'라는 전제 조건에 의해 헷갈릴 뻔했다. 그런데 출력해야 하는 값이 A배열의 아이템이 아닌 곱하고 더한 값 자체를 출력하면 되는 것이기 때문에 사실 'A만 재배열하라'와 같은 전제 조건은 의미가 없다. 사실 곱했을 때 값이 가장 작아야 하기 때문에 순서대로 큰 값과 작은 값이 매칭되도록 작성해주면 된다. 왜냐면 큰 값과 큰 값을 곱하게 되면 더 큰 값이 출력되기 때문이다. 내가 생각한 로직의 순서는 다음과 같다. 배열 A와 배열 B를 각각 정렬한다. 반복문을 만들고 인덱스 변수를 사용하여 큰 값과 작은 값이 매칭될..

문제 개요 풀이 문제에서 원하는 바를 요약하자면 '같은 시간대에 두 개 이상의 회의가 일어나지 않는 조건일 때, 가장 많은 회의를 발생시키려면 몇 개의 회의가 진행될 수 있는지 구하는 프로그램을 작성하라'이다. 우선 백준 카테고리에서 그리디 알고리즘으로 검색했기 때문에 처음부터 그리디 방식을 사용해야겠다 라는 생각으로 문제에 접근했다. (아니었다면 조금 더 헤맸을 것 같다.) 나는 이 문제를 처음 직면하고 세 가지 정도의 생각을 했다. 회의 런 타임이 짧은 순서대로 입력받은 회의를 정렬하고 끼워 맞추자. 회의 시작 시간을 기준으로 입력받은 회의를 정렬하고 반복문으로 개수를 정하자. 회의가 종료되는 시간을 기준으로 입력받은 회의를 정렬하고 반복문으로 개수를 정하자. 가장 처음에 했던 런 타임이 짧은 순서로..

문제 개요 풀이 이 문제는 이전에 풀었던 설탕 배달 문제와 아주 유사하다. 첫 줄에 동전의 개수와 타겟이 주어지는데, 타겟을 나눌 수 있는 가장 큰 동전을 사용할 수 있는 만큼 사용하고, 나머지를 두 번째 큰 동전, 세 번째... 의 순서로 빼면서 개수를 구하면 된다. 이 문제 같은 경우는 입력받는 동전의 단위가 1 혹은 5의 배수로 나누어 떨어지기 때문에 반드시 나누어 떨어질 수 있다는 가정이 보장된다. 만약 이렇지 않고 입력이 {1, 2, 3, 13}과 같이 애매한 숫자가 나온다면, 풀 수는 있으나 난이도가 올라갈 것이다. 어쨌든 문제를 보자마자 이렇게 해야겠다 생각이 들었던 사람도 있을 테지만, 그렇지 않다면 그냥 그리디하게 풀면 되는구나 하고 이해하고 넘어가면 될 것 같다. 내가 생각한 풀이 과정..

문제 개요 풀이 줄을 서는 순서에 따라 모든 사람들의 기다리는 시간의 총합이 달라질 때, 총합이 가장 적어질 때를 구해야 한다. 즉, 아무렇게나 줄을 설 수 있지만 전 인원의 웨이팅 시간의 합이 가장 적어지는 경우를 특정해야 하므로 그리디(탐욕)하게 접근해야 한다. 지문 속 예시대로 인출하는 데 걸리는 시간이 적은 순서대로 줄을 세웠을 경우가 우리가 특정하고자 하는 경우이다. 내가 생각한 로직의 순서는 전체 사람들의 인출 시간을 입력받아 int형으로 변환한다. 해당 데이터를 오름차순으로 정렬한다. 반복문을 이용해서 각 사람이 기다리게 되는 수를 구한 후 더해준다. 단순히 int형 변수인 sum을 하나 선언해서 sum을 반환하면 안 된다. sum을 선언했을 경우에 반복문 속에서 sum의 의미는 각 사람이 ..