[2주차_목요일] 42584_주식가격

[baexxbin]

• 사이트: 프로그래머스
• 문제: 주식가격
• 번호: 42584
• 레벨: Level2

[yeongleej]

🤔 시간복잡도 고려사항

prices 길이 == N <= 100,000

💡 풀이 아이디어

가격을 스택에 넣고, 스택의 상단과 비교 스택의 상단 > 현재 가격 : 가격이 떨어짐, 시간기록

[KodaHye]

🤔 시간복잡도 고려사항

• 2 <= prices.length <= 100,000이므로 이중 반복문을 통한 완전 탐색을 한다면 시간 초과 발생
• 스택을 사용하면 O(N)으로 가능

💡 풀이 아이디어

• 기간은 인덱스의 차이로 구할 수 있으므로 스택에는 인덱스를 넣음
• 스택에는 점점 증가하는 숫자들로만 구성되야 함
  1. 0번째 인덱스부터 마지막 인덱스까지 순차적으로 탐색
     • prices[i] < prices[stack.peek()] 이라면 prices[i] >= prices[stack.peek()이 될 때 까지 pop() 하면서 pop()되는 인덱스에서의 기간 구하기
     • 기간 구하는 방법: 현재 인덱스 - pop한 인덱스 값
  2. 탐색이 끝난 후 스택에 남아있는 인덱스에 대해 기간 구해주기
     • 기간 구하는 방법: prices.elgnth - 1 - pop한 인덱스 값

[yeahdy]

🤔 시간복잡도 고려사항 시간복잡도: 2 <= prices <= 100,000 크기로 O(NlogN) 까지 가능

💡 풀이 아이디어

• 알고리즘: queue
• 아이디어: queue 에 모든 주식을 넣고 하나씩 꺼냄 다음 주식이 현재 주식 보다 작다면 누적된 값++ , 멈춤 다음 주식이 현재 주식 보다 크거나 같다면 누적된 값++, 주식이 떨어질 때 까지 늘려간다 어떤 경우에서든 +1 을 하기 때문에 배열의 index를 활용함 > 배열[index]++

[Jewan1120]

🤔 시간복잡도 고려사항

• 2 ≤ prices의 길이 ≤ 100,000 → 10^5이므로 O(nlogn)
• 배열 순회 및 스택에서 데이터 비교까지 가능

💡 풀이 아이디어

1. 정답 배열의 초기 값으로 끝까지 가격이 떨어지지 않았을 때의 값을 설정
2. 현재 위치에서 다음 자기보다 작은 값이 나오는 것을 감지해야 함 → 스택
3. 뒤에서부터 순회하면서 아래의 과정 반복
   1. 자신보다 큰 값들은 pop
   2. 스택에 자신보다 작은 값이 있다면 그 값의 인덱스를 이용해 정답 배열의 값 계산
   3. 자신을 스택에 넣음

[baexxbin]

🤔 시간복잡도 고려사항

• 2 ≤ prices의 길이 ≤ 100,000
• O(NlogN) 이내로 풀기

💡 풀이 아이디어

• 가격이 떨어지는 시점을 확인: for문 뒤에서부터 돌기
• i시점에서 가격이 떨어지는 초 값을 가지고 있음: DP느낌
• 현재 값이 떨어지지 않는 동안 cnt값 업데이트
  • 이때 이전 ans[]의 값 활용
  • 다음 값(nxt)을 확인해 값이 떨어지지 않는 구간이라면, 해당 구간의 ans값(ans[i + cnt]) (해당 구간에서 유지되는 초 값)을 이용해 현재의 ans값 업데이트

처음에 스택으로 풀려했는데 실패.. 너무 복잡하게 생각하지 말자..

[icegosimperson]

🤔 시간복잡도 고려사항

• prices 길이 100,000 이하로 크지 않아서 시간 복잡도를 고려하지 않음

💡 풀이 아이디어

• 이중 반복문을 이용하여 인덱스 값을 비교한 뒤 큰 값이 있으면
• 가격이 떨어지지 않은 기간은 몇초인지 return