그리디 알고리즘을 쌈싸먹어 보자2
문제 예제 (1) : 백준 잃어버린 괄호
내 풀이
- 세준이는 왜 이런 일을 하는 걸까..? 진짜 이상한 애야..
- '+'와 '-' 연산으로만 이루어져 있다는게 포인트인 것 같다.
- '+'만 있는 경우엔 더하기만, '-'만 있는 경우엔 빼기만 하면 된다. 즉 문제는 더하기랑 빼기가 섞여 있는 경우!
- 상식적으로 생각하면 결과가 작으려면 작은 수에서 큰 수를 빼면 된다.
- 그럼 빼기 연산자 바로 뒤에 더하기 연산자가 나온다면, 그 위치에 괄호를 넣으면 된다.
- ex. a-b+c가 있다면 a-(b+c) 요런식으로!
- 습 근디 코드로 어케 구현하지?
근데 문제가 괄호의 위치를 구하는게 아니라, 최소값을 구하는거니까 그냥 + 연산자가 나왔을 때 -계산을 하면 되는거 아닌가..?!- 구론데구로나 + 연산자만 있는 경우엔 + 연산만 해야 한다. 그렇다고 전체 반복을 돈 다음 +만 있는지 -만 있는지 둘다 있는지 케이스를 나눠서 수행하면 쓸데없이 코드 라인만 길어지고 반복도 많이 돌게 된다.
- StringTokenizer로 음수 기준으로 자르고, 자른 문자열에 연산자가 끼어있다면 더해서 빼자
- 근데 문제가 있다! 맨 초기값을 정해야 하는데, 만약 + 연산자만 있다면 StringTokenizer가 자르지 못하니까 숫자로 형변환를 할 수 없다.
- result를 이상한 값(MAX_VALUE 등)으로 초기화하고 조건문으로 체크해주는 방법도 있겠지만, 마지막에 result에서 초기값을 다시 연산해주는게 싫어서 && 혹시라도 반복문 중간에 초기값이 또 나올까봐 boolean 플래그를 하나 두었다.
- 근데 문제가 있다! 맨 초기값을 정해야 하는데, 만약 + 연산자만 있다면 StringTokenizer가 자르지 못하니까 숫자로 형변환를 할 수 없다.
int result = 0;
boolean isFirst = true;
while (st.hasMoreTokens()) {
String subStr = st.nextToken();
int subResult = 0;
StringTokenizer plusSt = new StringTokenizer(subStr, "+");
while (plusSt.hasMoreTokens()) {
subResult += Integer.parseInt(plusSt.nextToken());
}
if (isFirst) {
result += subResult;
isFirst = false;
}
else result -= subResult;
}- 맞았다ㅎㅎ
해설
- sign와 minus 변수 두개를 활용한다.
- 만약 + 연산자가 나오면 sign에 1을, - 연산자가 나오면 sign에 -1을 넣는다.
- 이후 minus 변수를 이용, sign에서 -1이 한 번이라도 나오면 그 이후로 나오는 모든 수를 전부 뺀다 (+와 -가 섞인 경우니까 전부 빼기로 대체)
근데 이게 왜 그리디 유형인지 아직 잘 모르겠다..! 😇
문제 예제 (2) : 백준 수 묶기
내 풀이
- 아까는 더하기, 빼기를 응용해서 최소값을 구했다면 지금은 곱하기를 응용해서 최대값을 구하기!
- 조건 : 동일 숫자를 묶어서 곱하면 안됨, 모든 수는 단 한번만 묶거나 혹은 묶지 않아야 함, 정답은 항상 2^31보다 작음
- 당연히 곱해서 큰 수끼리 묶어야겠지?
- 일단 수를 입력받는데, 음수랑 양수를 묶으면 안되니까 따로 입력받자.
- 입력받은 수들을 내림차순 정렬하자. 이때 음수는 오름차순 정렬해야한다.
- 왜냐하면 음수 * 음수는 양수니까, 작은 순서대로 정렬해야 결과적으로 수가 커지기 때문!
- 0은 음수 배열에 들어가야한다.
- 만약 입력받은 음수가 총 짝수개라면, 음수와 곱해서 0으로 만들어 더하는게 좋고, 홀수개라면 오름차순 정렬해서 마지막 남은 1개 (묶이지 않은)로 더해주는게 좋으니까.
- 이후 각각 배열에서 수를 묶어서 결과값에 더한다.
- 배열 사이즈가 홀수라면 제일 마지막 인덱스는 제외하고 묶고, 짝수라면 고냥 다 묶는 방식
- 근데 대차게 틀렸다ㅋㅋㅋㅋ
- 왜지? 하고 테케를 다시 흝어봤는데, 하나하나 다 돌려보니 [2, 1, 1]에서 틀렸다!
- (테케 다 돌려보지도 않고 제출한 내가 돌멩이긴 함ㅠㅠ)
- 위처럼 1이 짝수개 연속해서 나온다면, 걍 각자 더하는게 더 결과가 커지기 때문! 진짜...멍청하다 나 자신....
public static int tieNum(List<Integer> numList) {
int result = 0;
int size = numList.size();
int j = 0;
while (j < size) {
// DESCRIBE: 전체 크기가 짝수일 때 마지막 수가 아니라면, 그리고 현재랑 다음이 1이 아니라면 곱해서 더하기
if (j+1 < size && numList.get(j) != 1 && numList.get(j+1) != 1) {
result += numList.get(j++) * numList.get(j++);
}
// DESCRIBE: 아니라면 각각 더하기
else {
result += numList.get(j++);
}
}
return result;
}- 맞았다~~
해설
- 양수는 큰 수끼리
- 하지만 1끼리는 묶지 말기!
- 음수는 작은 수끼리
- 0은 묶지 않는 것이 최대
- 하지만 묶이지 않은 음수가 있다면 0을 이용하자
- 처음 숫자 입력 받을 때부터 1의 개수와 0의 개수를 세고, 양수 배열과 음수 배열을 짝수 사이즈로 만들어서 푸는 방법도 있다.
문제 예제 (3) : 백준 대회 or 인턴
내 풀이
- n과 m을 줄이면서 팀 수를 카운트하면 된다.
- 근데 이제 남은 사람으로 인턴십도 보내고~ 팀도 만들 수 있을 때까지!
int result = 0;
while (n+m >= k+3 && n >= 2 && m >= 1) {
n -= 2;
m -= 1;
result+=1;
}- 맞았돵
해설
- 아래 경우가 한 팀 (동일 접근)
- n+3 >= k+3
- m >= 1
- n >= 2
문제 예제 (4) : 백준 30 (10:53, 8분 종료)
내 풀이
- 미르코씨...재밌게 사시는 분이시군요
- 30의 배수 = 3 * 10의 배수
- 즉 아래 조건을 충족해야 한다
- 하나 이상의 0 포함 (10의 배수가 되려면 마지막 자리가 0이여야 함)
- 각 자리의 숫자들을 더했을 때 3의 배수여야 함 (3의 배수 조건)
- 일단 위 조건 충족 못 하면 바로 -1 리턴하게 하자.
- 충족한다면 이제 최대값을 찾아야함
~~- 위에서 3의 배수 조건을 이미 충족했으니 제일 마지막 자리가 0이기만 하면 된다.
- 입력값이 무조건 양수임을 이용, 입력 문자열을 정수 배열로 만들어서 내림차순 정렬하면 된다.
코드를 입력하세요- 맞았지렁
해설
- 동일 접근
호그와트 장학생