tony9402
[2020 NHN 코딩테스트] Pre-Test 1차 후기 본문
[2020년] NHN 그룹사 신입 개발자 공개채용 Pre-Test 1차
예전에 교내에서 NHN 장학생 선발이 있었는데 그 선발이 되기 위해서는 코딩테스트를 통과해야 했다. 그때 나왔던 문제가 NHN 코딩테스트에서 쓰였던 문제라고 했는데 유형이 쉬운 구현 위주였다.
이번 시험에 총 3문제가 나왔다. 아침 8시까지 랩실에서 다른 작업하다가 집에 가서 3 ~ 4시간 정도 자고 시험 보러 다시 랩실 와서 너무 졸린 상태로 시험을 보게 됐다. 너무 졸리기도 하고 1번 문제를 보고 풀기 귀찮았는데 최근에 만들기 시작한 코딩테스트 대비 문제집(각 유형별로 문제 모음)을 만들기 위해서 참고 풀었다..
문제 내용은 NHN의 저작권이 있으므로 알고리즘 유형, 비슷한 문제, 시간복잡도만 언급하겠다.
1번
시간 복잡도 쿼리당 O(1)
귀찮은 구현(풀이는 바로 나왔지만 잠을 거의 못자서 귀찮...았다) 하지만 쉬운 구현. 상황을 잘 생각해보고 조건문을 잘 쓰면 된다.
2번
시간 복잡도 쿼리당 O(N)
옛날에 엄청 못풀어했던 문제였다. 사실 최근까지 못 풀던 문제라 어떻게 풀지 했는데 멍 때리다가 갑자기 풀이가 나와서 풀었다.
2304번: 창고 다각형
첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의
www.acmicpc.net
14719번: 빗물
첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치
www.acmicpc.net
시험문제 다 풀고 이 문제를 같은 방식으로 풀었을때 맞았다. 창고 다각형 문제를 통해 풀이를 설명하겠다.
1. 왼쪽에서 오른쪽으로 최댓값을 뽑는다. le[i] = max(le[i-1], arr[i])
2. 오른쪽에서 왼쪽으로 최댓값을 뽑는다. re[i] = max(re[i+1], arr[i])
3. 이제 왼쪽에서 오른쪽으로 쭉 가면서 넓이를 확인한다. ans += min(le[i], re[i])
NHN 문제에서는 위 3번이랑 살짝 달랐지만 이런 식으로 풀면 된다. (NHN 본 사람들은 알 것이다.)
공유 소스 보기
#include #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define FOR(i,s,e) for(int i=s;i<=e;i++) #define FORI(i,s,e,d) for(int i=s;i<=e;i+=d) using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int dy[]
www.acmicpc.net
공유 소스 보기
#include #define all(x) (x).begin(),(x).end() #define siz(x) (int)(x).size() #define FOR(i,s,e) for(int i=s;i<=e;i++) #define FORI(i,s,e,d) for(int i=s;i<=e;i+=d) using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int dy[]
www.acmicpc.net
3번
시간 복잡도 쿼리당 O(L)
귀찮은 구현, 어느 정도 난이도 있는 구현
앗 내가 가장 귀찮아하고 한번 말리면 계속 말리는 문제가 나왔다. 하지만 하나씩 풀어나가면 쉽게 풀린다.
백준에 비슷한 유형이 있지만 이 문제보다 매우 쉽다.
1662번: 압축
압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이
www.acmicpc.net
16362번: Parentheses
Your program is to read from standard input. The input consists of a single line containing a C expression. The expression is a string of single-lowercase alphabets, special symbols including left and right parentheses and five binary arithmetic operators
www.acmicpc.net
난이도는 대체적으로 쉬웠다. 생각한 풀이를 코딩으로 옮기는 능력이 있거나 코딩 실수가 없다면 쉽게 풀 수 있는 문제이다.
+
(3번은 맞게 풀고 제출 다른걸로 했고, 1번은 문제 범위 조건 안봐서 대충 mod 했다가 틀렸을거 같다. 만약 진짜 취준이였다면 검토 과정에서 발견하여 아마 약 1시간 정도 걸렸을꺼 같다. 하지만 너무 피곤해서 대충 보고 끄는 바람에 실수를 못잡아서 아쉽긴 하다.)
1번 모듈러 범위가 더 큰줄 알았지만 끝나고 보니깐 더 작았다.
x = (x + input + mod) % mod // | input | <= mod 인 경우는 된다. 하지만 1번 조건을 보니 | input | > mod 이 존재했다.
해결방법은 다양하다.
x = ((x + input) % mod + mod) % mod로 하거나
x = (x + input) % mod;
if(x < 0)x += mod;
로 하면 된다.