Cos Pro 1급 - 샘플 문제 5차 9번 - 연산 횟수 구하기(큐의 활용)

문제 지문 #9

정수 number와 target이 주어졌을 때, 다음 세 연산을 이용해 number를 target으로 만들려 합니다.

연산 1. 1을 더합니다.
연산 2. 1을 뺍니다.
연산 3. 2를 곱합니다.

정수 number와 target이 매개변수로 주어질 때, number로 target으로 만들려면 연산을 최소 몇 번 해야 하는지 return 하도록 solution 메서드를 작성해 주세요.

---

매개변수 설명

두 정수 number와 target이 solution 메서드의 매개변수로 주어집니다.

• number와 target은 0 이상 10,000 이하입니다.

---

return 값 설명

number를 target으로 만들려면 연산을 최소 몇 번 해야 하는지 return 합니다.

---

예시

number	target	return
5	9	2
3	11	3

---

예시 설명

예시 #1

1. 5 x 2 = 10
2. 10 - 1 = 9
   따라서 연산을 최소 2번 해야 합니다.

예시 #2

1. 3 x 2 = 6
2. 6 x 2 = 12
3. 12 - 1 = 11
   따라서 연산을 최소 3번 해야 합니다.

728x90

 

혼자 풀이

메서드 전체를 작성하는 문제입니다.
주어진 연산 1,2,3을 이용해서 number를 target으로 만들기 위해 필요한 연산의 횟수를 구해야 합니다.

저는 곱하기 연산으로 큰 수를 만들고 거기에서 더하기 빼기를 해서 target에 맞추는 것으로 코드를 짰는데,
결론적으로 틀렸습니다. 문제에 주어진 예시에 대해서는 정답을 내지만, 숫자가 조금만 커지면 안 맞더군요. 코드가 비루해서 굳이 공유할 필요도 없을 것 같고 바로 정답을 보겠습니다.

정답

정답에서는 큐를 활용하여 연산 횟수를 구했습니다.

1. number와 target이 10000 이하의 수이므로 1~10000을 담을 배열 visited를 선언합니다.
2. 시작 값인 visited[number] = 1로 초기화합니다.
3. 큐에 number부터 시작해서 number에 대한 +1, -1, x2의 계산 결과를 순차로 넣어줍니다.
4. n의 연산 결과인 n'가 기존에 방문한 적이 없는 수일 때, n'의 방문 횟수인 visited [n']에 visite [n]+1을 넣어줍니다.
5. n의 연산 결과인 n'가 target과 동일하면 visited[n']-1를 반환합니다. (1부터 시작했으므로 -1해야 연산 횟수)

위 예에서는 5는 2번의 연산 후에 9가 되었습니다.
아래 정답 코드에 주석으로 상세한 설명을 붙였습니다.

// 다음과 같이 import를 사용할 수 있습니다.
import java.util.*;

class Main {
	public int solution(int number, int target) {
		// 여기에 코드를 작성해주세요.		
		int answer = 0;
		//visited에는 10001개의 0을 항목으로 갖는 배열 각 숫자가 나오기 위해 연산한 횟수가 저장된다 
		int[] visited = new int[10001]; 
		Queue<Integer> q = new LinkedList<Integer>(); //연산의 결과를 넣을 큐(3개씩 나옴)
		q.offer(number);
		visited[number]=1; //visited에 number를 방문했음을 기록
		
		while(!q.isEmpty()){ //q가 빌때까지 
			int x=q.poll(); //q에서 하나를 꺼냄
			
			if(x==target) break; //q에서 가져온 값이 타겟과 같으면 종료
			
			if(x+1 <=10000 &&  visited[x+1]==0){  //x+1이 방문한 적이 없으면
				visited[x+1]=visited[x]+1; //visited[x]의 방문 횟수에 1을 더해서 visited[x+1]에 저장
				q.offer(x+1); //q에 연산 결과를 추가				
			}
			if(x-1 >=0 &&  visited[x-1]==0){  //x-1이 방문한 적이 없으면
				visited[x-1]=visited[x]+1; //visited[x]의 방문 횟수에 1을 빼서 visited[x+1]에 저장
				q.offer(x-1); //q에 연산 결과를 추가				
			}
			if(x*2 <=10000 &&  visited[x*2]==0){  //x+1이 방문한 적이 없으면
				visited[x*2]=visited[x]+1; //visited[x]의 방문 횟수에 2을 곱해서 visited[x+1]에 저장
				q.offer(x*2); //q에 연산 결과를 추가				
			}			
		}
		answer=visited[target]-1;
		return answer;
	}

 

실습은 아래 참고

2022.10.25 - [Programming/Cos Pro 1급] - Cos Pro 1급 공부 사이트 추천 - 구름 에듀(https://edu.goorm.io/)

Cos Pro 1급 공부 사이트 추천 - 구름에듀(https://edu.goorm.io/)