[프로그래머스] 탑

이 글에서는 프로그래머스 - 탑 문제에 대해 다뤄보겠습니다. 문제 풀이는 C++로 이루어져 있고 함께 들어가 있는 개념들도 간단히 정리 해보는 형식으로 작성되었으므로 오타등의 오류가 있을 수 있습니다. 오류 발견시 댓글로 꼭 말씀해주세요! 시작해볼까요?

 

하 진쟈 한 번만에 성공한거 너무 오랜만이라서 지금 흥분을 주체할 수 없어요. 아니 뭐 꼭 어려운 문제를 풀고 나서 성취를 느껴야 하는 건 아니잖아요? 안그래도 지금 백준에 뭐 안풀리는 문제 있어가지고(풀릴 듯 안풀리는... 분명 내일 풀면 풀릴 거야 망할 토마토...) 자존감 떨어지고 있는데 프로그래머스 와서 힐링 했네요ㅋㅋ

 

문제는 아래 [그림 1] 으로 깔끔하게 요약이 될 것 같습니다. 각 송신탑은 왼쪽으로 시그널을 보내고 자신 보다 높은 송신탑의 수신기가 시그널을 받죠. return 값은 내 시그널을 받은 수신기의 탑 번호, 없다면 0이 들어가 있는 vector 입니다.

 

[그림 1]

---

코드 복사 하고 싶으신 분들은 [더보기]를 눌러주세요

 #include <string>
 #include <vector>
 #include <algorithm>

 using namespace std;

 vector<int> solution(vector<int> heights) {
     vector<int> answer;
     
     // starting from the left to right
     // ends condition i > 0 because answer for first tower is always 0
     int size = static_cast<int>(heights.size());
     for(int i = size - 1; i > 0; i--){
         for(int find = i - 1; find > -1; find--){
             // if receiver tower exists
             if(heights[find] > heights[i]){
                 answer.push_back(find + 1);
                 break;
             }
             // if reciever tower doesn't exist
             if(find == 0)
                 answer.push_back(0);
         }
     }
     answer.push_back(0); // answer for first tower is always 0
     reverse(answer.begin(), answer.end()); // answer push_back started from the left
     return answer;
 }

#12 . 그냥 int size = heights.size() 해도 됩니다. 원래 vector의 size() return type이 unsigned long int인데 type conversion 해주지 않으면 노란 줄이 떠 캡쳐할 때 보기 안좋아서 explicit type conversion 해주었습니다.

#13 -24. 왼쪽 끝 부터 시작해서(바깥 for 문) 나의 시그널을 받아 줄 탑이 있는지를 찾아(안쪽 for문) 답을 저장하는 과정입니다. 어차피 제일 첫번째 탑의 송신을 받아 줄 탑은 없으므로 바깥 for 문의 종료 조건을 첫 번째 탑 검사 전에 끝내는 것으로 만들었습니다.

#25. 첫 번째 송신탑에 해당하는 답은 언제나 0이므로 별도로 삽입해줍니다.

#26. 왼쪽 끝부터 시작했기 때문에 answer에 들어가 있는 답은 실제 답과 역순이므로 한 번 더 뒤집어 줍니다.

 

채점결과 : 정확성(100.0) = 100.0