프로그래머스 주식 가격 문제

오늘은 프로그래머스 주식가격 문제를 풀었습니다.

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

코딩테스트 연습 - 주식가격

초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요. 제한사항 prices의 각 가격은 1 이상 10,00

programmers.co.kr

[1차 실수]

처음엔 이문제를 이진탐색 트리를 만들어 풀려고했습니다.

prices벡터를 뒤에서부터 앞으로 탐색하면서, 이진탐색트리를 만들고,

당장 들어온 값보다 작은 애를 찾으려했죠.

근데 고려하지못한 부분으로 당장 들어온 값보다 작다면 가장 최근에 추가된 애를 찾아야하는건데,

그저 당장 들어온 값보다 가장 작은애만 찾았다는게 실수였습니다.

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <stack>


using namespace std;

struct node{
  int data;
  int pos;
  struct node* pLeft;
  struct node* pRight;
};

struct tree{
  struct node *pRoot = NULL;
//성공적으로 만들면 true리턴, 이미있어서 값 수정시 false리턴. 만든노드는  pOutNode로 반환
  bool insert(int data, int pos, node** pOutNode){
      node *pNode = new node();
      pNode->data = data;
      pNode->pos = pos;
      pNode->pLeft = NULL;
      pNode->pRight = NULL;
      
      if(pRoot == NULL){
          pRoot = pNode;
          *pOutNode = pNode;
          return true;
      }
      else{
           return insertFitPos(pRoot, pNode, pOutNode);
      }
  }
  bool insertFitPos(node* parent, node *target, node **pOutNode){
      if(parent->data == target->data){
              parent->pos = target->pos;
              *pOutNode = parent;
              return false;
          }
          else if(parent->data < target->data){
              if(parent->pRight != NULL){
                return insertFitPos(parent->pRight, target, pOutNode);   
              }
              else {
                  parent->pRight = target;
                  *pOutNode = parent->pRight;
                  return true;
              }
          }
          else {
             if(parent->pLeft != NULL){
                 return insertFitPos(parent->pLeft, target, pOutNode);
             } 
              else {
                  parent->pLeft = target;
                  *pOutNode = parent->pLeft;
                  return true;
              }
          }
  } 
  //넘어온 값보다 작은 노드 찾음
  struct node *findNodeSmall(node *parent, int data){
      if(parent->data == data){
          if(parent->pLeft == NULL){
              return NULL;
          }
          else {
              return findNodeSmall(parent->pLeft, data);
          }
      }
      else if(parent->data > data){
          if(parent->pLeft == NULL) {
              return NULL;
          }
          else {
              return findNodeSmall(parent->pLeft, data);
          }
      }
      else{
          if(parent->pRight == NULL){
              return parent;
          }
          else {
              node* pTemp = findNodeSmall(parent->pRight, data);
              if(pTemp == NULL){
                  return parent;
              }
              else{
                  return pTemp;
              }
          }
      }
  }
  struct node* findNodeSmallThan(int data)
  {
      return findNodeSmall(pRoot, data);
  }
};


vector<int> solution(vector<int> prices) {
    vector<int> answer;
    stack<int> ans;
    tree bTree;
    
    for(int i=prices.size()-1;i>=0;i--){
        node * inputNode;
        bTree.insert(prices[i],i+1,&inputNode);
        
        node* pRes = bTree.findNodeSmallThan(inputNode->data);
        printf("Now i : %d \n",i);
        if(pRes == NULL){
            ans.push(prices.size()-(i+1));
        }
        else{
            printf("value %d, pos %d ,  inputNode value %d, pos %d \n",pRes->data,pRes->pos, inputNode->data, inputNode->pos);
            ans.push((pRes->pos)-(i+1));
        }
    }
    
        
    while(!ans.empty()){
        answer.push_back(ans.top());
        ans.pop();
    }
    
    return answer;
}

int main()
{
	while(1){
				
		int n;
		scanf("%d",&n);
		
		vector<int> prices;
		
		for(int i=1;i<=n;i++){
			int t;
			scanf("%d",&t);
			prices.push_back(t);
		}
		vector<int> res = solution(prices);
			
		for(int i=0;i<res.size();i++){
			printf("%d ",res[i]);
		}
		printf("\n\n");
	}
	return 0;	
}

[2차 실수]

1차 실수에서 그저 당장 들어온 값보다 가장 작은애만 찾았다면,

