[프로그래머스 Level 2] 메뉴 리뉴얼 (C++)

문제 (https://programmers.co.kr/learn/courses/30/lessons/72411)

코딩테스트 연습 - 메뉴 리뉴얼

- 처음 생각 (시간 초과)

orders 반복 -> course 반복 -> course 반복문 내에서 orders 문자열로 next_permutation 돌림

do while문 내에서 orders 문자열을 인덱스 0~j 부분을 잘라준다.

잘라낸 문자열을 정렬하고 set에 존재하는지 확인한다.

set에 해당 문자열이 존재하지 않는다면 set에 삽입, map에 해당 문자열 value 값 증가

 

위 과정을 마치면 map에 정말 많은 수들이 들어있다,,, map을 확인하면서 value 값이 2 이상이면서 해당 문자열 길이 중 최대 value 값인 문자열들을 answer에 삽입했다.

=> 시간이 매우 오래 걸림.... 

 

- 구글링을 통해서 course for문 내의 코드를 변경한 후 통과

tmp라는 vector를 생성하고 false로 초기화한 후 course 값만큼만 true로 설정한다. next_permutaion으로 tmp 벡터를 조합시키고 조합된 벡터 중 true인 인덱스에 위치한 문자들로 문자열을 생성한다. (즉, 인덱스를 조합한 것!)map에 생성된 문자열의 value 값을 증가시켜준다.

 

위 과정을 마치고 정답에 해당하는 값들을 찾기 위해 map을 정렬해야 하는데, value 값을 기준으로 내림차순 정렬을 해야 한다.정렬을 위해 map을 vector로 옮기고 정렬했다.

 

정렬 후 vector를 반복하며 해당 value가 1. 동일한 길이의 문자열 중 최댓값인지, 2. value 값이 2 이상인지 확인한 후 answer에 삽입해주면 끝!

---

[소스코드 - 통과]

[소스코드 - 시간 초과]