-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
해결됨
2-T 17298번-오큰수 질문
24.05.12 19:40 작성 조회수 70
0
안녕하세요 큰돌 선생님. 수업을 열심히 듣고 있는 학생입니다.
정답이 틀려서 질문했다기보단 강의를 보기 전에 스스로 풀었는데 저는 우선순위 큐를 사용해서 풀었습니다. 맞추고 나서 기분이 좋은 상태로 선생님 강의를 봤는데 스택으로 푸셨더라고요.
이런 방법도 있구나~ 하면서 어떻게 푸셨는지 로직을 보는데 이게 왜 되는지 오랜 시간 생각을 해봐도 논리? (스택 방식으로 푸는게 왜 유효하고 문제가 없는건지)를 모르겠습니다. ㅜㅜ
우선순위큐로 푸는 상황에서는 현재 가르키고 있는 인덱스의 값보다 작은 값의 모든 우선순위큐 안에 있는 인덱스들을 pop을 한다고 확신을 하겠는데 스택은 확신이 안 듭니다
예를 들면 스택안에 현재 인덱스가 가르키는 값보다 작은 값의 인덱스들은 저장을 하며 pop을 하다가 더 큰 값 인덱스를 만나서 while문을 멈췄는데 그 밑에 그러니까 더 일찍 들어온 애들 중에 pop을 해야 하는 애가 있는 상황이 있을까봐 저는 스택이 아닌 우선순위 큐부터 써본 것 같습니다.
이렇게 딱 스택을 써도 문제가 없겠다. 즉 위 같은 상황이 안 생기겠다! 라는 생각이 드는 논리를 알고 싶습니다.
그리고 이렇게 논리를 생각해야하는 문제들을 어떻게 대비해야하는지 여쭤보고싶습니다. 제가 머리가 나쁜지 한 10분 생각을 해봐도 스택이 왜 문제가 없는지 아직도 깨닫지 못했습니다 ㅠㅠ
이런 논리를 생각해내지 못해서 손도 못댄 문제들이 있습니다. 풀어보셨는지는 모르겠지만 프로그래머스에 요격 시스템이라는 문제는 비슷한 이유로 제대로 풀지 못해서 결국 남의 코드를 봤습니다.
밑에는 우선순위 큐로 푼 코드입니다
답변을 작성해보세요.
1
큰돌
지식공유자2024.05.13
안녕하세요 hoon님 ㅎㅎ
먼저 우선순위큐 코드 괜찮네요 ㅎㅎ
군더더기도 없는 코드라 굿굿입니다.
우선순위큐로 푸는 상황에서는 현재 가르키고 있는 인덱스의 값보다 작은 값의 모든 우선순위큐 안에 있는 인덱스들을 pop을 한다고 확신을 하겠는데 스택은 확신이 안 듭니다
...
이렇게 딱 스택을 써도 문제가 없겠다. 즉 위 같은 상황이 안 생기겠다! 라는 생각이 드는 논리를 알고 싶습니다.
>>
먼저 hoon님의 코드
hoon님은 우선순위큐 상단 = 제일 작은 수
이 수가 나오는 경우 -> 이보다 더 큰 수를 찾았을 경우, 순차적으로 해도 문제가 안됨. 어차피 작은 수부터 뽑힐게 자명함.
이런 논리이신거잖아요. 괜찮습니다.
그렇다면 저는 왜 스택을 사용했을까요?
짝짓기 : 일단 스택을 생각해보자. 그러면 스택으로 어떻게 하지? 근데 이 문제 같은 경우는 스택만 있어서는 안될 것같다. 왜? 3 2 1 4 같은 경우는 3 2 1의 오큰수는 4가 되어야 하기 때문에 단순히 1 - 4 같이 짝짓기는 안되겠네 생각 -> 배열을 생각하자.
왜 배열일까? : 3 2 1 에 4라는 값을 담아야 겠다고 생각.
스택을 담는것을 일단 담는다고 생각 (원래 짝짓기 문제에서 보통 그냥 다 일단 담음 그 경험에 비추어 생각)그렇다면 뺄때는 어떻게 해야할까?
스택에 3 2 1 을 담아두었을 때 4가나왔을 때 3 2 1이라는 값에는 4가 할당되어야 함. -> 순차적으로 빼면서 해당 값을 집어넣으면 끝.
이 때 push를 먼저 해야할까?: pop을 먼저해야할까? 4가 나왔을 때 빼는게 먼저이기 때문에 pop -> push를 기반으로 로직 구축
이런 플로우였던 것 같습니다.
모든 문제가 그렇지만 경험 + 예제를 기반으로 하나의 명제를 만들고 그 명제를 기반으로 로직을 구축하시면 됩니다.
그리고 이번 문제 - hoon님의 코드 및 로직도 괜찮았습니다. ㅎㅎ 문제에는 여러가지 답이 있고 그 답중에 괜찮은 답안이신 것 같습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
답변 1