[백준/Java] 2841번 외계인의 기타 연주

 

 

문제 풀이

이 문제는 Stack(스택) 알고리즘으로 푼다.

스택 + 실버 문제라 만만하게 봤는데 1시간 넘게 걸렸다.. 사람은 항상 겸손해야돼 ㅠㅠㅠㅠ

이 문제 코딩테스트로 나오면 히든 테케에서 탈탈 털릴 것 같다 ..🥲

 

 

BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(bf.readLine());
Stack<Integer>[] stack = new Stack[7];

1. 정수를 저장하는 스택들의 배열을 선언한다.

사실 스택에서 배열을 구성해서 문제를 푸는 건 처음이야 ..

 

 

int N = Integer.parseInt(st.nextToken());
int P = Integer.parseInt(st.nextToken());

int ans = 0;

2. 음의 수 N과 한 줄에 있는 프렛의 수 P를 입력 받는다.

나는 P를 사용하지 않았다!

 

정답을 담을 변수 ans를 생성한다.

 

 

for(int i=0; i<=6; i++) {
    stack[i] = new Stack<Integer>();
}

3. 문제에서 기타의 줄이 6개라고 했기 때문에

6개의 Stack 객체를 생성하여 할당한다.(stack[0]은 사용하지 않을거라서 6개라고 설명했다.)

 

그럼 아래의 사진과 같다.

나는 처음에 스택 1개만 만들었는데 여러 반례에 의해 잘못됨을 감지했다.

 

 

 

for(int i=0; i<N; i++) {
    st = new StringTokenizer(bf.readLine());

    int n = Integer.parseInt(st.nextToken());
    int p = Integer.parseInt(st.nextToken());

4. N번 만큼 반복하고,

줄의 번호 n과 그 줄에서 눌러야 하는 프렛의 번호 p를 입력 받는다.

 

//stack이 비어있을 때
if(stack[n].isEmpty()) {
    stack[n].add(p);
    ans++;
    continue;
}

5. 일단 stack[n]이 비어있다면,

해당하는 줄(n)에 프렛 p를 삽입한다.

그리고 이는 손가락을 움직인 것과 같기 때문에 ans를 1 증가시킨다.

그리고 다른 아래 코드는 실행할 필요 없으므로 continue 하고 다음으로 넘어간다.

 

//stack이 비어있지 않을 때
if(stack[n].peek() < p) {
    stack[n].add(p);
    ans++;
}else if(stack[n].peek() > p) {
    boolean check = true;
    while(!stack[n].isEmpty() && stack[n].peek() >= p) {
        if(stack[n].peek() == p) {
            check = false;
            break;
        }
        ans++;
        stack[n].pop();
    }

    if(check) {
        stack[n].add(p);
        ans++;					
    }
}else {
    //같을 때는 아무도 동작도 하지 않음.
}
}

6. stack[n]이 비어있지 않을 때다.

이 때는 3가지로 나눈다.

stack에 가장 마지막에 삽입된 값이 현재 프렛의 번호보다 클 때, 작을 때, 같을 때.

일단 같을 때는 손가락을 움직일 필요가 없으므로 어떤 작업도 수행하지 않아도 된다.

 

if(stack[n].peek() < p) {
    stack[n].add(p);
    ans++;
}

stack에 가장 마지막에 삽입된 값이 현재 프렛의 번호보다 클 때는

손을 떼지 않고, 다른 손가락으로 프렛을 누르면 된다.

그래서 stack[n]에 프렛의 번호 p를 삽입하고, ans를 1 증가시킨다.

 

else if(stack[n].peek() > p) {
    boolean check = true;
    while(!stack[n].isEmpty() && stack[n].peek() >= p) {
        if(stack[n].peek() == p) {
            check = false;
            break;
        }
        ans++;
        stack[n].pop();
    }
    if(check) {
        stack[n].add(p);
        ans++;
    }
}

stack에 가장 마지막에 삽입된 값이 현재 프렛의 번호보다 작을 때는 손가락을 떼야한다.

프렛 p가 소리나기 위해서는 프렛 p보다 큰 값을 가지는 값들을 stack에서 제거해줘야한다.

그래서 while문을 사용했고, while문을 통과할 수 있는 조건은 stack[n]의 크기가 0이 아니고,

stack의 맨 위에 있는 프렛의 번호가 프렛 p보다 클 때이다.

 

 if(stack[n].peek() == p) {
            check = false;
            break;
}

만약 stack의 맨 위에 있는 프렛의 번호와 프렛 p가 같다면 check를 false로 변경한다.

프렛의 번호가 같기 때문에(=이미 손가락으로 해당 프렛을 누르고 있기 때문에) 손가락을 따로 움직일 필요가 없다.

그리고 while문을 빠져나온다.

 

ans++;
stack[n].pop();

만약 같지 않다면 해당 코드를 실행한다.

현재 누르고 있는 프렛에서 손을 떼야하기 때문에 ans를 1 증가 시키고, stack[n]의 맨 위의 값을 제거한다.

 

if(check) {
        stack[n].add(p);
        ans++;
}

while문을 빠져나와 check가 true라면

현재 프렛 p을 stack[n]에 삽입하고, ans를 1 증가시킨다.

 

System.out.println(ans);

7.멜로디를 연주하는데 필요한 최소 손가락 움직임을 출력한다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		Stack<Integer>[] stack = new Stack[7];
		
		int N = Integer.parseInt(st.nextToken());
		int P = Integer.parseInt(st.nextToken());
		
		int ans = 0;
		
		for(int i=0; i<=6; i++) {
			stack[i] = new Stack<Integer>();
		}
		
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(bf.readLine());
			
			int n = Integer.parseInt(st.nextToken());
			int p = Integer.parseInt(st.nextToken());
			
//			stack이 비어있을 때
			if(stack[n].isEmpty()) {
				stack[n].add(p);
				ans++;
				continue;
			}
			
//			stack이 비어있지 않을 때
			if(stack[n].peek() < p) {
				stack[n].add(p);
				ans++;
			}else if(stack[n].peek() > p) {
				boolean check = true;
				while(!stack[n].isEmpty() && stack[n].peek() >= p) {
					if(stack[n].peek() == p) {
						check = false;
						break;
					}
					ans++;
					stack[n].pop();
				}
				
				if(check) {
					stack[n].add(p);
					ans++;					
				}
			}else {
				//같을 때는 아무도 동작도 하지 않음.
			}
		}
		System.out.println(ans);
	}
}

 

 

 

 

 

https://www.acmicpc.net/problem/2841