본 문제는 level2 라고 하기엔 조금 놀랄만큼 쉬웠던 문제이다. 해결한 사람 수만 봐도 level1의 문제와 비슷했기 때문에 쉬울거라고 예상은 했었지만 정말 쉬운 문제였다. 다만, 본 문제가 왜 Stack/Queue 문제인지는 아직 잘 이해가가지 않는다. stack을 시용해서 풀 수는 있으나 여러가지 다른 방법으로도 해결 가능하기 때문에… 물론 모든 문제가 제시된 방법으로만 해결되는 것은 아니기 때문에 어떤 방법으로든 효율성 좋게 해결만 한다면 괜찮지 않을까?
1. 문제
수평 직선에 탑 N대를 세웠습니다. 모든 탑의 꼭대기에는 신호를 송/수신하는 장치를 설치했습니다.
발사한 신호는 신호를 보낸 탑보다 높은 탑에서만 수신합니다. 또한, 한 번 수신된 신호는 다른 탑으로 송신되지 않습니다.
예를 들어 높이가 6, 9, 5, 7, 4인 다섯 탑이 왼쪽으로 동시에 레이저 신호를 발사합니다. 그러면, 탑은 다음과 같이 신호를 주고받습니다.
높이가 4인 다섯 번째 탑에서 발사한 신호는 높이가 7인 네 번째 탑이 수신하고, 높이가 7인 네 번째 탑의 신호는 높이가 9인 두 번째 탑이, 높이가 5인 세 번째 탑의 신호도 높이가 9인 두 번째 탑이 수신합니다. 높이가 9인 두 번째 탑과 높이가 6인 첫 번째 탑이 보낸 레이저 신호는 어떤 탑에서도 수신할 수 없습니다. 맨 왼쪽부터 순서대로 탑의 높이를 담은 배열 heights가 매개변수로 주어질 때 각 탑이 쏜 신호를 어느 탑에서 받았는지 기록한 배열을 return 하도록 solution 함수를 작성해주세요.
제한조건
- heights는 길이 2 이상 100 이하인 정수 배열입니다.
- 모든 탑의 높이는 1 이상 100 이하입니다.
- 신호를 수신하는 탑이 없으면 0으로 표시합니다.
2. 알고리즘! 생각해보자
heights벡터의 마지막 원소부터 시작해 처음 원소가 될 때까지 다음을 반복한다.- 현재 원소 앞의 원소부터해서 계속해서 앞으로 반복하며 현재 원소보다 큰 값이 나오면 원소의 위치를
answer벡터의 앞에 넣는다. - 해당 원소보다 큰 값이 없으면
answer의 앞에 0을 넣는다. heights벡터의 반복이 끝나면,answer를 반환한다.
3. 해결코드
[C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <string>
#include <vector>
using namespace std;
vector<int> solution(vector<int> heights) {
vector<int> answer;
for (int i = heights.size() - 1; i >= 0; i--) {
bool is_insert = false;
for (int j = i - 1; j >= 0; j--) {
if (heights[i] < heights[j]) {
is_insert = true;
answer.insert(answer.begin(), j + 1);
break;
}
}
if (!is_insert) answer.insert(answer.begin(), 0);
}
return answer;
}
4. 해결능력UP, 깊이 생각해보기
vector의insert()사용 방법- 효율성을 더 좋게 하는 방법은 없나…
stack을 사용할 수는 있는데 알고리즘 자체는 똑같아서..
5. 참고해서 문제해결 ٩( ᐛ )و
- [C++ 공식문서] std:vector:insert http://www.cplusplus.com/reference/vector/vector/insert/
1
출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges