[level 2] 프린터 , queue, max_element=> 활용해 다시 풀어보기

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

예전에 시도했다가 실패한 문제다.

오랜만에 다시 풀어본다.

 

예전에 풀었던 실패한 방식이다. 

1차 실패

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 1;
        int size = priorities.length,temp; 
        int targetPrior = priorities[location];
        int flag []= new int[size];  
        int start = 0,index;
        
        for(int i =0; i< size ; i++) flag[i] = 0;
      
        temp =start;
        
        while(temp > 0) {
    	   index = start;
    	   if(temp == 1) return answer;
	       for(int i = 0; i< temp; i++, index=(index+1)%size) {
	        	while(flag[index]!= 0) 
	        		index = (index+1)%size;
	        	if(priorities[index] > priorities[start]) start = index;
	       }
	       if(location == start) break;
	       
	       flag[start] = 1;
	       
	       while(flag[start]!=0) start = (start+1)%size;
	       temp--;
	       answer++;
       }
        return answer;
    }
}

순환 큐를 풀었던 기억이 난다.

왜 틀렸는지는 확인하기 귀찮다.

 

 

성공한 방법

#include <string>
#include <vector>
#include <utility>

using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    vector < pair<int,int>> plist;
    pair <int,int> p;
    for(int i = 0 ; i < priorities.size();i++)
        plist.push_back(make_pair(i,priorities[i]));
    
    while(!plist.empty()){
        p = plist[0]; 
        int index = 0, max = p.second;//가장 큰 원소 위치 index
        
        for(int i = 0 ; i < plist.size() ; i++ ){//가장 큰 원소 찾고
            if( max < plist[i].second ){
                index = i;
                max = plist[i].second;
            }
        }
        
        if( plist[index].first == location){//제일 큰 원소가 찾는 원소라면 
            return ++answer;
        }
        else{//제일 큰 원소지만 찾는 원소는 아닐때
            if(index == 0) {//제일 큰 원소가 맨 앞에 있는 경우
                plist.erase(plist.begin());
            }
            else{//제일 큰원소가 중간에 있는 경우
                for(int j = 0 ; j<index; j++){//맨뒤로 원소추가
                    plist.push_back(plist[j]);
                }
                plist.erase(plist.begin(),plist.begin()+index+1);//index는 어차피 제일 큰거라 pop할꺼니까 한번에 지워
            }    
        }
        answer++; 
    }   
    return answer;
}

성공은 했으나 스택이나 큐를 사용하지 않았다.

풀이 방법

문제 그대로 따라 갔다.

<print 우선 순위, 처음 위치> pair 값을 넣은 vector plist를 만든다.

plist에서 맨 첫 번째 원소의 우선순위 값을 저장한 후

plist에서 더 큰 우선 순위가 있는 원소를 찾는다. 

1. 제일 큰 원소의 처음 위치가 loction 값과 같다면 바로 리턴

2. 제일 큰 원소가 찾는 원소가 아니라면 2가지 경우로 나뉜다.

    1)제일 큰 원소가 plist의 맨 앞에 위치한 경우

    2) 제일 큰 원소가 중간에 위치한 경우

        큰 원소 위치 전까지의 원소들을 다시 plist에 넣고 처음 부터 큰 원소까지 다 지운다.

 

헷갈린 부분

1. 문제에서 원한 것은 location 위치에 있는 원소가 몇 번째로 출력되냐는 것이다.

하지만 내가 문제를 풀 때 가장 큰 원소이면서 내가 원하던 원소이면 즉 loction에 위치한 동시에 가장 큰 원소이냐는 것이냐 이런 조건을 추가해 문제를 창조하고 있었다. => 문제 풀 때 지문 잘 기억하자 , 같은 말 같지만 문제를 풀다보면 코드 진행 방식이 조금 달라진다.

       if(index == 0){//제일 큰 원소가 지금 원소라면
            answer++;
            cout<<"1. answer " << answer<<endl;
            if(p.first == location) return answer;// 내가 찾는 원소라면
             plist.erase(plist.begin());//j 원소 일단 꺼낸다.
        }
        else{//제일 큰 원소가 다른 원소 라면
            for(int j = 0 ; j<index ; j++){//맨뒤로 원소추가
                plist.push_back(plist[j]);
            }
            
            answer++;
            cout<<"2. answer " << answer << " out : "<<max <<endl;
            plist.erase(plist.begin(),plist.begin()+index);//index는 어차피 제일 큰거라 pop할꺼니까 한번에 지워
            //여기서 한번에 지우자
        }

처음에 이렇게 작성했다. 문제를 다시 읽어보면 왜 틀렸는지 알 수 있다.

 

2. 해당 변수가 무엇을 의미하는 것인지 잘 기억해서 문제를 해결하자.

index 자체가 아닌 plist[index].first와 location을 비교해야한다.

 

 

 

다른 사람 풀이

queue와 max_element를 사용했다. 이것을 활용해 다시 풀어보자.

 

배운 내용

• erase (v.begin(), v.begin()+a) ;시작부터 끝-1까지 지워 줌
• max_element(v.begin(),v.end())
  • 헤더파일 : algorithm 
  • vector에서 존재하는 원소 중  최대, 최소(min_element) 찾기
  • 주소값을 반환하기 때문에 int max = *max_element( v.begin(), v.end() ) 이렇게 사용
  • 활용 : v.erase( max_element(v.begin(), v.end())) //가장 큰 원소 바로 지우기

 

참고사이트

max_element : https://m.blog.naver.com/PostView.nhn?blogId=chansung0602&logNo=221116097894&proxyReferer=https:%2F%2Fwww.google.com%2F