[백준(BOJ)] 2841번 외계인의 기타 연주 C++

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

2841번: 외계인의 기타 연주

어떤 문제인가?

기타를 치는데 가장 높은 프렛의 음이 발생하는 조건이 있다.

따라서 원하는 음을 치자고 할 때 높은 프렛을 누르고 있던 손가락을 떼야한다.

원하는 음이 기존에 누르고 있던 프렛보다 높다면 상관은 없다.

 

 

이때, 입력한 n번만큼 원하는 프렛과 줄 번호가 주어졌을 때, 손가락을 가장 적게 움직이는 횟수를 출력해야 한다.

 

접근 방법

처음에는 이 문제를 vector와 pair를 사용해 프렛과 줄 번호를 저장하려고 했다.

하지만, 이를 통해 구현하려고 하니 굉장히 답답했고 어떻게 해야 할지 감이 잘 잡히지 않았다.

문제를 다시 읽으며 고민하다가 입력한 프렛과 현재 누르고 있는 프렛 중 가장 큰 프렛부터 비교하며 손가락을 누르고 있을지, 떼야할지를 정해야 한다는 생각을 통해 자연스럽게 stack을 이용할 생각을 할 수 있었다.

 

stack<int>guitar[6];

기타는 총 6줄이므로 위와 같이 선언했다.

 

손가락의 이동 횟수를 저장할 변수를 선언해준다.

int cnt=0;

당연히 0으로 초기화한다.

 

int N, P;
cin>> N >> P;

for(int i=0; i < N; i++){
    int line, plat;
    cin >> line >> plat;

 

그다음 연주 횟수, 프렛의 수를 입력받는다.

그다음 줄 번호 프렛 번호를 입력받는다. 

그다음 입력된 각 줄마다 입력된 프렛의 번호를 추가하는 방식으로 진행했다.

 

이 문제는 발생할 수 경우의 수를 모두 처리해주어야 했다.

 

 

1. 입력된 줄에 손가락이 없을 때.

if(guitar[line-1].empty()){
    guitar[line-1].push(plat);
    cnt++;
}

 

입력된 줄에 아무런 손가락도 존재하지 않으니 줄에 추가(손가락을 올린다)해주고 횟수를 증가시킨다.

 

2. 입력된 줄에 있는 가장 큰 프렛이 입력된 프렛보다 작을 때.

else if (guitar[line-1].top() <plat){
        cnt ++;
        guitar[line-1].push(plat);
}

이 경우에는 현재 누르고 있는 프렛 중 가장 큰 프렛보다 입력된 프렛이 높으므로 입력된 프렛의 소리가 날 것이므로

손가락을 뗄 필요 없이 줄에 추가(손가락을 올린다)해주고 횟수를 증가시키면 된다.

 

 

3. 입력된 줄에 있는 가장 큰 프렛이 입력된 프렛과 같을 때.

else  if(guitar[line-1].top() == plat ){
    continue;
}

 

이 경우에는 그냥 continue를 해주면 된다.

 

4. 입력된 줄에 있는 가장 큰 프렛이 입력된 프렛보다 클 때.

else if(guitar[line-1].top() > plat){
    while(!guitar[line-1].empty() && guitar[line-1].top() > plat){
        guitar[line-1].pop();
        cnt ++;
    }

    if(!guitar[line-1].empty() && guitar[line-1].top() == plat ){
        continue;
    }
    else{
        guitar[line-1].push(plat);
        cnt++;
    }
}

이 경우가 가장 복잡한 경우이다.

 

먼저 while문을 통해 입력된 줄에 있는 가장 큰 프렛이 입력된 프렛보다 작아질 때까지 반복하며

입력된 줄에 있는 프렛을 삭제(손가락을 뗀다)한다. 

이때 반복 한 번마다 횟수를 증가시킨다. 손가락을 하나 씩 떼는 것이기 때문이다.

 

그다음, 만약 입력된 줄에 있는 가장 큰 프렛이 입력된 프렛과 같다면 continue를 통해 별도의 작업 없이 넘어간다.

 

만약 그렇지 않다면 입력된 줄에 프렛을 추가(손가락을 올린다)하고 횟수를 증가시킨다.

 

마지막으로 모든 입력이 끝난 후 손가락이 움직인 횟수를 출력하면 끝!

cout << cnt;

 

 

무엇이 어려웠는가?

먼저 자료구조를 선택하는 것부터 쉽지 않았다.

자료구조를 선택하는 것 부터 시간이 걸려서 어렵게 느껴졌다.

 

그리고 가장 어렵게 느껴졌던 것은 예외 처리였다.

1, 2, 3번 경우를 생각해내는 것은 큰 어려움은 없었다.

 

하지만 4변 경우의 예외를 처리하는 것에서 시간을 많이 잡아 먹혔다.

 

guitar[line-1].push(plat);
cnt++;

원래는 while문이 끝나면 그냥 추가를 했다. 당연히 입력된 프렛보다 큰 프렛들을 다 삭제(손가락을 뗀다)했으니 이렇게 하는 것이 맞다고 생각했다. 하지만 출력이 계속 이상하게 되어서 계속 고민했다...

 

이럴 땐 어쩌구, 저럴 땐 저쩌고~~..~~ 이렇게 하나씩 과정을 말하던 중 "같을 때는 상관없으니까 그냥 넘어가고.."를 내 입으로 직접 말했다. 그러고 3초후에 어? 엥? 하고 내 코드를 보니 같을 때에 대한 코드가 적혀있지 않았다.

왜 내 뇌는 이 코드를 작성하지도 않고 컴퓨터 탓만 했는가.....

같을 때는 그냥 넘어가야한다고 생각해서인지 내 뇌에서도 코드를 작성하지 않고 넘어가버렸다.

해결하고 나니 참 허탈스러웠다..

 

 

배운 점

 

문제를 읽으면 바로 아! 자료구조 이걸 써야지! 가 생각나야 할 텐데 아직 많이 부족하다고 문제를 풀 때마다 느끼는 것 같다.

 

예외 처리를 확실하고 꼼꼼하게 하자. 머리로는 분명 생각했던 것인데 코드를 쓸 때 빼먹는 경우가 많다고 느껴진다.

문제를 풀기 전에 먼저 머리로만 흐름을 그리지말고, 내 머리를 믿지 말고 생각한 내용을 다 패드에 적어놓고

이걸 보면서 코드를 써내려가고, 생각난 것은 다시 패드에 적고 이런 습관을 들여야 할 것 같다.

.

.

.

.

P.S. 요 며칠 컴공 고질병(거북목, 라운드 숄더 등)으로 인해 몸 컨디션이 좋지 않아서 좀 뜸했다.

몸이 불편하니 아무것도 하기가 싫어서 정말 병원 다니면서 치료받고 푹 쉬었다.

쉬는 게 질릴 때쯤 몸도 많이 괜찮아져서 오늘 블로그를 썼다.

앞으로 더 열심히해야겠다. 화이팅!

 

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EC%8D%B8%EB%A8%B8%EC%BD%94%EB%94%A9/2841.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.