2차 도전에선 작은값중 가장 최근에 들어온애를 전체탐색했습니다. 이러니 당연 정답은 맞춰도, 효율성 부문에서 꽝이였습니다. 딱봐도 최악의 상황은 매번 전체탐색을 하게될테니까요.

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <stack>


using namespace std;

struct node{
  int data;
  int pos;
  struct node* pLeft;
  struct node* pRight;
};

struct tree{
  struct node *pRoot = NULL;
//성공적으로 만들면 true리턴, 이미있어서 값 수정시 false리턴. 만든노드는  pOutNode로 반환
  bool insert(int data, int pos, node** pOutNode){
      node *pNode = new node();
      pNode->data = data;
      pNode->pos = pos;
      pNode->pLeft = NULL;
      pNode->pRight = NULL;
      
      if(pRoot == NULL){
          pRoot = pNode;
          *pOutNode = pNode;
          return true;
      }
      else{
           return insertFitPos(pRoot, pNode, pOutNode);
      }
  }
  bool insertFitPos(node* parent, node *target, node **pOutNode){
      if(parent->data == target->data){
      		
              parent->pos = target->pos;
            //  	printf("pos %d, data %d \n",parent->pos, parent->data);
              *pOutNode = parent;
              return false;
          }
          else if(parent->data < target->data){
              if(parent->pRight != NULL){
                return insertFitPos(parent->pRight, target, pOutNode);   
              }
              else {
                  parent->pRight = target;
                  *pOutNode = parent->pRight;
                  return true;
              }
          }
          else {
             if(parent->pLeft != NULL){
                 return insertFitPos(parent->pLeft, target, pOutNode);
             } 
              else {
                  parent->pLeft = target;
                  *pOutNode = parent->pLeft;
                  return true;
              }
          }
  } 
  //넘어온 값보다 작은 노드 찾음 (작기만 하면!! pos 가장 직전꺼로 찾기) 
  struct node *findNodeSmall(node *parent, int data){
      if(parent->data == data){
          if(parent->pLeft == NULL){
              return NULL;
          }
          else {
              return findNodeSmall(parent->pLeft, data);
          }
      }
      else if(parent->data > data){
          if(parent->pLeft == NULL) {
              return NULL;
          }
          else {
              return findNodeSmall(parent->pLeft, data);
          }
      }
      else{ //현 노드가  찾으려는 데이터보다  값이 작다면 
          node* minNode = parent;
          
          if(parent->pRight != NULL){
             node* pTemp = findNodeSmall(parent->pRight, data);
              if(pTemp != NULL){
              	//printf("!!  %d < %d ", pTemp->pos, minNode->pos);
                  if(pTemp->pos < minNode->pos) {
              	  	minNode = pTemp;
              	  }
              }
          }
          if(parent->pLeft != NULL){
          	 node *pTemp = findNodeSmall(parent->pLeft, data);
          	 if(pTemp != NULL) {
          	 	//	printf("!!  %d < %d ", pTemp->pos, minNode->pos);
          	   if(pTemp->pos < minNode->pos) {
				 minNode = pTemp;	
			   }
          	 }
          }
          return minNode;
      }
  }
  struct node* findNodeSmallThan(int data)
  {
      return findNodeSmall(pRoot, data);
  }
};


vector<int> solution(vector<int> prices) {
    vector<int> answer;
    stack<int> ans;
    tree bTree;
    
    for(int i=prices.size()-1;i>=0;i--){
        node * inputNode;
        bTree.insert(prices[i],i+1,&inputNode);
        
        node* pRes = bTree.findNodeSmallThan(inputNode->data);
       // printf("Now i : %d \n",i);
        if(pRes == NULL){
            ans.push(prices.size()-(i+1));
        }
        else{
          //  printf("value %d, pos %d ,  inputNode value %d, pos %d \n",pRes->data,pRes->pos, inputNode->data, inputNode->pos);
            ans.push((pRes->pos)-(i+1));
        }
    }
    
        
    while(!ans.empty()){
        answer.push_back(ans.top());
        ans.pop();
    }
    
    return answer;
}

int main()
{
	while(1){
				
		int n;
		scanf("%d",&n);
		
		vector<int> prices;
		
		for(int i=1;i<=n;i++){
			int t;
			scanf("%d",&t);
			prices.push_back(t);
		}
		vector<int> res = solution(prices);
			
		for(int i=0;i<res.size();i++){
			printf("%d ",res[i]);
		}
		printf("\n\n");
	}
	return 0;	
}

