#코딩테스트 #PS #백준 #baekjoon
이번 문제는 피드백(http://blog). naver.com/bible20141/222587426622)을 위해 트라이 유형을 찾아 풀어본 문제였다. 올해 초 프로그램에서 같은 문제를 만나 정렬을 활용해 풀었는데, 트라이 알고리즘을 사용해 풀었더니 난이도가 갑자기 높게 느껴졌다. 하지만 산업체를 하면서 PS하는 나의 공부 특성상 장시간 문제를 해결하지 못하는 경우가 많아 약점인 구조체의 구현 실력을 연습할 조건이 없다. 당분간 회사가 성수기라 딱히 더 이상의 시간은 없을 것 같다. 우선 오늘의 문제도 트라이를 구현해 실패해 정렬을 쓰고 통과했지만 다음에 기회가 되면 구조체와 반을 사용해 문제 푸는 연습을 반복해보자.Solved.ac 기준 골드4였다. 골드 1 → 플레이 5 승급까지 AC.Rating 앞으로 23점. * 문제 유형 : 자료 구조, 문자열, 정렬, 트리, 트라이
- 문제 난이도…(3/10): 문제 통과 자체는 어렵지 않지만 트라이얼로 푸는 것은 실패했다.약 4시간 잡았다 – 체감설계 난이도(2/5) : 구조체, 클래스, 포인터의 실력이 여전히 약하다. 해법을 떠올리기는 쉽다. – 체감 구현 난이도(1/5) : 포인터를 다루는 연습을 집중해서 날짜를 잡아보자.정렬 구현은 간단하다.1. 바로 해동성공(30minmax) 2. 알고리즘 유형을 확인하여 해동성공(30minmax) 3. 알고리즘 유형 공부하고 해동성공(60minmax) 4. 문제접근 확인 후 해동성공(60minmax) 5. 업솔빙으로 통과(nomax)
처음에 트라이를 구조체로 구현하려 했으나 실패하였고, 이어서 벡터를 사용하여 트라이를 구현하려 했으나 실패했다. 정렬을 이용해 1차 통과하고 다시 벡터를 사용해 트라이 구현하려 했으나 연달아 실패 후 다른 사람의 트라이 구조를 참고해 통과했다. 아직 확실히 모르겠어, 트라이 구현 방법은.<문제>:n개의 전화번호가 주어진다. 어떤 전화번호가 다른 전화번호 접두사라면 NO를 출력하라. 그런 경우가 아니면 YES출력. https://www.acmicpc.net/problem/50525052번 제출, 맞춘 사람, 문자 코딩, 재채기 결과, 점수 현황, 강의, 전화 번호 목록, 다언어 시간 제한, 메모리 제한 제출, 맞힌 사람, 정답율 1초 256MB, 27409,8548,505029.541%, 문제, 전화 번호 목록이 주어진다. 이때 이 리스트가 일관성이 있는지를 요구하는 프로그램을 작성하세요. 전화 번호 목록이 일관성을 유지하려면 하나의 번호가 다른 번호의 접두어인 경우가 있어서는 안 된다. 예를 들어 전화 번호 목록이 다음과 같은 경우를 생각하고 보면 긴급 전화:911정규:97625999선영:91125426때…www.acmicpc.net<정렬에 풀이있던 코드…통과>:sort한 후의 전후 비교.<2차원 배열로 트라이를 실장해 본 코드…> 실패>: 트라이를 2차원 벡터로 실장하자. 전화번호는 최대 10자리이고 n은 10000개여서 벡터로 표현 가능…. 하지만 신기하게도 중간에 index 오류가 나서 어디서 나올지는 찾았지만 고치지 못하고 디버깅 보류했다.<코드설계> -n회 동안 nums를 받고 x자리 nums라면 x번 전화번호부(phones)를 체크하면서 새로 추가하거나 기존 번호를 따른다.- 예를 들어 ‘123’을 검색할 때 -phones [0] [i] [0] == ‘1’이면 이미 있으므로 idx를 phones [0] [i]로 바꾼다.- 그리고 이어서 2를 가진 인덱스가 phones[i] 안에 있는지 찾아본다. – bool형 isover를 만들어서 i번째 위치가 단어의 마지막인지 아닌지 표시하자.phones에서 새로운 단어가 추가될 때마다 isover도 업데이트 하자.(ex): ’12’, ’13’, ‘123’을 입력받은 경우, phones와 isover는 다음과 같다. (phones) 0:”, 11: ‘1’, 2, 32: ‘2’, 43: ‘3’, 4: ‘3’, (isover) 0: false 2: true 4:true <구조체에서 트라이 구현한 코드 참조… 통과>: 트라이를 구조체에 구현하여 풀었던 코드. 참고: https://ip99202.github.io/posts/%EB%B0%B1%EC%A4%80-5052-%EC%A0%84%ED%99%94%EB%B2%88%ED%98%B8-%EB%AA%A9%EB%A1%9D/