로그인 유지
이문제를 풀었는데 런타임에러.. 시간초과가 되서 그러는데요..
장원영선생님께서 O(n+m)알고리즘으로 고안해보시라고 해법을 올려주셨는데..
감이 안잡히네요..
그러면 for문을 1번 돌려서 처리해야되죠..?
어떻게 해야될지.. 잘 몰르겠어요..
알려주시면 감사하겠습니다.
nlgn의 시간복잡도를 가지는 방법은 알려드릴 수 있을것 같습니다.
1.
구조체를 이용하여 정렬해 순위를 증가시켜주면서 자신의 앞 원소가 자신보다 크면 자신은 현재까지 나온 순위중 가장 마지막이 되고 자신의 앞 원소가 자신과 같다면 그 원소와 같은 순위가 되는 방식으로 순위를 정해주고 자신의 원래 위치를 저장해서 값을 호출할 수 있습니다.
2.
원소가 100까지 밖에 없으니 각각의 원소의 순위를 기억해주는 방법이 있습니다.
배열을 복사해서 정렬하고 각각 순위를 증가시켜주면서 그 원소의 순위를 배열로 참조한 후, 처음 원래배열에서 원소의 순위값을 읽어 출력하는 방법입니다.
도움이 됐기를 바랍니다.
감사합니다
덕분에 No good없이 풀었네요^^
nlgn의 시간복잡도를 가지는 방법은 알려드릴 수 있을것 같습니다.
1.
구조체를 이용하여 정렬해 순위를 증가시켜주면서 자신의 앞 원소가 자신보다 크면 자신은 현재까지 나온 순위중 가장 마지막이 되고 자신의 앞 원소가 자신과 같다면 그 원소와 같은 순위가 되는 방식으로 순위를 정해주고 자신의 원래 위치를 저장해서 값을 호출할 수 있습니다.
2.
원소가 100까지 밖에 없으니 각각의 원소의 순위를 기억해주는 방법이 있습니다.
배열을 복사해서 정렬하고 각각 순위를 증가시켜주면서 그 원소의 순위를 배열로 참조한 후, 처음 원래배열에서 원소의 순위값을 읽어 출력하는 방법입니다.
도움이 됐기를 바랍니다.