[강원대학교] 교내 프로그래밍 대회 예선 후기

예선은 2시간 5문제로 구성되었습니다.

프로그래머스에서 진행했으며 처음엔 9문제였지만, 5문제로 줄었네요.

 

3번까지는 매우 쉽다가 난이도가 갑자기 증가했네요.

설명은 자바 기준이며 효율성은 고려하지 않아 비효율적인 알고리즘일 수 있습니다.

더 좋은 로직이 있다면 공유해주세요.

1번, 2번, 3번은 단순 구현입니다.

 

1번은 return a*b; 였나요?

2번과 3번의 순서가 헷갈리는데 감안해서 읽어주세요.

 

2번은 x, y 좌석의 중복을 제거하는 문제였습니다.

저는 Set 배열을 이용하여 x 좌표 값을 배열 인덱스로 이용했습니다.

(2, 4) -> set[2].contains(4) 

 

3번은 binary로 이루어진 String을 적절히 처리하면 됩니다.

시작 문자(0, 1)를 StringBuilder에 넣은 후 for 루프를 돕니다.

변수는 문자 개수 count, 직전 문자를 저장하는 number를 이용했습니다.

만약 현재 읽은 문자와 number가 다르다면 아스키코드를 이용하여 빌더에 넣어줬습니다.

예를 들어 count가 3이라면 count + 'A'로 'D'가 나오겠네요.

 

4번부터는 어려웠습니다. 유니온 파인드와 리스트를 이용했습니다.

2020/11/06 - [문제풀이/자바] - [백준 1976] 여행 가자 (자바)

[백준 1976] 여행 가자 (자바)

유니온 파인드에 관한 설명은 위 포스트와 안에 또 있는 다른 포스트를 읽으며 공부하면 됩니다.

 

백준 기준 골드 3 정도로 생각하네요.

특정 그룹의 중앙값을 출력하면 되는 문제였는데 문제 설명이 너무 복잡해서 문제 읽는 시간이 너무 오래 걸렸습니다.

 

t1, t2를 유니온 파인드로 모두 묶습니다. 그 후 대푯값 배열 parent를 돌면서 모든 대푯값을 Set에 넣었습니다.

이 값을 기준으로 어레이 리스트에 그룹의 값을 넣었습니다. 이 리스트를 오름차순으로 정렬하고 다시 링크드 리스트에  중앙값을 넣었습니다. Set에 있는 값을 기준으로 한 링크드 리스트에서 중앙값을 모두 뽑아냈으면 정답 링크드 리스트에 모든 값이 모였을 텐데 이 값을 오름차순 정렬하여 반환했습니다.

 

5번은 위상 정렬을 이용했습니다. 골드 2 정도로 생각합니다.

2020/10/02 - [문제풀이/자바] - [백준 2252] 줄 세우기 (자바)

[백준 2252] 줄 세우기 (자바)

위상 정렬의 개념입니다.

 

4, 5번은 작정하고 낸 것 같습니다. 어려운 개념에 함정을 하나씩 심어 놓았습니다.

이 문제에서 함정은 예제 1번에서 나온 A입니다. 문제에서 원하는 값까지 가기 위해 필요한 값과 불필요한 값을 찾아야 합니다.

x->y로 이어지는 link를 만들었고, y->x로 이어지는 path를 만들었습니다.

link는 위상 정렬을 하는데 이용하며 path는 문제에서 요구하는 값에 필요한 값인지 검사합니다.

예를 들어 "B"까지 가기 위해 필요한 값을 알기 위해 path를 이용해 B부터 출발하여 모든 값을 체크합니다.

다른 함정은 선후관계가 존재하지 않는다면 사전 순으로 출력하는 것인데 이것은 그냥 큐 대신 우선순위 큐를 이용해서 해결했습니다.

 

위상 정렬을 하며 필요한 값 + 우선순위 큐 이용 이 두 가지를 통해 정답을 출력할 수 있습니다.

 

다양한 실력을 가진 학생들이 볼 텐데 개념과 문제를 이해했다는 가정하에 자세히 작성해봤습니다. 물론 매우 쉽게 작성하지 않았습니다.

본선에서는 더 어려운 문제가 나올 텐데 최대한 많이 푸는 것을 목적으로 시험을 봐야겠습니다.

 

더 좋은 로직을 알고 있거나 설명이 부족한 부분은 말씀해주세요.

모든 문제는 자바를 기준으로 설명했으니 다른 언어에서 지원하지 않는 자료구조가 있을 수 있는데 직접 구현하거나 개념을 이해했다면 응용하여 풀 수 있을 것으로 생각합니다.