QQ의 다이어리

문제 https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWqU0zh6rssDFARG SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 이 문제는 입력된 문자열들을 중복 제거, 길이 짧은 순 정렬, 길이 같다면 사전순 정렬하는 문제이다. 처음에는 문제 대충 읽고 중복 제거 + 사전순 정렬로 생각해서 set으로 구현했는데 당연히 틀려서 삽질을 좀 했었다.. 그리고 이 문제가 시간 제한이 있어서 cin/cout을 쓰면 pass를 못한다. 그래서 scanf/printf를 사용해야 하는데, 또 문자열을 다루기 때문에 string..

문제 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 풀이 n개의 숫자 중에서 자신보다 작은 수의 개수를 하나씩 출력하는 문제이다. 처음에는 set을 사용하여 풀이하려고 시도했다. set에 입력받은 수를 insert 하면 정렬이 되고, 중복이 제거되므로 for문을 돌면서 작은 수들의 개수를 세려고 했지만 시간 초과가 발생했다. set이나 map은 정렬과 중복 제거가 수행되지만 인덱스로 접근할 수..

문제 https://www.acmicpc.net/problem/2002 2002번: 추월 입력은 총 2N+1개의 줄로 이루어져 있다. 첫 줄에는 차의 대수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 대근이가 적은 차량 번호 목록이 주어지고, N+2째 줄부터 N개의 줄에는 영식이 www.acmicpc.net 풀이 map 사용하는 문제에 재미 들렸다 ㅎ 먼저 map에 입력되는 차량 번호와 순서(0~n의 값을 갖는 각 차량의 번호표)를 저장한다. 추월하지 않았다면 들어와야 했을 번호를 idx에 저장한다. 배열을 생성해서 차가 터널에서 나가면 앞서 저장한 번호표에 해당하는 인덱스로 가서 1을 입력한다. (3번 번호표를 갖는 차가 나가면 arr[3]의 값을 1로 변경. 이 과정이 없으면..

문제 https://www.acmicpc.net/problem/13414 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net 풀이 온갖 STL을 떡칠한지라 ;; 당연히 시간 초과가 날 줄 알았으나 그렇지 않았다. map과 set에 대해서는 꽤 안다고 생각했는데 이 문제를 풀면서 배운 것이 많아서 정리한다. set을 사용하자니 입력값인 학번들이 입력 순서대로가 아니라 학번 순서로 정렬될 테니 적합하지 않았고, vector를 사용하자니 탐색이 너무 느릴 것 같았다. 그래서 unordered set을 사용하..

문제 https://swexpertacademy.com/main/talk/codeBattle/problemDetail.do?contestProbId=AV-Tj7ya3jYDFAXr&categoryId=AYIPD136YD8DFATO&categoryType=BATTLE&battleMainPageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 힙을 구현한 후, 1과 함께 어떤 숫자가 입력되면 그 수를 힙에 추가하고, 2가 입력되면 루트 노드를 출력하고 삭제한다. 풀이 처음에 10^5를 바보같이 10000로 생각해서 계속 런타임 에러가 났다..ㅋ 배열 크기는 여유있게 100005 정도로 잡아두고, 배열을 ..

문제 https://swexpertacademy.com/main/talk/codeBattle/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD&categoryId=AYIPD136YD8DFATO&categoryType=BATTLE&battleMainPageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 풀이 트리는 구조체로 구현하고, 공통 조상을 찾은 후, 서브트리의 크기는 BFS로 알아낸다. 공통조상을 알아내는 것은 그냥 단순하게 정점들을 방문하고 비교해보면서 찾아냈는데 더 좋은 방법이 있을 것 같다.. 트리를 구현하는 것은 구조체의 배열을 이용해서 인덱스로 접..

문제 https://www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 풀이 2차원 벡터를 생성해서 입력값들을 저장했다. 2차원 벡터로 문자열과 1차원 정수 벡터를 짝으로 묶었으므로, 아래와 같이 저장된다. v.first v.second[0] v.second[1] v.second[2] 이름 국어 점수 영어 점수 수학 점수 그 후, comp 함수를 생성하여 정렬했는데, comp 함수에는 문제가 요구하는 내용을 바탕으로 정렬하도록 했다. 국어 ..

문제 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이 DLL을 이용하여 풀 수 있는 문제이다. 포인트는, 첫 번째로 현재 커서의 위치를 나타내는 cur 포인터가 연산이 끝나고 제자리를 잘 가리키도록 해야 한다는 것이다. 추가 연산을 한 후에는 새로 생성된 노드를 가리키고, 삭제 연산을 한 후에는 가리키던 노드의 이전 노드를 가리키도록 한다. 왼쪽이나 오른쪽으로 이동하는 연산을 할 때는 연결리스트의 범위를 넘어가지 않도록 한다. 두 번째는 연..

문제 https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 풀이 입력으로 주어지는 배열의 원소 개수가 최대 8개이므로, 브루트포스로 하나하나 확인해가며 최댓값을 찾으면 된다. 이때 모든 경우의 수를 찾기 위해 next_permutation 을 사용했다. 입력받은 배열을 오름차순으로 정렬한 후, 계속해서 다음 순열을 찾으면서 원소들의 절댓값을 더한다. 끝날 때까지 반복하고 나면 max 변수에 최댓값이 저장된다. 코드 #include #include #include ..

문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 R이 입력되었을 때, 매번 배열을 뒤집으면 시간 초과가 발생할 것이다. R이 입력될 때마다 flag를 설정해서 처리해줬다. 뒤집힌 상황 -> D가 입력됨 -> 뒤에서 노드를 제거 뒤집히지 않은 상황 -> D가 입력됨 -> 앞에서 노드를 제거 즉, 앞 뒤에서 노드를 제거할 수 있어야 하므로 더블리 링크드 리스트를 사용했다. 더블리 링크드 리스트로 구현하면 값을 출력할 때도 맨 뒤 노드부터 prev로 접근하면서 역순으로 출력하거나, head부터 ..