55.기차운행(stack 응용)

it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비

ㅌ

1. 초기

 

2. 최적화

문제해결 아이디어(초기)

• 입력된 값을 배열에 저장
• 문제 해결을 위한 반복문 루프
  • 입력 된 숫자의 개수 N보다 배열의 인덱스가 작으면 Push 하고 'P'문자 저장
  • 불가능 조건 체크 더 이상 Push 할 값이 없고 stack에 남아 있는 값이 교차로 B로 가야할 값보다 클경우 불가능
  • -교차로 stack Pop 반복문
  • 현재 stack이 비어 있는 상태라면 Pop하지말고 다시 Push할 값 찾으러 break;
  • 교차로 B로 가야할 check 값 과 stack의 top의 값이 같으면 Pop 하고 'O'문자 저장 아니면 break;
  • 출력할 ch문자 P,O가 입력된 숫자의 2배 짝이 맞다면 가능한 상태로 break;

문제해결 아이디어(최적화)

• 교차로 stack 중심에서 생각하기
• 숫자 하나 입력받고 바로 stack에 넣은 후 1,2,3,4,... 순서로 check 하며 교차로 B로 Pop하기 check 순서에 맞지 않으면 다시 숫자 입력 받기
• 위 과정을 모두 거쳤을 때 stack에 값이 남아 있다면(check 순서에 맞지 않고 Push 받을 값이 더 이상 없다면 impossible한 경우)