또다시 코딩

https://programmers.co.kr/learn/courses/30/lessons/42584

문제를 처음 확인할 때 생각해볼 수 있는 가장 쉬운 방법으로는 O(n^2) 시간 복잡도를 가지고 있는 완전 탐색이다.

그러나 문제를 읽어보면 다음 인덱스 시점의 시간에서 가격이 떨어지느냐 안 떨어지느냐에 따라 return값이 결정된다는 것을 확인할 수 있다.

한 가지 주의해야 할 점은 다음 인덱스가 이전 인덱스보다 작다는 것을 알기 전 시간은 이미 1초가 흘렀다고 생각하는 것이고

전부 다 돌아보는 것이 아닌 두 번째 for문부터는 바로 앞 인덱스부터 탐색을 시작하면 해결할 수 있다.

문제의 분류로는 스택과 큐 카테고리에 존재하지만 오히려 스택과 큐를 활용하여 해결방법을 생각해보더라도 오히려 코드가 더 길어질 것 같으며 큰 차이가 없을 것 같아 다음과 같이 완전 탐색과 같은 방법으로 해결하였다.

3 언어의 코드 방식도 전부 동일하며 문제 예시에 대한 이해를 빠르게 한다면 빠른 시간 내에 해결할 수 있을 것 같다.

C++

#include <string>
#include <vector>

using namespace std;

vector<int> solution(vector<int> prices) 
{
    vector<int> answer;
    for(int i=0;i<prices.size();i++)
    {
        int cnt=0;
        for(int j=i+1;j<prices.size();j++)
        {
            cnt++;
            if (prices[i] > prices[j])
                break;
        }
        answer.push_back(cnt);
    }
    return answer;
}

Java

class Solution 
{
    public int[] solution(int[] prices) 
    {
        int[] answer = new int[prices.length];
        for(int i=0;i<prices.length;i++)
        {
            for (int j=i + 1;j<prices.length;j++)
            {
                answer[i]++;
                if (prices[i]>prices[j])
                    break;
            }
        }
        return answer;
    }
}

Python3

def solution(prices):
    answer = [0] * len(prices)
    # prices 크기만큼 빈 리스트를 할당.
    for i in range(0,len(prices)):
        for j in range(i + 1, len(prices)):
            answer[i] += 1
            if prices[i]>prices[j]:
                break;
    return answer

https://github.com/ukjinlee66/BOJ/blob/master/17406.cpp

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

문제에서 시키는 방법대로만 구현하면 되는 문제였다. 다만 배열을 돌리기 위해서 가장 바깥 단계부터 안쪽으로 몇 단계까지 돌려야 하는지는 s라는 변수를 생각하여 코딩하였고 3번의 시도 끝에 풀게 되었는데 next_permutaion 사용 시 vector라던지 배열이 sort 되어있는 상태에서 사용되어야 한다는 것을 다시 한번 생각하는 시간이 되었다.

도형의 종류별로 회전과 대칭의 index를 확인해보며 넣었을 경우 얻는 값을 최대로 경신해주기만 하면 풀리는 막일 문제였다. 꼼꼼하게 체크할게 거의 없었고 가능하면 정리해서 코드를 짜야 하지만 역량테스트를 치른다는 가정하에 가장 빠르게 해결하기 위하여 너저분하게 코드가 짜였다.

https://github.com/ukjinlee66/BOJ/blob/master/14500.cpp

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

새로운 게임1과의 차이점이라면 더이상 맨밑의말만 움직이는것이 아닌 모든 말이 각턴에 움직이게되는데 말위에 있더라도 그놈이 업고있는놈들을데리고 말을 내려서 이동한다는 점이다. 단지 level을 없애고 vector index만 잘 조절해주면 해결되는 문제이다.

https://github.com/ukjinlee66/BOJ/blob/master/17837.cpp

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