BAEKJOON / 백준 - JAVA 2841번 외계인의 기타 연주

2024.04.30기준 - 실버1

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

이 문제는 상근이의 상상의 친구인 외계인이 손가락을 수십억 개 가지고 있는 상황에서 기타 멜로디를 연주할 때,

손가락을 가장 적게 움직여야 하는 횟수를 구하는 문제입니다.

 

한 번에 한 손가락으로 한 번의 프렛을 누르거나 떼는 것을 한 번의 손가락 움직임으로 정의합니다.

 

각 줄 별로 눌러야 하는 프렛을 저장할 리스트를 선언을 했습니다.

 

그 줄에 눌려있는 프렛이 없다면 (size가 0이라면),

그 줄에 해당하는 list에 프렛 번호를 추가하고 count를 올려줍니다.

 

그 줄에 눌려있는 프렛이 있다면,

눌러야 하는 프렛보다 더 높은 프렛들을 제거하면서 count를 올려줍니다.

만약, 지금 눌러야 하는 프렛이 눌려져 있다면 count를 올리지 않고 바로 진행해 줍니다.

중복된 프렛이 없는 경우 count를 올려주면서 list에 프렛을 저장합니다.

 

반복문 마지막으로 프렛을 내림차순으로 정렬을 한 뒤 계속 진행합니다.

 

이 문제를 해결하기 위해 입력된 멜로디를 순차적으로 처리하면서 필요한 손가락 움직임을 계산했습니다.

각 줄마다 눌러야 하는 프렛을 저장하고, 이미 눌려있는 프렛보다 낮은 프렛을 누를 때마다 손가락을 한 번 더

움직이는 방식으로 손가락 움직음을 계산했습니다.

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int count = 0;
		
		List<List<Integer>> list = new LinkedList<>();
		for (int i = 0; i < 7; i++) {
        	// 각 줄별로 눌어야 하는 프렛을 저장할 리스트 초기화.
			list.add(new LinkedList<>());
		}
		
		while (n-- > 0) {
			st = new StringTokenizer(br.readLine());
			int l = Integer.parseInt(st.nextToken()); // 줄 번호
			int num = Integer.parseInt(st.nextToken()); // 눌러야 하는 프렛 번호
			
			if (list.get(l).size() == 0) { // 해당 줄에 아무 프렛도 눌려있지 않은 경우
				count++; // 손가락을 움직여 count++
				list.get(l).add(num); // 눌러야 하는 플렛 추가
			} else {
            	// 중복된 프렛이 있는지 확인하는 변수 선언
				boolean bo = false;
				
                // 이미 눌러있는 프렛보다 낮은 프렛을 누를 때까지 반복
				while (list.get(l).size() != 0 && list.get(l).get(0) >= num) {
                	// 중복된 프렛이 있을 경우
					if (list.get(l).get(0) == num) {
						bo = true;
						break;
					} else {
						count++; // 손가락을 움직여 count++
						list.get(l).remove(0); // 눌러야 하는 프렛 제거
					}
				}
				
                // 중복된 프렛이 없는 경우
				if (!bo) {
					count++; // 손가락을 움직여 count++
					list.get(l).add(num); // 눌러야 하는 프렛 추가
				}
			}
			
            // 프렛을 내림차순으로 정렬
			Collections.sort(list.get(l), (o1, o2) -> o2 - o1);
		}
		
		bw.write(Integer.toString(count));
		bw.flush();
		bw.close();
		br.close();
	}
}