Everyday Code : addBinary

วันนี้เราจะมาเรียนรู้จากโจทย์ addBinary ใน Leetcode กันครับ ซึ่งเป็นโจทย์ที่ผู้เขียนคิดว่าเราได้เรียนรู้อะไรมากมายจากการทำโจทย์ข้อนี้เป็นอย่างมาก

Problem : โจทย์จะกำหนดเลขฐาน 2 มาให้ในรูปแบบของ String และนำตัวแปรทั้ง 2 มาบวกกันผลลัพธ์ที่ได้จะเป็น เลข Binary เช่นกัน

น่าสนใจมากว่าแต่ Binary หรือเลขฐาน 2 มันคืออะไรกันนะ ? ก่อนที่เราจะทำโจทย์ข้อนี้ ผมจะพาทุกคนไปรู้จักกับเลขฐาน 2 หรือ Binary กันครับ

EP 1 : Binary

Binary ( เลขฐาน 2 ) ถ้าใครยังไม่รู้จักเลขฐาน 2 ผมขออธิบายสั้นๆแบบนี้ครับ

เลขฐาน 2 ก็เหมือนเลขฐาน 10 ที่เราใช้กันทุกวัน อย่าง 0–9 ครับ

แต่หลักการของ Binary คือการเลือกผลลัพธ์และนำมาบวกกันให้ได้ตามเป้าหมายครับ

โดยที่เริ่มต้นด้วย 2⁰ , 2¹ ไล่ขึ้นไปเลื่อยๆตามภาพนี้ครับ

หลังจากที่เรากำหนดค่าให้แต่ละตำแหน่งแล้ว เราก็จะตั้ง Target หรือเป้าหมายขึ้นมาในใจครับ

How to change the base ( เลขฐาน 10 ) to binary

ถ้าเราต้องการแปลงเลข 52 ( เลขเป้าหมาย ) ให้กลายเป็น binary

เราจะเลือกค่าจาก Binary มารวมกันให้ได้เท่ากับตัวเลขที่ต้องการ คือ เลข 32 16 4 ทั้งหมด 3 ตัว

และแน่นอนเราจะเปลี่ยนให้กลายเป็นเลข Binary ด้วยการแทนค่าว่า 0 = ไม่เอา 1 = เอานั้นเอง

ดังนั้นเรามาแก้โจทย์ด้วยการ Code กันดีกว่า

Problem Binary : จงแปลงเลข ใดใดก็ตามที่ไม่เกิน 255 ให้กลายเป็น Binary

Let Code !

สร้าง class Solution เพื่อนำไปใช้ใน main ก่อนเลย

class Solution{
  String convert(int n){
		
  }
}

ขั้นตอนที่ 1 : เราจะกำหนดจำนวนมากที่สุดของ byte ก่อน อย่างในรูปข้างบนก็คือ 128 เพื่อที่จะสับเลขให้เป็นจำนวนย่อยลงไปเลื่อยๆในทุกครั้งที่เราสร้าง Code ที่จะเลือกหรือไม่เลือกค่านั้นออกมา

int valueByte = 128;

ขั้นตอนที่ 2 : เรารู้จากการแปลงเลขข้างบนว่า การแปลงเลขฐาน 10 เป็น Binary คือการเลือกเลขในช่วงต่างๆแหละนำมาบวกกัน แต่มันมีเงื่อนไขดังนี้

• ถ้าเรากำหนดเลข 50 เราจะไม่เลือกช่องที่มีค่า 64 เนื่องจาก มันเกินเป้าหมายของเรา

if(valueByte > target) ; เราจะไม่เลือกเลขนั้น หรืออีกความหมายคือ "0"

• ถ้าเลข 50 เหมือนเดิมแต่เราเป็นค่าในช่อง 32 เราจะเลือก เพราะมันต่ำกว่าเป้าหมายของเรา

if(valueByte <= target) ; เราจะเลือกตัวเลขนี้ หรืออีกความหมายคือ "1"

และนี้คือ Condition ทั้งหมดในการเลือกเลข

ขั้นตอนที่ 3 : สร้าง Loop ที่จะแปลงตัวเลขเมื่อเราผ่านเงื่อนไขต่างๆใน Condition จากขั้นตอนที่ 2

เราจะสร้าง While Loop ด้วยการคิดถึงการดำเนินการไปเลื่อยๆของ Logic นี้

• เมื่อเราผ่านตัวเลขในชุดที่เราจะเลือกหรือไม่เลือก
• อย่างเช่น target = 50 ; เราจะต้องเลื่อนผ่าน 128 และ 64 นั้นก็คือเราต้องเปลี่ยนแปลงค่า valueByte ด้วย
• ทุกครั้งที่เราเลือกหรือไม่เลือกค่านั้น ค่าต่อไปจะถูกหาร 2 ลงเสมอ

128 → 64 → 32 → 16 …. ไปเลื่อยๆ

เราจะใช้ Operator / (หาร) ด้วย 2 ลงไปเลื่อยๆ และเมื่อถึงเลขสุดท้าย ก็คือ 1 เมื่อ 1/2 จะกลายเป็น 0 ( เพราะเรากำหนดตัวแปรเป็น Int )

while(valueByte!=0)
 // condition จากขั้นตอนที่ 2
ทุกครั้งที่เลือกหรือไม่เลือก Update ค่าด้วยการ /2
valueByte = valueByte /2 ;// หรือ valueByte /= 2 ; ก็ได้

เอาหละ อย่างสุดท้ายเมื่อเราเลือกค่าใดค่าหนึ่งในส่วนย่อยของ 128 เราต้องทำการ Update อีกหนึ่งค่า

นั้นก็คือ target หริอ เป้าหมายของเราด้วย เพื่อให้ในสุดท้ายผลรวมจากการเลือกจะเท่ากับ target ของเรา

เมื่อเราเลือก if(valueByte<target); target = target - valueByte // หรือ target -= valueByte

แค่นี้เราก็ได้เงื่อนไข และวิธีทั้งหมดในการ แปลงเลขฐาน 10 เป็นเลข ฐาน 2 แล้ว

ประกอบร่างงง

class Solution{
  String convert(int target){
  int valueByte = 128;
  String result = "";
  while(valueByte != 0){
    if(valueByte > target ) result = result + "0" ;// ไม่เลือกเพราะ valueByte มากกว่า
    // เพิ่มค่า 0 เข้าไปใน String คำตอบ
    if(valueByte < target ) 
      result = result + "1" ; 
      target = target - valueByte ;
    //เมื่อเลือกค่าใน valueByte แล้วต้องหักลบออกจากค่าเป้าหมายด้วย
			
      valueByte = valueByte / 2 ; 
    // เมื่อเสร็จสิ้น Condition ต้องอัพเดทค่าเพื่อทำในรอบต่อไป
   }
  return result ;
  }
}

เสร็จแล้วว !! และต่อไปเราจะไปกันต่อกับบทความใน Ep ต่อไป เพื่อนำ Logic นี้ไปใช้กับ addBinary กัน

( ซึ่งต้องขอเกริ่นก่อนเลยว่าเป็นวิธีที่ผิดนะ 555 แต่ถ้าหากเราไม่รู้วิธีที่ผิดจะเรียนรู้วิธีที่ถูกแบบประสิทธิภาพได้ยังไง )

อย่าลืม รอติดตามใน Ep ต่อไป Everyday Code : addBinary Ep.2