3차 도전

결국 트리를 만들어서 한다는 생각은 애초에 틀린 방식이였고, 다른 아이디어가 필요했습니다.

생각해보니 문제를 푸는데 핵심은 이 한문장이였습니다.

지금까지 들어온 값 중 자기보다 작은, 그것도 가장 최근 들어온 값.

'가장 최근이란 개념을 적용하기에 최고인 스택을 어떻게 활용하면 좋을까?' 를 생각했고,

1. 스택에 자기보다 크거나 같은값이 있으면 다 빼자. 어차피 자기보다 작은 최근값이 필요하니

굳이 스택에 저장해둘 필요가 없다.

2. 빼는 동작을 했는데도, 스택에 원소가 남아있다면 TOP원소의 위치 - 현재 숫자 위치

스택이 비어있다면 prices벡터 크기 - 현재숫자위치 가 정답이다.

였습니다.

#include <stdio.h>
#include <iostream>
#include <vector>
#include <stack>
#include <stdlib.h>

using namespace std;


vector<int> solution(vector<int> prices) {
    vector<int> answer;
 	
 	stack<pair<int, int> > stk;
 	stack<int> test;
 	
 	for(int i=prices.size()-1;i>=0;i--){
 		
 		while(stk.size() >0 && stk.top().first >= prices[i]){
 			stk.pop();	
 		}
 		if(stk.size() == 0){
 		 test.push(prices.size()-(i+1));
 		}
 		else{
 			test.push(stk.top().second - (i+1));
 		}
 		stk.push({prices[i],i+1});
 	}
 	
 	while(!test.empty()){
 		answer.push_back(test.top());
 		test.pop();
 	}
 	
    return answer;
}

int main()
{
	while(1){
				
		int n;
		scanf("%d",&n);
		
		vector<int> prices;
		
		for(int i=1;i<=n;i++){
			int t=rand()%10000;
//			scanf("%d",&t);
			prices.push_back(t);
		}
		vector<int> res = solution(prices);
			
		for(int i=0;i<res.size();i++){
			printf("%d ",res[i]);
		}
		printf("\n\n");
	}
	return 0;	
}

비슷한 문제

탑 codeup.kr/problem.php?id=4654

탑

문제 4) 탑 (초등 4) KOI 통신연구소는 레이저를 이용한 새로운 비밀 통신 시스템 개발을 위한 실험을 하고 있다. 실험을 위하여 일직선 위에 N개의 높이가 서로 다른 탑을 수평 직선의 왼쪽부터 오

codeup.kr

소들의 헤어스타일 codeup.kr/problem.php?id=3130

소들의 헤어스타일

첫번째 줄에 소의 수 N이 입력된다.(1 <= N <= 80,000) 두 번째 줄 부터 N+1번째 줄까지 각 소들의 키가 입력된다. ( 1 <= hi <= 1,000,000,000 )

codeup.kr

<박기완의 c언어 코딩교육 시리즈 >

게임개발을 희망하는 초등학생, 중학생, 고등학생들을 위한 c언어 책

이 글을 보고있다는건 게임개발에 관심있다는 거겠죠? 그렇다면 정말 잘보셨습니다. 읽기 쉽고, 단기간 내에 자기꺼화 할 수 있게 최대한 핵심만 담았습니다. 게임을 어떻게 만드는지 궁금해

blog.codingteacher.kr

초등, 중등, 고등 1:1 원격 c언어 교육문의

010 - 4537 - 7998

현재 대치동 학원에서 코딩강사로 활동중에 있습니다

영재고, 과학고 내신 /

초등, 중등, 고등 입문반, 초급, 중급, 정올반 /

앱, 게임 제작반 문의주세요!

'박기완 코딩교육 > 코딩테스트 대비' 카테고리의 다른 글

프로그래머스 타겟 넘버 문제 (0)	2020.10.18
프로그래머스 가장 먼 노드 문제 (0)	2020.10.17
프로그래머스 입국심사 문제 (0)	2020.10.16
프로그래머스 스킬트리 문제 (0)	2020.10.15
프로그래머스 기능개발 문제 (0)	2020.10.14

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

억만장자가 될 사람

프로그래머스 주식 가격 문제

'박기완 코딩교육 > 코딩테스트 대비' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

프로그래머스 주식 가격 문제

'박기완 코딩교육 > 코딩테스트 대비' 카테고리의 다른 글

'박기완 코딩교육/코딩테스트 대비' Related Articles

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역