[코테연습] 조이스틱
오늘은 탐욕법과 관련된 문제를 풀었다.
https://school.programmers.co.kr/learn/courses/30/lessons/42860
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
조이스틱 문제 였는데, 해당 문제를 분석하여 논리적으로 나누어보면 다음과 같다.
1. 조이스틱 위, 아래로 조작
- A 에서 위, 아래로 조작시에 특정 문자가 가장 가까운 수를 구한다.
- 해당 문자를 Map<String, Integer> 로 저장해둔다.
2. 조이스틱 왼쪽, 오른쪽으로 조작
- for 문으로 각 문자에서 왼쪽 / 오른쪽으로 갈때 길이를 구한다.
- 길이를 구할때 A 문자열이 연속되는 경우를 뺀다.
이 문제에서 가장 중요한 포인트는 조이스틱을 왼쪽과 오른쪽으로 조작할때이다.
왼쪽에서 오른쪽으로 이동하는 것은 문제가 되지 않는다. 이 경우에는 name.length - 1 의 조작횟수를 갖게된다.
하지만, 왼쪽에서 오른쪽으로 가다가 꺾어서 다시 왼쪽으로 쭉 가는 경우 (2)
처음부터 오른쪽으로 가다가 왼쪽으로 꺾어서 가는 경우(3) 가 변수 일 것이다.
잘 생각해보면, JANENG 라는 문자열이 있을 때
왼쪽에서 오른쪽으로 갈때는 JANENG 로 조작할 필요가 없다.
> (2)
오른쪽으로 가다가 왼쪽으로 갈때는 중복되는 횟수가 존재한다. 해당 중복을 배열의 index 로 확인하면 꺾는 지점을 3번째 index 라고 할때
0 1 2 3 // 2 1 0 // 5 4
이다.
0 1 2 만큼의 중복이 발생하는 것을 알 수 있다.
이를 수식으로 적는다면
i = 3 // i * 2 = 6 이다.
나머지 5,4 를 세기위해 수식으로 적는다면
name.length - (i + 1) = 6 - (3 + 1) = 2 이다.
이를 반복문과 결합해보면다면
int min = name.length - 1;
for (int i = 0; i < name.length; i++ ) {
min = Math.min( i * 2 + name.length - (i + 1), min );
}
일 것이다.
단 'A' 가 연속되는 수를 빼야함으로 while 문으로 i + 1 에서 'AA' 가 중복되는 수를 빼준다.
int min = name.length - 1;
for (int i = 0; i < name.length; i++ ) {
int index = i + 1;
while(index < length && arr[index].equals("A")) {
index++;
}
min = Math.min( i * 2 + name.length - index, min );
}
> (3)
처음부터 왼쪽으로가다가 오른쪽을 갈때의 경우를 따져보자
JANENG 라는 문자열이 있을때,
i = 3 에서 꺾는다고 하면
5 4 3 // 4 5 // 0 1 2
4 5 만큼 중복이 발생하는 것을 알 수 있다.
이를 수식으로 확인해본다면
( name.length - (i + 1) ) * 2 = (6 - 2) * 2 = 4
것이다.
나머지 0 1 2 는 i = 3 으로 셀수 있다.
이를 반복문과 함께 본다면
int min = name.length - 1;
for (int i = 0; i < name.length; i++ ){
min = Math.min(min, (name.length - (i+1) * 2) + i );
}
동일하게 'A' 가 연속되는 수를 빼기 위해서 while 문을 추가한다.
int min = name.length - 1;
for (int i = 0; i < name.length; i++ ){
int index = i + 1;
while(index < length && arr[index].equals("A")) {
index++;
}
min = Math.min(min, (name.length - index * 2) + i );
}
두 수식을 합치면 다음과 같은 답으로 문제를 해결 할 수 있다.