[원티드] 2022 3rd 쇼미더코드 후기

쇼미더코드

처음으로 쇼미더코드 문제를 풀어보았다.

 

코딩 테스트 결과에 따라 배지를 부여받을 수 있다고 한다.

 

결과

사실 아직도 코딩테스트는 익숙지 않은 것 같다..

문제도 꼼꼼히 읽어봐야겠다..

 

A. 누적합을 이용한 문제이다.

문제를 잘못읽어 1 또는 2의 가장 긴 길이를 반환하도록 구현해서 틀렸다.

https://www.acmicpc.net/problem/1912

1912번: 연속합

백준의 해당 문제와 매우 유사하다.

1인 경우 + 1, 2인 경우 -1로 계산하고, 음수가 되는 경우 시작점을 초기화하여 0으로 다시 계산하도록 풀어주었다.

 

 

B. 영역의 개수를 구하는 블러드필 문제이다.

다만 도넛 모양으로 주어진다. 따라서 배열의 밖으로 넘어가는 경우 반대쪽으로 돌아가도록 구현해 주면 된다.

 

 

C. A그룹과 B그룹이 악수를 하는데 그룹내 학생마다 선호도가 주어진다.

악수하는 두 학생의 선호도에 따라 W[a][b]의 만족도가 올라간다. 이때 최대가 되도록 만족도를 구해주면 된다.

 

처음에는 각 그룹의 학생들이 모두 붙어 있다고 생각해 2중 포문을 통해 풀었다. -> 틀렸음

순서만 지키면 되기 때문에 백트래킹을 통해 조합으로 선택하여 풀었다. -> 시간초과

dp를 이용한 방법이 떠올랐다.

악수할 경우 (이전 값중 최댓값 + 현재 악수한 경우)와 악수하지 않을 경우(현재값 포함 이전 최댓값)로 나누어 dp테이블을 갱신해 주어 해결했다.

 

 

다시 생각해보면 문제 자체는 그리 어렵지 않았던 것 같다.

하지만 유형 파악과 시간복잡도 파악때문에 몇 차례 틀렸다.. 단순히 문제만 풀게 아니라 문제 파악의 중요성을 뼈저리게 깨닫게 되었다..

 

---

금손뱃지 득!